← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/gui/graphvisualizer/DotParser.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/gui/graphvisualizer/DotParser.java
 
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
 */
 
22
package weka.gui.graphvisualizer;
 
23
 
 
24
import java.io.Reader;
 
25
import java.io.StreamTokenizer;
 
26
import java.io.BufferedReader;
 
27
import java.io.IOException;
 
28
import java.io.FileWriter;
 
29
 
 
30
import weka.core.FastVector;
 
31
import weka.gui.graphvisualizer.GraphNode;
 
32
import 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
 */
 
53
public 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