dotparser.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    DotParser.java
 *    Copyright (C) 2003 Ashraf M. Kibriya
 *
 */
package weka.gui.graphvisualizer;

import java.io.BufferedReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.StreamTokenizer;

import weka.core.FastVector;



/**
 * This class parses input in DOT format, and 
 * builds the datastructures that are passed to it.
 * It is NOT 100% compatible with the DOT format. The 
 * GraphNode and GraphEdge classes do not have any provision 
 * for dealing with different colours or  shapes of nodes, 
 * there can however, be a different label and ID for a 
 * node. It  also does not do anything for labels for 
 * edges. However, this class won't crash or throw an 
 * exception if it encounters any of the above 
 * attributes of an edge or a node. This class however,
 * won't be able to deal with things like subgraphs and 
 * grouping of nodes.
 *
 * @author Ashraf M. Kibriya ([e-mail])
 * @version 1.0 - 23 Apr 2003 - Initial version (Ashraf M. Kibriya)
 */
public class DotParser implements GraphConstants  {

    /** These holds the nodes and edges of the graph */
    protected FastVector m_nodes, m_edges;
    /** This is the input containing DOT stream  to be parsed */
    protected Reader m_input;
    /**  This holds the name of the graph if there is any otherwise it is null */
    protected String m_graphName;

    /**
    *
    *  Dot parser Constructor
    *
    * @param input - The input, if passing in a string then
    *                encapsulate that in String reader object
    * @param nodes - Vector to put in GraphNode objects,
    *                corresponding to the nodes parsed in from
    *                the input
    * @param edges - Vector to put in GraphEdge objects,
    *                corresponding to the edges parsed in from
    *                the input
    */
    public DotParser(Reader input, FastVector nodes, FastVector edges) {
	m_nodes = nodes; m_edges = edges;
	m_input = input; 
    }


    /**
     * This method parses the string or the InputStream that we
     * passed in through the constructor and builds up the
     * m_nodes and m_edges vectors
     *
     * @return - returns the name of the graph
     */
    public String parse() {
	StreamTokenizer tk = new StreamTokenizer(new BufferedReader(m_input));
	setSyntax(tk);

	graph(tk);

	return m_graphName;
    }

    
   /**
    * This method sets the syntax of the StreamTokenizer.
    * i.e. set the whitespace, comment and delimit chars.
    *
    */
   protected void setSyntax(StreamTokenizer tk) {
	tk.resetSyntax();
	tk.eolIsSignificant(false);
	tk.slashStarComments(true);
	tk.slashSlashComments(true);
	tk.whitespaceChars(0,' ');
	tk.wordChars(' '+1,'\u00ff');
	tk.ordinaryChar('[');
	tk.ordinaryChar(']');
	tk.ordinaryChar('{');
	tk.ordinaryChar('}');
	tk.ordinaryChar('-');
	tk.ordinaryChar('>');
	tk.ordinaryChar('/');
	tk.ordinaryChar('*');
	tk.quoteChar('"');
	tk.whitespaceChars(';',';');
	tk.ordinaryChar('=');
    }

    /*************************************************************
     *
     * Following methods parse the DOT input and mimic the DOT 
     * language's grammar in their structure
     *  
     *************************************************************
     */
    protected void graph(StreamTokenizer tk) {
	try {
	    tk.nextToken();
	    
	    if(tk.ttype==tk.TT_WORD) {
		if(tk.sval.equalsIgnoreCase("digraph")) {
		    tk.nextToken();  
		    if(tk.ttype==tk.TT_WORD) {
			m_graphName = tk.sval;
			tk.nextToken();
		    }
		    
		    while(tk.ttype!='{') {
			System.err.println("Error at line "+tk.lineno()+" ignoring token "+tk.sval);
			tk.nextToken();
			if(tk.ttype==tk.TT_EOF)
			    return;
		    }
		    stmtList(tk);
		}
		else if(tk.sval.equalsIgnoreCase("graph"))
		    System.err.println("Error. Undirected graphs cannot be used");
		else
		    System.err.println("Error. Expected graph or digraph at line "+tk.lineno());
	    }
	}
	catch(Exception ex) { ex.printStackTrace(); }


	//int tmpMatrix[][] = new int[m_nodes.size()][m_nodes.size()];
	//for(int i=0; i<m_edges.size(); i++)
	//    tmpMatrix[((GraphEdge)m_edges.elementAt(i)).src]
	//	     [((GraphEdge)m_edges.elementAt(i)).dest] = ((GraphEdge)m_edges.elementAt(i)).type;
	//for(int i=0; i<m_nodes.size(); i++) {
	//    GraphNode n = (GraphNode)m_nodes.elementAt(i);
	//    n.edges = tmpMatrix[i];
	//}

	//Adding parents, and those edges to a node which are coming out from it
	int tmpEdges[], noOfEdgesOfNode[]=new int[m_nodes.size()], noOfPrntsOfNode[]=new int[m_nodes.size()];
	for(int i=0; i<m_edges.size(); i++) {
	    GraphEdge e = (GraphEdge)m_edges.elementAt(i);
	    noOfEdgesOfNode[e.src]++;
	    noOfPrntsOfNode[e.dest]++;
	}
	for(int i=0; i<m_edges.size(); i++) {
	    GraphEdge e  = (GraphEdge)m_edges.elementAt(i);
	    GraphNode n  = (GraphNode)m_nodes.elementAt(e.src);
	    GraphNode n2 = (GraphNode)m_nodes.elementAt(e.dest);
	    if(n.edges==null) {
		n.edges = new int[noOfEdgesOfNode[e.src]][2];
		for(int k=0; k<n.edges.length; k++)
		    n.edges[k][1]=0;
	    }
	    if(n2.prnts==null) {
		n2.prnts = new int[noOfPrntsOfNode[e.dest]];
		for(int k=0; k<n2.prnts.length; k++)
		    n2.prnts[k]=-1;
	    }
	    int k=0;
	    while(n.edges[k][1]!=0) k++;
	    n.edges[k][0] = e.dest;
	    n.edges[k][1] = e.type;
	    
	    k=0;
	    while(n2.prnts[k]!=-1) k++;
	    n2.prnts[k] = e.src;	    
	}
    }
    

