Source code: com/port80/graph/dot/impl/Dot.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 /*
6 * This software may only be used by you under license from AT&T Corp.
7 * ("AT&T"). A copy of AT&T's Source Code Agreement is available at
8 * AT&T's Internet website having the URL:
9 * <http://www.research.att.com/sw/tools/graphviz/license/source.html>
10 * If you received this software without first entering into a license
11 * with AT&T, you have an infringing copy of this software and cannot use
12 * it without violating AT&T's intellectual property rights.
13 */
14
15 /**
16 * Graph layout package derived from the C version of Graphviz 1.7.17.
17 *
18 * The algorithm used in dot operate in a number of passes:
19 * . ranking - rank groups according to parent-child relationship.
20 * . mincross - shuffle vertex in same rank to minimize crossing.
21 * . position - determine the vertex position.
22 * . anneal - reroute with shortest path algorithm.
23 * . route - route connections.
24 *
25 * . Subgraphs are logical group of vertices that shares some common
26 * attributes. Vertics can be shared among subgraphs.
27 *
28 * . Clusters are physical group that should keep together as a group
29 * and vertices in clusters are mutually exclusive.
30 *
31 */
32 package com.port80.graph.dot.impl;
33
34 import java.awt.Graphics2D;
35 import java.awt.image.BufferedImage;
36 import java.io.File;
37 import java.io.FileInputStream;
38 import java.io.FileNotFoundException;
39 import java.io.InputStream;
40 import java.util.HashMap;
41 import java.util.Map;
42
43 import javax.imageio.ImageIO;
44 import javax.imageio.ImageWriter;
45 import javax.imageio.stream.FileImageOutputStream;
46
47 import com.port80.graph.IGraph;
48 import com.port80.graph.IVertex;
49 import com.port80.graph.dot.parser.DotParser;
50 import com.port80.graph.impl.DirectedGraphRenderer;
51 import com.port80.graph.impl.GraphPanel;
52 import com.port80.graph.impl.ToDotVisitor;
53 import com.port80.util.Debug;
54 import com.port80.util.PseudoRandom;
55 import com.port80.util.SystemWatch;
56 import com.port80.util.msg;
57 import com.port80.util.sprint;
58
59 /** Graph layout.
60 */
61 public class Dot {
62
63 // Static fields ///////////////////////////////////////////////////////
64 //
65
66 private static final String NAME = "Dot";
67 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
68 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
69 private static final int VERSION = 0x0101;
70 private static final String VERSIONNAME = "$Revision: 1.37 $";
71 private static final String USAGE = "java " + NAME + " [-options] <dotfile>\n";
72 private static boolean DEBUG = false;
73 public static boolean VERBOSE = false;
74 static {
75 Debug.add(CLASSNAME);
76 }
77
78 private static final int MAXUNTANGLE = 5;
79 private static final int MAXANNEAL = 5;
80
81 private static Map opt = new HashMap();
82
83 // Instance fields /////////////////////////////////////////////////////
84 //
85
86 BufferedImage bimg;
87 Graphics2D g2d;
88 DirectedGraphRenderer renderer;
89
90 // Static methods //////////////////////////////////////////////////////
91 //
92
93 public static IGraph dot(IGraph g) {
94 return new Dot().layout(g, 0, 2);
95 }
96
97 public static IGraph dot(IGraph g, int seed, int passes) {
98 return new Dot().layout(g, seed, passes);
99 }
100
101 public static IGraph dot(IGraph g, IVertex v) {
102 return new Dot().route(g, v, 0);
103 }
104
105 // Constructors ////////////////////////////////////////////////////////
106 //
107
108 public Dot() {
109 bimg = new BufferedImage(10, 10, BufferedImage.TYPE_BYTE_GRAY);
110 g2d = (Graphics2D) bimg.getGraphics();
111 renderer = new DirectedGraphRenderer();
112 }
113
114 public Dot(Map options) {
115 this();
116 // Configure layout and graph options.
117 }
118
119 // test main ///////////////////////////////////////////////////////////
120 //
121
122 public static void main(String[] args) {
123
124 if (args.length == 0)
125 msg.usage(USAGE);
126 String[] cmdArgs =
127 msg.getArgs(
128 opt,
129 NAME,
130 args,
131 " help=h verbose=v check debug dump seed: save: scale: passes: cell");
132
133 if (opt.get("help") != null)
134 msg.usage(USAGE);
135 if (opt.get("debug") != null) {
136 DEBUG = true;
137 Debug.enable("debug,test,trace");
138 Debug.enable(".*");
139 }
140 if (opt.get("check") != null) {
141 Debug.enable("check");
142 }
143 if (opt.get("verbose") != null) {
144 VERBOSE = true;
145 Debug.enable("verbose");
146 }
147
148 if (VERBOSE)
149 msg.println("### " + cmdArgs.length + " files ...");
150
151 ////////////////////////////////////////
152
153 Dot app = new Dot();
154 int seed = 0;
155 if (opt.get("seed") != null) {
156 String str = (String) opt.get("seed");
157 if (str.length() > 0)
158 seed = msg.parseInt(str, 0);
159 }
160 for (int ai = 0; ai < cmdArgs.length; ai++) {
161 DotParser parser = parseFile(cmdArgs[ai]);
162 IGraph g = parser.getGraph();
163 if (opt.get("dump") != null)
164 msg.println(ToDotVisitor.sprint(parser.getGraph(), ""));
165 app.layout(g, seed, msg.getOptInt(opt, "passes", 2));
166 //
167 String fname = msg.getOptString(opt, "save");
168 if (fname != null) {
169 GraphPanel gpanel = new GraphPanel(g, msg.getOptFloat(opt, "scale", 1f));
170 BufferedImage buf = gpanel.getImage();
171 TestUtil.saveImage(buf, fname);
172 if (true)
173 msg.println("Saved: " + fname + ".png");
174 }
175 }
176 }
177
178 public void updateShape(IGraph g) {
179 // Determine label sizes.
180 // A temp. image is to get a Graphics2D for font info and text layout.
181 renderer.updateShape(g2d, g);
182 }
183
184 public static void setVerbose(boolean verbose) {
185 VERBOSE = verbose;
186 }
187
188 public static DotParser parseFile(String fpath) {
189 DotParser parser = null;
190 InputStream input;
191 fpath = msg.normalizeFilePath(fpath);
192 SystemWatch timer1 = new SystemWatch();
193 try {
194 input = new FileInputStream(fpath);
195 timer1.start();
196 parser = new DotParser(input, fpath).parse();
197 } catch (FileNotFoundException e) {
198 msg.err("File " + fpath + " not found.");
199 } catch (Exception e) {
200 String m = (parser != null) ? parser.getLineno() : "";
201 msg.err(m, e);
202 }
203 if (parser == null)
204 return null;
205
206 timer1.stop();
207 int lines = parser.getTotalLines();
208 String name = msg.fileName(fpath);
209 if (VERBOSE)
210 msg.println(
211 sprint
212 .f(" * %-32s: %6d lines in %8.2f (sec)=%8.2f (lines/sec), used/total size=%.1f/%.1f (M)")
213 .a(name)
214 .a(lines)
215 .a(timer1.elapsed())
216 .a(lines / timer1.elapsed())
217 .a(timer1.size() / 1e6)
218 .a(timer1.totalSize() / 1e6f)
219 .end());
220 return parser;
221 }
222
223 // Instance methods ////////////////////////////////////////////////////
224 //
225
226 /** Layout a complete graph.
227 *
228 * @require Annotated Vertex shape "-shape" (dimensions).
229 */
230 public IGraph layout(IGraph g, int seed, int passes) {
231 SystemWatch timer = null;
232 if (true)
233 timer = new SystemWatch().start();
234 if (VERBOSE) {
235 msg.println(
236 NAME
237 + ".layout(): allVertices="
238 + g.allVertices().size()
239 + ", topVertices="
240 + g.getVertexSet().size());
241 }
242 // Remove any existing layout information.
243 g.clearLayout();
244 // Init. vertex dimension.
245 if (seed > 0)
246 g.setAttr("seed", PseudoRandom.getTableID(seed));
247 updateShape(g);
248 DotGraph dotgraph = new DotGraph(g);
249 //msg.println(dotgraph.toString());
250 //
251 // Ranking.
252 //
253 NetworkSimplex.dotRank(dotgraph, g.getAttrDouble("nslimit", 1.0), true);
254 dotgraph.saveRanks();
255 if (DEBUG)
256 msg.println(dotgraph.sprintRankDebugGraph());
257
258 // MinCross.
259 //
260 VirtualGraph vgraph = new VirtualGraph(g);
261 if (seed < 0) {
262 int bestcost = Integer.MAX_VALUE;
263 int bestseed = 0;
264 int cost;
265 for (int i = 0; i < -seed; ++i) {
266 cost = MinCross.dot(vgraph, 0, 6, i);
267 if (cost < bestcost) {
268 bestcost = cost;
269 bestseed = i;
270 }
271 if (bestcost == 0)
272 break;
273 }
274 seed = bestseed;
275 }
276 if (VERBOSE)
277 msg.println(NAME + ".layout(): seed=" + seed);
278 MinCross.dot(vgraph, 0, 6, seed);
279 vgraph.removeAux();
280 MinCross.dot(vgraph, 2, 6, seed);
281
282 // Untangle takes 25sec. Although do not solve problem of
283 // excessive long routes due to avoiding of crossings, this
284 // remove most uneccessary crossings that make the output
285 // drawing ugly. And this don't need the second pass
286 // Position(). However, this do not solve the problem that
287 // Position() would be non-crossed edges into long twisted
288 // routes. So Anneal() is much better.
289 //
290 //Untangle.dot(vgraph,MAXUNTANGLE);
291 //MinCross.dot(vgraph,0,6,seed);
292
293 // Obsolete. Add auxillary spacing vertex between vertices for
294 // MinCross to reorder bus vertices. Not much improvement.
295 //
296 //vgraph.insertAux();
297 //vgraph.resetCost();
298 //MinCross.dot(vgraph,2,2);
299 //vgraph.removeAux();
300
301 if (false)
302 vgraph.plotMinCross();
303 int bestcost = Position.dotPosition(vgraph);
304 //
305 // Two pass Anneal/Position. Additional pass here doesn't
306 // help much for testdot00.
307 //
308 //Anneal.dot(vgraph,2);
309 //Position.dotPosition(vgraph);
310
311 if (passes > 0) {
312 while (--passes > 0) {
313 if (opt.get("cell") != null)
314 AnnealWithCell.dot(vgraph, MAXANNEAL);
315 else
316 Anneal.dot(vgraph, 2, MAXANNEAL);
317 Position.dotPosition(vgraph);
318 }
319 } else {
320 int cost;
321 int maxiter = Math.min(-passes, 20);
322 for (int iter = 1; iter <= maxiter && bestcost > 0; ++iter) {
323 if (opt.get("cell") != null)
324 AnnealWithCell.dot(vgraph, MAXANNEAL);
325 else
326 Anneal.dot(vgraph, 2, MAXANNEAL);
327 vgraph.sanityCheck();
328 MinCross.dot(vgraph, 2, 6, seed);
329 cost = Position.dotPosition(vgraph);
330 if (VERBOSE)
331 msg.println(
332 "\n###\n### "
333 + NAME
334 + ".dot(): pass="
335 + iter
336 + ", cost="
337 + cost
338 + "\n###");
339 if (iter < maxiter / 2)
340 continue;
341 if (cost < bestcost) {
342 bestcost = cost;
343 continue;
344 } else if (cost == bestcost) {
345 break;
346 } else {
347 if (iter != maxiter)
348 iter = maxiter - 1;
349 }
350 }
351 }
352 if (false) {
353 if (false)
354 AnnealWithCell.dot(vgraph, MAXANNEAL);
355 if (passes > 1 && opt.get("cell") == null)
356 Anneal.dot(vgraph, 1, MAXANNEAL);
357 }
358
359 // testdot00 result cost=71467 with(Anneal and 2-pass Position, DISTFACTOR=4).
360 // testdotciv result cost=24423 with(as above).
361 Position.saveResult(vgraph);
362 if (false)
363 Position.printPositionGraph(vgraph);
364
365 // Update vertex shape origin.
366 //
367 updateShape(g);
368 Route.dot(vgraph);
369 if (VERBOSE)
370 msg.outln(g.sprintGraph());
371 if (true)
372 msg.println(timer.stop().toString());
373 return g;
374 }
375
376 public IGraph route(IGraph g, IVertex v, int seed) {
377 return g;
378 }
379
380 ////////////////////////////////////////////////////////////////////////
381
382 }