source: branches/MetisMQI/src/main/java/weka/gui/graphvisualizer/DotParser.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 University of Waikato, Hamilton, New Zealand
 *
 */
package weka.gui.graphvisualizer;

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

import weka.core.FastVector;
import weka.gui.graphvisualizer.GraphNode;
import weka.gui.graphvisualizer.GraphEdge;



/**
 * 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 (amk14@cs.waikato.ac.nz)
 * @version $Revision: 1.4 $ - 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()];
    int 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