Source code: com/port80/graph/impl/DirectedGraph.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.impl;
6
7 import java.awt.Rectangle;
8 import java.awt.image.BufferedImage;
9 import java.io.File;
10 import java.util.ArrayList;
11 import java.util.Collection;
12 import java.util.Comparator;
13 import java.util.HashMap;
14 import java.util.HashSet;
15 import java.util.Iterator;
16 import java.util.List;
17 import java.util.Map;
18 import java.util.Set;
19 import java.util.TreeSet;
20
21 import javax.imageio.ImageIO;
22 import javax.imageio.ImageWriter;
23 import javax.imageio.stream.FileImageOutputStream;
24
25 import com.port80.graph.GraphException;
26 import com.port80.graph.IEdge;
27 import com.port80.graph.IEdgeFactory;
28 import com.port80.graph.IGraph;
29 import com.port80.graph.IVertex;
30 import com.port80.graph.IVertexFactory;
31 import com.port80.graph.dot.impl.RouteFactory;
32 import com.port80.util.Debug;
33 import com.port80.util.msg;
34 import com.port80.util.attr.AttrTable;
35 import com.port80.util.attr.IAttrTable;
36 import com.port80.util.attr.PointFactory;
37
38 /** Basic directed graph class.
39 *
40 * @see com.port80.graph.IGraph
41 */
42 public class DirectedGraph extends GraphElement implements IGraph {
43
44 // Static fields ///////////////////////////////////////////////////////
45 //
46
47 private static final String NAME = "DirectedGraph";
48 private static final String PACKAGENAME = "com.port80.graph.impl";
49 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
50 private static final int VERSION = 0x0101;
51 private static final String VERSIONNAME = "v0.1";
52 static {
53 Debug.add(CLASSNAME);
54 }
55 private static boolean DEBUG = false;
56 private static boolean VERBOSE = true;
57
58 // Nested classes //////////////////////////////////////////////////////
59 //
60
61 public static class NameComparator implements Comparator {
62 public int compare(Object a, Object b) {
63 String namea = ((DirectedGraph) a).getName();
64 if (namea == null)
65 return -1;
66 String nameb = ((DirectedGraph) b).getName();
67 if (nameb == null)
68 return 1;
69 return namea.compareTo(nameb);
70 }
71 }
72
73 // Instance fields /////////////////////////////////////////////////////
74 //
75
76 /**
77 * Vertex factory create vertices for the graph and holds the default attribute values.
78 */
79 private IVertexFactory fVertexFactory;
80 /**
81 * Vertex factory create edges for the graph and holds the default attribute values.
82 */
83 private IEdgeFactory fEdgeFactory;
84
85 /**
86 * Graph wide vertex attribute table to store customized attributes
87 * that applies to all vertices in the graph.
88 */
89 private IAttrTable fVertexAttrTable;
90 /**
91 * Graph wide edge attribute table to store customized attributes
92 * that applies to all edges in the graph.
93 */
94 private IAttrTable fEdgeAttrTable;
95 //
96 private IGraph fParent;
97 private boolean fIsCluster = false;
98 protected Map fVertexTable = new HashMap();
99 protected Set fEdgeSet = new HashSet();
100 protected List fSubGraphList = new ArrayList(3);
101
102 // Constructors ////////////////////////////////////////////////////////
103 //
104
105 public DirectedGraph(String name, Object data, IGraph parent) {
106 super((parent != null) ? (IAttrTable) parent : (IAttrTable) DefaultGraphAttrTable.getInstance());
107 this.fName = name;
108 this.fData = data;
109 this.fParent = parent;
110 if (parent == null) {
111 fVertexFactory = new DirectedVertexFactory();
112 fEdgeFactory = new DirectedEdgeFactory();
113 fVertexAttrTable = new AttrTable(fVertexFactory);
114 fEdgeAttrTable = new AttrTable(fEdgeFactory);
115 } else {
116 if (name != null && name.startsWith("cluster_"))
117 fIsCluster = true;
118 parent.getSubGraphs().add(this);
119 fVertexFactory = parent.getVertexFactory();
120 fEdgeFactory = parent.getEdgeFactory();
121 fVertexAttrTable = new AttrTable(parent.getVertexAttrTable());
122 fEdgeAttrTable = new AttrTable(parent.getEdgeAttrTable());
123 }
124 }
125
126 // Instance methods ////////////////////////////////////////////////////
127 //
128
129 public boolean isCluster() {
130 return fIsCluster;
131 }
132 public String toString() {
133 return NAME + ": " + fName;
134 }
135
136 public IGraph newGraph(String name, Object data) {
137 return new DirectedGraph(name, data, this);
138 }
139
140 public IVertex newVertex(String name, Object data) throws GraphException {
141 IVertex ret = fVertexFactory.newVertex(name, data, this);
142 addVertex(ret);
143 return ret;
144 }
145
146 public IVertex newVertex(String name, String port, Object data) throws GraphException {
147 IVertex ret = fVertexFactory.newVertex(name, port, data, this);
148 addVertex(ret);
149 return ret;
150 }
151
152 public IEdge newEdge(IVertex tail, IVertex head, String ename, Object data) throws GraphException {
153 IEdge e = fEdgeFactory.newEdge(tail, head, ename, data, this);
154 head.addIn(e);
155 tail.addOut(e);
156 fEdgeSet.add(e);
157 return e;
158 }
159
160 public boolean removeEdge(IEdge e) {
161 boolean ret = true;
162 if (!e.getHead().removeIn(e)) {
163 ret = false;
164 msg.err("Edge not in IN edge list of its head: e=" + e);
165 }
166 if (!e.getTail().removeOut(e)) {
167 ret = false;
168 msg.err("Edge not in OUT edge list of its tail: e=" + e);
169 }
170 ret = ret && fEdgeSet.remove(e);
171 return ret;
172 }
173
174 public boolean isValid(IVertex head, IVertex tail) {
175 return true;
176 }
177
178 public boolean canDelete(IEdge e) {
179 return true;
180 }
181
182 // IGraph interface ////////////////////////////////////////////////////
183 //
184
185 public IVertexFactory getVertexFactory() {
186 return fVertexFactory;
187 }
188 public IEdgeFactory getEdgeFactory() {
189 return fEdgeFactory;
190 }
191 public IAttrTable getVertexAttrTable() {
192 return fVertexAttrTable;
193 }
194 public IAttrTable getEdgeAttrTable() {
195 return fEdgeAttrTable;
196 }
197
198 public String getGraphTypeName() {
199 return "digraph";
200 }
201 public IGraph getParent() {
202 return fParent;
203 }
204
205 /*
206 public void setParent(IGraph parent) {this.parent=parent;}
207 */
208 public boolean containsVertex(String vname) {
209 if (fVertexTable.containsKey(vname))
210 return true;
211 for (int i = 0; i < fSubGraphList.size(); ++i) {
212 if (((IGraph) fSubGraphList.get(i)).containsVertex(vname))
213 return true;
214 }
215 return false;
216 }
217
218 public boolean containsVertex(IVertex v) {
219 return containsVertex(v.getName());
220 }
221
222 public IVertex getVertex(String vname) {
223 IVertex ret = (IVertex) fVertexTable.get(vname);
224 if (ret != null)
225 return ret;
226 for (int i = 0; i < fSubGraphList.size(); ++i) {
227 ret = ((IGraph) fSubGraphList.get(i)).getVertex(vname);
228 if (ret != null)
229 return ret;
230 }
231 return null;
232 }
233
234 public IVertex getVertex(IVertex v) {
235 return getVertex(v.getName());
236 }
237
238 public Set getVertexNameSet() {
239 return fVertexTable.keySet();
240 }
241
242 /** @return Set of IVertex in the graph not include vertices in subgraphs.*/
243 public Set getVertexSet() {
244 return new HashSet(fVertexTable.values());
245 }
246 public Set getEdgeSet() {
247 return fEdgeSet;
248 }
249
250 public void addVertex(IVertex v) throws GraphException {
251 String vname = v.getName();
252 if (containsVertex(vname))
253 throw new GraphException("Duplicated vertex", getVertex(vname), v);
254 fVertexTable.put(vname, v);
255 }
256
257 /** Add a collection of IVertex. */
258 public void addAllVertex(Collection c) throws GraphException {
259 for (Iterator it = c.iterator(); it.hasNext();)
260 addVertex((IVertex) it.next());
261 }
262
263 /** Remove a vertex from the graph or its subgraph.
264 *
265 * @return null if vertex not under this graph, else vertex removed.
266 */
267 public IVertex removeVertex(String vname) {
268 IVertex v = (IVertex) fVertexTable.get(vname);
269 if (v != null) {
270 v.setParent(null);
271 return (IVertex) fVertexTable.remove(vname);
272 }
273 return null;
274 }
275
276 public IVertex removeVertex(IVertex v) {
277 return removeVertex(v.getName());
278 }
279
280 /** Remove a collection of IVertex. */
281 /*
282 public boolean removeAllVertex(Collection c) {
283 boolean ok=true;
284 for(Iterator it=c.iterator(); it.hasNext();) {
285 ok=ok&&(removeVertex((IVertex)it.next())!=null);
286 }
287 return ok;
288 }
289 public boolean clear() {
290 for(Iterator it=vertexTable.values().iterator(); it.hasNext();) {
291 if(removeVertex((IVertex)it.next())==null) return false;
292 }
293 for(int i=0; i<subGraphList.size(); ++i) {
294 if(!((IGraph)subGraphList.get(i)).clear()) return false;
295 }
296 return true;
297 }
298 */
299
300 public Set allVertexNameSet() {
301 Set ret = fVertexTable.keySet();
302 for (int i = 0; i < fSubGraphList.size(); ++i) {
303 ret.addAll(((IGraph) fSubGraphList.get(i)).allVertexNameSet());
304 }
305 return ret;
306 }
307
308 /** All vertices under this graph including those in all its nested
309 * subgraphs. */
310 public Set allVertices() {
311 Set ret = new HashSet(fVertexTable.values());
312 for (int i = 0; i < fSubGraphList.size(); ++i) {
313 ret.addAll(((IGraph) fSubGraphList.get(i)).allVertices());
314 }
315 return ret;
316 }
317
318 /** All edges under this graph including thos in all its nested
319 * subgraphs. */
320 public Set allEdges() {
321 Set ret = allEdges(allVertices(), new HashSet());
322 for (int i = 0; i < fSubGraphList.size(); ++i) {
323 IGraph g = (IGraph) fSubGraphList.get(i);
324 allEdges(g.allVertices(), ret);
325 }
326 return ret;
327 }
328
329 private Set allEdges(Set vset, Set ret) {
330 if (vset == null)
331 return ret;
332 IVertex v;
333 IEdge[] outs;
334 for (Iterator it = vset.iterator(); it.hasNext();) {
335 v = (IVertex) it.next();
336 outs = v.outs();
337 for (int i = 0; i < outs.length; ++i)
338 ret.add(outs[i]);
339 }
340 return ret;
341 }
342
343 public int size() {
344 int ret = fVertexTable.size();
345 for (int i = 0; i < fSubGraphList.size(); ++i) {
346 ret += ((IGraph) fSubGraphList.get(i)).size();
347 }
348 return ret;
349 }
350
351 /**
352 * Remove all layout attributes to prepare for new layout.
353 */
354 public void clearLayout() {
355 for (Iterator it = new HashSet(attrKeySet()).iterator(); it.hasNext();) {
356 String attr = (String) it.next();
357 if (attr.startsWith("-") || attr.equals("bb"))
358 removeAttr(attr);
359 }
360 Collection vertices = fVertexTable.values();
361 for (Iterator it = vertices.iterator(); it.hasNext();) {
362 IVertex v = (IVertex) it.next();
363 v.clearLayout();
364 }
365 for (int i = 0; i < fSubGraphList.size(); ++i) {
366 IGraph g = (IGraph) fSubGraphList.get(i);
367 g.clearLayout();
368 }
369 }
370
371 ////////////////////////////////////////////////////////////////////////
372
373 public boolean containsGraph(IGraph g) {
374 return getGraph(g) != null;
375 }
376
377 /*
378 public boolean addGraph(IGraph g) {
379 if(containsGraph(g)) return false;
380 subGraphList.add(g);
381 return true;
382 }
383
384 public boolean removeGraph(IGraph g) {
385 if(subGraphList.remove(g)) return true;
386 for(int i=0; i<subGraphList.size(); ++i) {
387 if(((IGraph)subGraphList.get(i)).removeGraph(g)) return true;
388 }
389 return false;
390 }
391 */
392
393 public IGraph getGraph(IGraph g) {
394 int index = fSubGraphList.indexOf(g);
395 if (index >= 0)
396 return g;
397 IGraph ret;
398 for (int i = 0; i < fSubGraphList.size(); ++i) {
399 ret = (IGraph) fSubGraphList.get(i);
400 ret = ret.getGraph(g);
401 if (ret != null)
402 return ret;
403 }
404 return null;
405 }
406
407 public List getSubGraphs() {
408 return fSubGraphList;
409 }
410
411 /** Find vertices with given attribute name.
412 *
413 * @return Set of IVertex that contains the given attribute name.
414 */
415 public Set findVerticesWithAttr(String attrname) {
416 Set ret = new HashSet();
417 IVertex v;
418 for (Iterator it = fVertexTable.values().iterator(); it.hasNext();) {
419 v = (IVertex) it.next();
420 if (v.hasAttr(attrname))
421 ret.add(v);
422 }
423 for (int i = 0; i < fSubGraphList.size(); ++i) {
424 ret.addAll(((IGraph) fSubGraphList.get(i)).findVerticesWithAttr(attrname));
425 }
426 return ret;
427 }
428
429 public Set findEdgesWithAttr(String attrname) {
430 Set ret = new HashSet();
431 IVertex v;
432 IEdge e;
433 IEdge[] outs;
434 for (Iterator it = fVertexTable.values().iterator(); it.hasNext();) {
435 v = (IVertex) it.next();
436 outs = v.outs();
437 for (int i = 0; i < outs.length; ++i) {
438 e = outs[i];
439 if (e.hasAttr(attrname))
440 ret.add(e);
441 }
442 }
443 for (int i = 0; i < fSubGraphList.size(); ++i) {
444 ret.addAll(((IGraph) fSubGraphList.get(i)).findEdgesWithAttr(attrname));
445 }
446 return ret;
447 }
448
449 ////////////////////////////////////////////////////////////////////////
450
451 public String sprintGraph() {
452 StringBuffer ret = new StringBuffer("digraph " + fName + " {\n");
453 IVertex v;
454 Set vts = allVertices();
455 // Make sure IEdge "-pos" attribute are populated before enabling DotMode.
456 for (Iterator it = vts.iterator(); it.hasNext();) {
457 v = (IVertex) it.next();
458 IEdge[] outs = v.outs();
459 for (int i = 0; i < outs.length; ++i) {
460 outs[i].getAttrCached("pos");
461 }
462 v.getAttrCached("frombus");
463 v.getAttrCached("tobus");
464 v.getAttrCached("inbus");
465 v.getAttrCached("outbus");
466 }
467 //
468 Rectangle bounds = (Rectangle) getAttr("bb");
469 if (bounds != null) {
470 RouteFactory.dotModeOn(bounds.height);
471 PointFactory.dotModeOn(bounds.height);
472 }
473 Set keys;
474 keys= attrKeySet();
475 //keys.remove("bb");
476 if (keys.size()>0) {
477 ret.append(" graph [\n");
478 printlnAttrs(ret, this, keys, " ");
479 ret.append(" ];\n");
480 }
481 //
482 IAttrTable table;
483 table = (IAttrTable) getVertexAttrTable();
484 keys = table.attrKeySet();
485 if (keys.size()>0) {
486 ret.append(" node [\n");
487 printlnAttrs(ret, table, keys, " ");
488 ret.append(" ];\n");
489 }
490 table = getEdgeAttrTable();
491 keys = table.attrKeySet();
492 if (keys.size()>0) {
493 ret.append(" edge [\n");
494 printlnAttrs(ret, table, keys, " ");
495 //printlnAttr(ret, table, "arrowsize", " ");
496 ret.append(" ];\n");
497 }
498 String s;
499 for (Iterator it = vts.iterator(); it.hasNext();) {
500 v = (IVertex) it.next();
501 s = v.getAttrString("label");
502 if (s == null)
503 s = v.getName();
504 s = msg.escString(s);
505 ret.append(" \"" + v.getName() + "\" [label=\"" + s + "\" ");
506 appendAttr(ret, v, "style");
507 appendAttr(ret, v, "color");
508 appendAttr(ret, v, "fillcolor");
509 appendAttr(ret, v, "pos");
510 appendAttr(ret, v, "-bounds");
511 appendAttr(ret, v, "-tobus", "tobus");
512 appendAttr(ret, v, "-frombus", "frombus");
513 appendAttr(ret, v, "-inbus", "inbus");
514 appendAttr(ret, v, "-outbus", "outbus");
515 ret.append("];\n");
516 }
517 ret.append("\n");
518 for (Iterator it = vts.iterator(); it.hasNext();) {
519 v = (IVertex) it.next();
520 IEdge[] outs = v.outs();
521 for (int i = 0; i < outs.length; ++i) {
522 sprintEdge(ret, outs[i]);
523 }
524 }
525 ret.append("}\n");
526 if (bounds != null) {
527 RouteFactory.dotModeOff();
528 PointFactory.dotModeOff();
529 }
530 return ret.toString();
531 }
532
533 private void sprintEdge(StringBuffer ret, IEdge e) {
534 IVertex head = e.getHead();
535 IVertex tail = e.getTail();
536 //}
537 ret.append(" \"" + tail.getName() + "\"->\"" + head.getName() + "\" [");
538 appendAttr(ret, e, "critical");
539 appendAttr(ret, e, "color");
540 appendAttr(ret, e, "style");
541 appendAttr(ret, e, "headarrow");
542 appendAttr(ret, e, "tailarrow");
543 appendAttr(ret, e, "arrowsize");
544 appendAttr(ret, e, "-pos");
545 if (e.getAttrBool("debug"))
546 ret.append(" debug=true");
547 ret.append("];\n");
548 }
549
550 private void appendAttr(StringBuffer ret, IAttrTable table, String name) {
551 String s = table.getAttrAsString(name);
552 if (s != null)
553 ret.append("\"" + name + "\"=\"" + s + "\" ");
554 }
555
556 private void appendAttr(StringBuffer ret, IAttrTable table, String attrname, String name) {
557 String s = table.getAttrAsString(attrname);
558 if (s != null)
559 ret.append("\"" + name + "\"=\"" + s + "\" ");
560 }
561
562 private void printlnAttr(StringBuffer buf, IAttrTable table, String name, String indent) {
563 String s = table.getAttrAsString(name);
564 buf.append(indent + "\"" + name + "\"=\"" + s + "\",\n");
565 }
566
567 private void printlnAttrs(StringBuffer buf, IAttrTable table, Set keys, String indent) {
568 String name, value;
569 for (Iterator it = new TreeSet(keys).iterator(); it.hasNext();) {
570 name = (String) it.next();
571 if (name.startsWith("-"))
572 continue;
573 value = table.getAttrAsString(name);
574 buf.append(indent + "\"" + name + "\"=\"" + value + "\",\n");
575 }
576 }
577
578 ////////////////////////////////////////////////////////////////////////
579
580 public boolean saveImage(String fname, float scale) {
581 GraphPanel gpanel = new GraphPanel(this, scale);
582 BufferedImage buf = gpanel.getImage();
583 try {
584 if (!fname.endsWith(".png"))
585 fname += ".png";
586 File ifile = msg.createFile(fname);
587 ImageWriter writer = (ImageWriter) ImageIO.getImageWritersByFormatName("png").next();
588 FileImageOutputStream of = new FileImageOutputStream(ifile);
589 writer.setOutput(of);
590 writer.write(buf);
591 of.close();
592 writer.dispose();
593 } catch (Exception e) {
594 msg.err(NAME + ".saveImage(): Can't open output file: " + fname, e);
595 return false;
596 }
597 if (VERBOSE)
598 msg.println(NAME + ".saveImage(): " + fname + " saved.");
599 return true;
600 }
601
602 // IGraphElement interface //////////////////////////////////////////////
603 //
604 public String getElementTypeName() {
605 return NAME;
606 }
607
608 // Helper methods //////////////////////////////////////////////////////
609 //
610
611 ////////////////////////////////////////////////////////////////////////
612
613 }