    protected void stmtList(StreamTokenizer tk) throws Exception{
	tk.nextToken();
	if(tk.ttype=='}' || tk.ttype==tk.TT_EOF)
	    return;
	else {
	    stmt(tk);
	    stmtList(tk);
	}
    }

    
    protected void stmt(StreamTokenizer tk) {
	//tk.nextToken();

	if(tk.sval.equalsIgnoreCase("graph") || tk.sval.equalsIgnoreCase("node") || tk.sval.equalsIgnoreCase("edge") )
	    ; //attribStmt(k);
	else {
	    try {
		nodeID(tk);
		int nodeindex= m_nodes.indexOf(new GraphNode(tk.sval, null));
		tk.nextToken();
		
		if(tk.ttype == '[')
		    nodeStmt(tk, nodeindex);
		else if(tk.ttype == '-')
		    edgeStmt(tk, nodeindex);
		else
		    System.err.println("error at lineno "+tk.lineno()+" in stmt");
	    }
	    catch(Exception ex) {  System.err.println("error at lineno "+tk.lineno()+" in stmtException"); ex.printStackTrace();
	    }
	}
    }


    protected void nodeID(StreamTokenizer tk) throws Exception{
	
	if(tk.ttype=='"' || tk.ttype==tk.TT_WORD || (tk.ttype>='a' && tk.ttype<='z') || (tk.ttype>='A' && tk.ttype<='Z')) {
	    if(m_nodes!=null && !(m_nodes.contains( new GraphNode(tk.sval, null))) ) { 
		m_nodes.addElement( new GraphNode(tk.sval, tk.sval) ); 
		//System.out.println("Added node >"+tk.sval+"<"); 
	    }
	}
	else
	    { throw new Exception(); }

	//tk.nextToken();
    }

    
    protected void nodeStmt(StreamTokenizer tk, final int nindex) throws Exception {
	tk.nextToken();
	
	GraphNode temp = (GraphNode) m_nodes.elementAt(nindex);

	if(tk.ttype==']' || tk.ttype==tk.TT_EOF) 
	    return;
	else if(tk.ttype==tk.TT_WORD) {

	    if(tk.sval.equalsIgnoreCase("label")) {

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
			temp.lbl = tk.sval;
		    else
			{ System.err.println("couldn't find label at line "+tk.lineno()); tk.pushBack();}
		}
		else 
		    { System.err.println("couldn't find label at line "+tk.lineno()); tk.pushBack(); }
	    }

	    else if(tk.sval.equalsIgnoreCase("color")){

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
			;
		    else
			{ System.err.println("couldn't find color at line "+tk.lineno()); tk.pushBack(); }
		}
		else 
		    { System.err.println("couldn't find color at line "+tk.lineno()); tk.pushBack(); }
	    }

