source: branches/MetisMQI/src/main/java/weka/gui/graphvisualizer/DotParser.java @ 35

Last change on this file since 35 was 29, checked in by gnappo, 15 years ago

Taggata versione per la demo e aggiunto branch.
File size: 14.3 KB
Line 
1/*
2 *    This program is free software; you can redistribute it and/or modify
3 *    it under the terms of the GNU General Public License as published by
4 *    the Free Software Foundation; either version 2 of the License, or
5 *    (at your option) any later version.
6 *
7 *    This program is distributed in the hope that it will be useful,
8 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
9 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10 *    GNU General Public License for more details.
11 *
12 *    You should have received a copy of the GNU General Public License
13 *    along with this program; if not, write to the Free Software
14 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
15 */
16
17/*
18 *    DotParser.java
19 *    Copyright (C) 2003 University of Waikato, Hamilton, New Zealand
20 *
21 */
22package weka.gui.graphvisualizer;
23
24import java.io.Reader;
25import java.io.StreamTokenizer;
26import java.io.BufferedReader;
27import java.io.IOException;
28import java.io.FileWriter;
29
30import weka.core.FastVector;
31import weka.gui.graphvisualizer.GraphNode;
32import weka.gui.graphvisualizer.GraphEdge;
33
34
35
36/**
37 * This class parses input in DOT format, and
38 * builds the datastructures that are passed to it.
39 * It is NOT 100% compatible with the DOT format. The
40 * GraphNode and GraphEdge classes do not have any provision
41 * for dealing with different colours or  shapes of nodes,
42 * there can however, be a different label and ID for a
43 * node. It  also does not do anything for labels for
44 * edges. However, this class won't crash or throw an
45 * exception if it encounters any of the above
46 * attributes of an edge or a node. This class however,
47 * won't be able to deal with things like subgraphs and
48 * grouping of nodes.
49 *
50 * @author Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)
51 * @version $Revision: 1.4 $ - 23 Apr 2003 - Initial version (Ashraf M. Kibriya)
52 */
53public class DotParser implements GraphConstants  {
54 
55  /** These holds the nodes and edges of the graph */
56  protected FastVector m_nodes, m_edges;
57  /** This is the input containing DOT stream  to be parsed */
58  protected Reader m_input;
59  /**  This holds the name of the graph if there is any otherwise it is null */
60  protected String m_graphName;
61 
62  /**
63   *
64   *  Dot parser Constructor
65   *
66   * @param input - The input, if passing in a string then
67   *                encapsulate that in String reader object
68   * @param nodes - Vector to put in GraphNode objects,
69   *                corresponding to the nodes parsed in from
70   *                the input
71   * @param edges - Vector to put in GraphEdge objects,
72   *                corresponding to the edges parsed in from
73   *                the input
74   */
75  public DotParser(Reader input, FastVector nodes, FastVector edges) {
76    m_nodes = nodes; m_edges = edges;
77    m_input = input;
78  }
79 
80 
81  /**
82   * This method parses the string or the InputStream that we
83   * passed in through the constructor and builds up the
84   * m_nodes and m_edges vectors
85   *
86   * @return - returns the name of the graph
87   */
88  public String parse() {
89    StreamTokenizer tk = new StreamTokenizer(new BufferedReader(m_input));
90    setSyntax(tk);
91   
92    graph(tk);
93   
94    return m_graphName;
95  }
96 
97 
98  /**
99   * This method sets the syntax of the StreamTokenizer.
100   * i.e. set the whitespace, comment and delimit chars.
101   *
102   */
103  protected void setSyntax(StreamTokenizer tk) {
104    tk.resetSyntax();
105    tk.eolIsSignificant(false);
106    tk.slashStarComments(true);
107    tk.slashSlashComments(true);
108    tk.whitespaceChars(0,' ');
109    tk.wordChars(' '+1,'\u00ff');
110    tk.ordinaryChar('[');
111    tk.ordinaryChar(']');
112    tk.ordinaryChar('{');
113    tk.ordinaryChar('}');
114    tk.ordinaryChar('-');
115    tk.ordinaryChar('>');
116    tk.ordinaryChar('/');
117    tk.ordinaryChar('*');
118    tk.quoteChar('"');
119    tk.whitespaceChars(';',';');
120    tk.ordinaryChar('=');
121  }
122 
123  /*************************************************************
124   *
125   * Following methods parse the DOT input and mimic the DOT
126   * language's grammar in their structure
127   *
128   *************************************************************
129   */
130  protected void graph(StreamTokenizer tk) {
131    try {
132      tk.nextToken();
133     
134      if(tk.ttype==tk.TT_WORD) {
135        if(tk.sval.equalsIgnoreCase("digraph")) {
136          tk.nextToken();
137          if(tk.ttype==tk.TT_WORD) {
138            m_graphName = tk.sval;
139            tk.nextToken();
140          }
141         
142          while(tk.ttype!='{') {
143            System.err.println("Error at line "+tk.lineno()+" ignoring token "+
144            tk.sval);
145            tk.nextToken();
146            if(tk.ttype==tk.TT_EOF)
147              return;
148          }
149          stmtList(tk);
150        }
151        else if(tk.sval.equalsIgnoreCase("graph"))
152          System.err.println("Error. Undirected graphs cannot be used");
153        else
154          System.err.println("Error. Expected graph or digraph at line "+
155          tk.lineno());
156      }
157    }
158    catch(Exception ex) { ex.printStackTrace(); }
159   
160   
161    //int tmpMatrix[][] = new int[m_nodes.size()][m_nodes.size()];
162    //for(int i=0; i<m_edges.size(); i++)
163    //    tmpMatrix[((GraphEdge)m_edges.elementAt(i)).src]
164    //       [((GraphEdge)m_edges.elementAt(i)).dest] =
165    //                                   ((GraphEdge)m_edges.elementAt(i)).type;
166    //for(int i=0; i<m_nodes.size(); i++) {
167    //    GraphNode n = (GraphNode)m_nodes.elementAt(i);
168    //    n.edges = tmpMatrix[i];
169    //}
170   
171    //Adding parents, and those edges to a node which are coming out from it
172    int tmpEdges[], noOfEdgesOfNode[]=new int[m_nodes.size()];
173    int noOfPrntsOfNode[]=new int[m_nodes.size()];
174    for(int i=0; i<m_edges.size(); i++) {
175      GraphEdge e = (GraphEdge)m_edges.elementAt(i);
176      noOfEdgesOfNode[e.src]++;
177      noOfPrntsOfNode[e.dest]++;
178    }
179    for(int i=0; i<m_edges.size(); i++) {
180      GraphEdge e  = (GraphEdge)m_edges.elementAt(i);
181      GraphNode n  = (GraphNode)m_nodes.elementAt(e.src);
182      GraphNode n2 = (GraphNode)m_nodes.elementAt(e.dest);
183      if(n.edges==null) {
184        n.edges = new int[noOfEdgesOfNode[e.src]][2];
185        for(int k=0; k<n.edges.length; k++)
186          n.edges[k][1]=0;
187      }
188      if(n2.prnts==null) {
189        n2.prnts = new int[noOfPrntsOfNode[e.dest]];
190        for(int k=0; k<n2.prnts.length; k++)
191          n2.prnts[k]=-1;
192      }
193      int k=0;
194      while(n.edges[k][1]!=0) k++;
195      n.edges[k][0] = e.dest;
196      n.edges[k][1] = e.type;
197     
198      k=0;
199      while(n2.prnts[k]!=-1) k++;
200      n2.prnts[k] = e.src;
201    }
202  }
203 
204 
205  protected void stmtList(StreamTokenizer tk) throws Exception{
206    tk.nextToken();
207    if(tk.ttype=='}' || tk.ttype==tk.TT_EOF)
208      return;
209    else {
210      stmt(tk);
211      stmtList(tk);
212    }
213  }
214 
215 
216  protected void stmt(StreamTokenizer tk) {
217    //tk.nextToken();
218   
219    if(tk.sval.equalsIgnoreCase("graph") || tk.sval.equalsIgnoreCase("node") ||
220    tk.sval.equalsIgnoreCase("edge") )
221      ; //attribStmt(k);
222    else {
223      try {
224        nodeID(tk);
225        int nodeindex= m_nodes.indexOf(new GraphNode(tk.sval, null));
226        tk.nextToken();
227       
228        if(tk.ttype == '[')
229          nodeStmt(tk, nodeindex);
230        else if(tk.ttype == '-')
231          edgeStmt(tk, nodeindex);
232        else
233          System.err.println("error at lineno "+tk.lineno()+" in stmt");
234      }
235      catch(Exception ex) {
236        System.err.println("error at lineno "+tk.lineno()+" in stmtException");
237        ex.printStackTrace();
238      }
239    }
240  }
241 
242 
243  protected void nodeID(StreamTokenizer tk) throws Exception{
244   
245    if(tk.ttype=='"' || tk.ttype==tk.TT_WORD || (tk.ttype>='a' && tk.ttype<='z')
246    || (tk.ttype>='A' && tk.ttype<='Z')) {
247      if(m_nodes!=null && !(m_nodes.contains( new GraphNode(tk.sval, null))) ) {
248        m_nodes.addElement( new GraphNode(tk.sval, tk.sval) );
249        //System.out.println("Added node >"+tk.sval+"<");
250      }
251    }
252    else
253    { throw new Exception(); }
254   
255    //tk.nextToken();
256  }
257 
258 
259  protected void nodeStmt(StreamTokenizer tk, final int nindex)
260  throws Exception {
261    tk.nextToken();
262   
263    GraphNode temp = (GraphNode) m_nodes.elementAt(nindex);
264   
265    if(tk.ttype==']' || tk.ttype==tk.TT_EOF)
266      return;
267    else if(tk.ttype==tk.TT_WORD) {
268     
269      if(tk.sval.equalsIgnoreCase("label")) {
270       
271        tk.nextToken();
272        if(tk.ttype=='=') {
273          tk.nextToken();
274          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
275            temp.lbl = tk.sval;
276          else {
277            System.err.println("couldn't find label at line "+tk.lineno());
278            tk.pushBack();
279          }
280        }
281        else {
282          System.err.println("couldn't find label at line "+tk.lineno());
283          tk.pushBack();
284        }
285      }
286     
287      else if(tk.sval.equalsIgnoreCase("color")){
288       
289        tk.nextToken();
290        if(tk.ttype=='=') {
291          tk.nextToken();
292          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
293            ;
294          else {
295            System.err.println("couldn't find color at line "+tk.lineno());
296            tk.pushBack();
297          }
298        }
299        else {
300          System.err.println("couldn't find color at line "+tk.lineno());
301          tk.pushBack();
302        }
303      }
304     
305      else if(tk.sval.equalsIgnoreCase("style")) {
306       
307        tk.nextToken();
308        if(tk.ttype=='=') {
309          tk.nextToken();
310          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
311            ;
312          else {
313            System.err.println("couldn't find style at line "+tk.lineno());
314            tk.pushBack();
315          }
316        }
317        else {
318          System.err.println("couldn't find style at line "+tk.lineno());
319          tk.pushBack();
320        }
321      }
322    }
323    nodeStmt(tk, nindex);
324  }
325 
326 
327  protected void edgeStmt(StreamTokenizer tk, final int nindex)
328  throws Exception {
329    tk.nextToken();
330   
331    GraphEdge e=null;
332    if(tk.ttype=='>') {
333      tk.nextToken();
334      if(tk.ttype=='{') {
335        while(true) {
336          tk.nextToken();
337          if(tk.ttype=='}')
338            break;
339          else {
340            nodeID(tk);
341            e = new GraphEdge(nindex,
342            m_nodes.indexOf( new GraphNode(tk.sval, null) ),
343            DIRECTED);
344            if( m_edges!=null && !(m_edges.contains(e)) ) {
345              m_edges.addElement( e );
346              //System.out.println("Added edge from "+
347              //                  ((GraphNode)(m_nodes.elementAt(nindex))).ID+
348              //                  " to "+
349              //                ((GraphNode)(m_nodes.elementAt(e.dest))).ID);
350            }
351          }
352        }
353      }
354      else {
355        nodeID(tk);
356        e = new GraphEdge(nindex,
357        m_nodes.indexOf( new GraphNode(tk.sval, null) ),
358        DIRECTED);
359        if( m_edges!=null && !(m_edges.contains(e)) ) {
360          m_edges.addElement( e );
361          //System.out.println("Added edge from "+
362          //                 ((GraphNode)(m_nodes.elementAt(nindex))).ID+" to "+
363          //                 ((GraphNode)(m_nodes.elementAt(e.dest))).ID);
364        }
365      }
366    }
367    else if(tk.ttype=='-') {
368      System.err.println("Error at line "+tk.lineno()+
369      ". Cannot deal with undirected edges");
370      if(tk.ttype==tk.TT_WORD)
371        tk.pushBack();
372      return;
373    }
374    else {
375      System.err.println("Error at line "+tk.lineno()+" in edgeStmt");
376      if(tk.ttype==tk.TT_WORD)
377        tk.pushBack();
378      return;
379    }
380   
381    tk.nextToken();
382   
383    if(tk.ttype=='[')
384      edgeAttrib(tk, e);
385    else
386      tk.pushBack();
387  }
388 
389 
390  protected void edgeAttrib(StreamTokenizer tk, final GraphEdge e)
391  throws Exception {
392    tk.nextToken();
393   
394    if(tk.ttype==']' || tk.ttype==tk.TT_EOF)
395      return;
396    else if(tk.ttype==tk.TT_WORD) {
397     
398      if(tk.sval.equalsIgnoreCase("label")) {
399       
400        tk.nextToken();
401        if(tk.ttype=='=') {
402          tk.nextToken();
403          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
404            System.err.println("found label "+tk.sval);//e.lbl = tk.sval;
405          else {
406            System.err.println("couldn't find label at line "+tk.lineno());
407            tk.pushBack();
408          }
409        }
410        else {
411          System.err.println("couldn't find label at line "+tk.lineno());
412          tk.pushBack();
413        }
414      }
415      else if(tk.sval.equalsIgnoreCase("color")) {
416       
417        tk.nextToken();
418        if(tk.ttype=='=') {
419          tk.nextToken();
420          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
421            ;
422          else {
423            System.err.println("couldn't find color at line "+tk.lineno());
424            tk.pushBack();
425          }
426        }
427        else {
428          System.err.println("couldn't find color at line "+tk.lineno());
429          tk.pushBack();
430        }
431      }
432     
433      else if(tk.sval.equalsIgnoreCase("style")) {
434       
435        tk.nextToken();
436        if(tk.ttype=='=') {
437          tk.nextToken();
438          if(tk.ttype==tk.TT_WORD || tk.ttype=='"')
439            ;
440          else {
441            System.err.println("couldn't find style at line "+tk.lineno());
442            tk.pushBack();
443          }
444        }
445        else {
446          System.err.println("couldn't find style at line "+tk.lineno());
447          tk.pushBack();
448        }
449      }
450    }
451    edgeAttrib(tk, e);
452  }
453 
454 
455  /**
456   *
457   * This method saves a graph in a file in DOT format.
458   * However, if reloaded in GraphVisualizer we would need
459   * to layout the graph again.
460   *
461   * @param filename  - The name of the file to write in. (will overwrite)
462   * @param graphName - The name of the graph
463   * @param nodes     - Vector containing all the nodes
464   * @param edges     - Vector containing all the edges
465   */
466  public static void writeDOT(String filename, String graphName,
467  FastVector nodes, FastVector edges) {
468    try {
469      FileWriter os = new FileWriter(filename);
470      os.write("digraph ", 0, ("digraph ").length());
471      if(graphName!=null)
472        os.write(graphName+" ", 0, graphName.length()+1);
473      os.write("{\n", 0, ("{\n").length());
474     
475      GraphEdge e;
476      for(int i=0; i<edges.size(); i++) {
477        e = (GraphEdge) edges.elementAt(i);
478        os.write(((GraphNode)nodes.elementAt(e.src)).ID, 0,
479        ((GraphNode)nodes.elementAt(e.src)).ID.length());
480        os.write("->", 0, ("->").length() );
481        os.write(((GraphNode)nodes.elementAt(e.dest)).ID+"\n",
482        0,
483        ((GraphNode)nodes.elementAt(e.dest)).ID.length()+1);
484      }
485      os.write("}\n", 0, ("}\n").length());
486      os.close();
487    }
488    catch(IOException ex) { ex.printStackTrace(); }
489  }
490 
491} // DotParser
Note: See TracBrowser for help on using the repository browser.