	    else if(tk.sval.equalsIgnoreCase("style")) {

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"') 
			;
		    else
			{ System.err.println("couldn't find style at line "+tk.lineno()); tk.pushBack(); }
		}	    
		else 
		    { System.err.println("couldn't find style at line "+tk.lineno()); tk.pushBack(); }
	    }
	}
	nodeStmt(tk, nindex);
    }


    protected void edgeStmt(StreamTokenizer tk, final int nindex) throws Exception {
	tk.nextToken();

	GraphEdge e=null;
	if(tk.ttype=='>') {
	    tk.nextToken();
	    if(tk.ttype=='{') {
		while(true) {
		    tk.nextToken();
		    if(tk.ttype=='}')
			break;
		    else {
			nodeID(tk);
			e = new GraphEdge(nindex, m_nodes.indexOf( new GraphNode(tk.sval, null) ), DIRECTED);
			if( m_edges!=null && !(m_edges.contains(e)) ) {
			    m_edges.addElement( e );
			    //System.out.println("Added edge from "+((GraphNode)(m_nodes.elementAt(nindex))).ID+" to "+
			    //		       ((GraphNode)(m_nodes.elementAt(e.dest))).ID);  
			}		
		    }
		}
	    }
	    else {
		nodeID(tk);
		e = new GraphEdge(nindex, m_nodes.indexOf( new GraphNode(tk.sval, null) ), DIRECTED);
		if( m_edges!=null && !(m_edges.contains(e)) ) {
		    m_edges.addElement( e );
		    //System.out.println("Added edge from "+((GraphNode)(m_nodes.elementAt(nindex))).ID+" to "+
		    //		       ((GraphNode)(m_nodes.elementAt(e.dest))).ID);  
		}
	    }
	}
	else if(tk.ttype=='-') { 
	    System.err.println("Error at line "+tk.lineno()+". Cannot deal with undirected edges"); 
	    if(tk.ttype==tk.TT_WORD)
		tk.pushBack(); 
	    return; 
	}
	else { 
	    System.err.println("Error at line "+tk.lineno()+" in edgeStmt"); 
	    if(tk.ttype==tk.TT_WORD)
		tk.pushBack(); 
	    return;
	}

	tk.nextToken();
	
	if(tk.ttype=='[')
	    edgeAttrib(tk, e);
	else 
	    tk.pushBack();
    }
    

    protected void edgeAttrib(StreamTokenizer tk, final GraphEdge e) throws Exception{
	tk.nextToken();
	
	if(tk.ttype==']' || tk.ttype==tk.TT_EOF) 
	    return;
	else if(tk.ttype==tk.TT_WORD) {

	    if(tk.sval.equalsIgnoreCase("label")) {

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
			System.err.println("found label "+tk.sval);//e.lbl = tk.sval;
		    else
			{ System.err.println("couldn't find label at line "+tk.lineno()); tk.pushBack();}
		}
		else 
		    { System.err.println("couldn't find label at line "+tk.lineno()); tk.pushBack(); }
	    }

	    else if(tk.sval.equalsIgnoreCase("color")){

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
			;
		    else
			{ System.err.println("couldn't find color at line "+tk.lineno()); tk.pushBack(); }
		}
		else 
		    { System.err.println("couldn't find color at line "+tk.lineno()); tk.pushBack(); }
	    }

	    else if(tk.sval.equalsIgnoreCase("style")) {

		tk.nextToken();
		if(tk.ttype=='=') {
		    tk.nextToken();
		    if(tk.ttype==tk.TT_WORD || tk.ttype=='"') 
			;
		    else
			{ System.err.println("couldn't find style at line "+tk.lineno()); tk.pushBack(); }
		}	    
		else 
		    { System.err.println("couldn't find style at line "+tk.lineno()); tk.pushBack(); }
	    }
	}
	edgeAttrib(tk, e);
    }

    
    /**
     *
     * This method saves a graph in a file in DOT format.
     * However, if reloaded in GraphVisualizer we would need 
     * to layout the graph again.
     *
     * @param filename  - The name of the file to write in. (will overwrite)
     * @param graphName - The name of the graph
     * @param nodes     - Vector containing all the nodes
     * @param edges     - Vector containing all the edges 
     */
    public static void writeDOT(String filename, String graphName, FastVector nodes, FastVector edges){
	try {
	    FileWriter os = new FileWriter(filename);
	    os.write("digraph ", 0, ("digraph ").length());
	    if(graphName!=null)
		os.write(graphName+" ", 0, graphName.length()+1);
	    os.write("{\n", 0, ("{\n").length());

	    GraphEdge e;
	    for(int i=0; i<edges.size(); i++) {
		e = (GraphEdge) edges.elementAt(i); 
		os.write(((GraphNode)nodes.elementAt(e.src)).ID, 0, ((GraphNode)nodes.elementAt(e.src)).ID.length());
		os.write("->", 0, ("->").length() );
		os.write(((GraphNode)nodes.elementAt(e.dest)).ID+"\n", 0, ((GraphNode)nodes.elementAt(e.dest)).ID.length()+1);
	    }
	    os.write("}\n", 0, ("}\n").length());
	    os.close();
	}
	catch(IOException ex) { ex.printStackTrace(); }
    }
    
} // DotParser