001 package nl.cwi.sen1.gui.plugin.prefusedot;
002
003 import java.awt.geom.Point2D;
004 import java.io.BufferedReader;
005 import java.io.IOException;
006 import java.io.InputStream;
007 import java.io.InputStreamReader;
008 import java.io.OutputStream;
009 import java.io.PrintStream;
010 import java.text.CharacterIterator;
011 import java.text.StringCharacterIterator;
012 import java.util.HashMap;
013 import java.util.Iterator;
014 import java.util.LinkedList;
015 import java.util.List;
016 import java.util.Map;
017 import java.util.regex.Matcher;
018 import java.util.regex.Pattern;
019
020 import prefuse.data.Edge;
021 import prefuse.data.Graph;
022 import prefuse.data.Node;
023
024 /**
025 * @author Jurgen Vinju
026 *
027 * This class wraps a prefuse Graph in order to provide a bridge to AT&T's
028 * graphviz. The idea is to build a graph via this interface and call the
029 * doDotLayout() method after constructing the graph in memory. This will start
030 * a session with the external dot tool via pipes, and annotate the graph with
031 * x,y position information, and store the locations for the curved edges also.
032 * @see nl.cwi.sen1.gui.plugin.prefusedot.DotNodeLayout for how this information will later be used to actually
033 * layout the graph.
034 */
035 public class DotAdapter extends Graph {
036 private static final int dpi = 72;
037
038 public static final String DOT_CURVE_POINTS = "curve-points";
039 public static final String DOT_X = "dotX";
040 public static final String DOT_Y = "dotY";
041 public static final String DOT_WIDTH = "dotWidth";
042 public static final String DOT_HEIGHT = "dotHeight";
043 public static final String DOT_LABEL = "label";
044 public static final String DOT_ID = "id";
045 public static final String DOT_SHAPE = "shape";
046
047 private double scale;
048
049 private Map<String, Node> nodeIds = new HashMap<String, Node>();
050
051 public DotAdapter() {
052 super(true);
053 addColumn(DOT_ID, String.class);
054 addColumn(DOT_LABEL, String.class);
055 addColumn(DOT_X, int.class);
056 addColumn(DOT_Y, int.class);
057 addColumn(DOT_CURVE_POINTS, Point2D[].class);
058 addColumn(DOT_WIDTH, int.class);
059 addColumn(DOT_HEIGHT, int.class);
060 addColumn(DOT_SHAPE, String.class);
061 }
062
063 /**
064 * Run the Dot layout algorithm and store the results as attributes in the graph
065 * table. These attributes can later be used by a prefuse layout algorithm.
066 * @see DotNodeLayout and @see DotLabelLayout for details. This method assumes
067 * you have added nodes and edges using the @method addNode() and @method addEdge() methods.
068 *
069 */
070 public void doDotLayout() {
071 executeDot();
072 }
073
074 private void executeDot() {
075 try {
076 String command = "dot -y -Tplain";
077 Process child = Runtime.getRuntime().exec(command);
078
079 OutputStream out = child.getOutputStream();
080 printDot(new PrintStream(out));
081 out.close();
082
083 InputStream in = child.getInputStream();
084 parseDot(in);
085 in.close();
086 } catch (IOException e) {
087 // TODO do something with this error
088 }
089 }
090
091 private Node getNode(String id) {
092 return nodeIds.get(id);
093 }
094
095 private void storeNode(String id, Node node) {
096 nodeIds.put(id, node);
097 }
098
099 /**
100 * This private class stores pre-compiled regular expressions for parsing
101 * the dot -Tplain output format.
102 */
103 private static class Patterns {
104 /*
105 * graph scale width height
106 * node name x y width height label style shape color fillcolor
107 * edge tail head n x1 y1 .. xn yn [label xl yl] style color
108 * stop
109 */
110 static final String id = "(\\w+|(?:\"(?:[^\\\"]|(?:\\\")|(?:\\\\))*\"))";
111 static final String w = "(\\S+)";
112 static final String d = "([0-9]+)";
113 static final String r = "([0-9]+\\.[0-9]+)";
114 static final String s = "\\s+";
115 static final String any = "(.*)";
116
117 static final Pattern start = Pattern.compile("graph" + s + r + s + r
118 + s + r);
119 static final Pattern node = Pattern.compile("node" + s + id + s + r + s
120 + r + s + r + s + r + s + any);
121 static final Pattern edge = Pattern.compile("edge" + s + id + s + id
122 + s + d + s + any);
123 static final Pattern point = Pattern
124 .compile("\\s*(\\S+)\\s+(\\S+)(.*)");
125 }
126
127 private void parseDot(InputStream in) {
128 BufferedReader i = new BufferedReader(new InputStreamReader(in));
129
130 try {
131 do {
132 String line = i.readLine();
133
134 if (line != null) {
135 Matcher m;
136
137 m = Patterns.start.matcher(line);
138 if (m.matches()) {
139 parseStart(m.group(1), m.group(3));
140 continue;
141 }
142
143 m = Patterns.node.matcher(line);
144 if (m.matches()) {
145 parseNode(m.group(1), m.group(2), m.group(3), m.group(4), m.group(5));
146 continue;
147 }
148
149 m = Patterns.edge.matcher(line);
150 if (m.matches()) {
151 parseEdge(m.group(1), m.group(2), m.group(3), m
152 .group(4));
153 continue;
154 }
155 }
156 } while (i.ready());
157 } catch (IOException e) {
158 // TODO : do something with this error
159 }
160 }
161
162 /**
163 * Returns a list of edges from the source node to the target node.
164 */
165 public List<Integer> getAllEdges(int source, int target) {
166 List<Integer> result = new LinkedList<Integer>();
167 int outd = getOutDegree(source);
168 if (outd > 0) {
169 int[] edges = (int[]) m_links.get(source, OUTLINKS);
170 for (int i = 0; i < outd; ++i) {
171 if (getTargetNode(edges[i]) == target) {
172 result.add(new Integer(edges[i]));
173 }
174 }
175 }
176 return result;
177 }
178
179 /**
180 * Returns a list of edges between the source and target node
181 *
182 * @param source
183 * the source Node
184 * @param target
185 * the target Node
186 * @return an Edge with given source and target nodes, or null if no such
187 * edge is found.
188 */
189 public List<Edge> getAllEdges(Node source, Node target) {
190 nodeCheck(source, true);
191 nodeCheck(target, true);
192 List<Integer> edges = getAllEdges(source.getRow(), target.getRow());
193 List<Edge> result = new LinkedList<Edge>();
194 for (Integer i : edges) {
195 result.add(getEdge(i.intValue()));
196 }
197 return result;
198 }
199
200 private void parseEdge(String toString, String fromString,
201 String pointCount, String pointsStr) {
202 String to = idFromDot(toString);
203 String from = idFromDot(fromString);
204 Point2D[] points = parseEdgePoints(Integer.parseInt(pointCount),
205 pointsStr);
206
207 List<Edge> edges = getAllEdges(getNode(to), getNode(from));
208 for (Edge edge : edges) {
209 Object tmp = edge.get(DOT_CURVE_POINTS);
210 if (tmp == null) {
211 edge.set(DOT_CURVE_POINTS, points);
212 break;
213 }
214 }
215 }
216
217 private Point2D[] parseEdgePoints(int count, String rest) {
218 List<Point2D> points = new LinkedList<Point2D>();
219
220 for (; count > 0; count--) {
221 Matcher n = Patterns.point.matcher(rest);
222
223 if (n.matches()) {
224 int x = (int) (Double.parseDouble(n.group(1)) * scale * dpi);
225 int y = (int) (Double.parseDouble(n.group(2)) * scale * dpi);
226 points.add(new Point2D.Float(x, y));
227 rest = n.group(3);
228 } else {
229 break;
230 }
231 }
232
233 Point2D[] result = new Point2D[points.size()];
234 Iterator<Point2D> iter = points.iterator();
235
236 for (int i = 0; iter.hasNext(); i++) {
237 result[i] = iter.next();
238 }
239
240 return result;
241 }
242
243 private void parseNode(String id, String xstr, String ystr, String widthStr, String heightStr) {
244 id = idFromDot(id);
245 int x = (int) (Double.parseDouble(xstr) * scale * dpi);
246 int y = (int) (Double.parseDouble(ystr) * scale * dpi);
247 int width = (int) (Double.parseDouble(widthStr) * scale * dpi);
248 int height = (int) (Double.parseDouble(heightStr) * scale * dpi);
249
250 x = x - width / 2;
251 y = y - height / 2;
252 Node node = getNode(id);
253
254 if (node != null) {
255 node.setInt(DOT_X, x);
256 node.setInt(DOT_Y, y);
257 node.setInt(DOT_WIDTH, width);
258 node.setInt(DOT_HEIGHT, height);
259 } else {
260 System.err.println("Node not found: " + id);
261 }
262 }
263
264 private void parseStart(String scaleStr, String heightStr) {
265 scale = Double.parseDouble(scaleStr);
266 }
267
268 /**
269 * Prints out the prefuse graph to Graphviz Dot format
270 * @param b PrintStream to output the graph to
271 */
272 public void printDot(PrintStream b) {
273 b.append("digraph prefuseGraph {\n");
274 printNodes(b);
275 printEdges(b);
276 b.append("}\n");
277 }
278
279 private void printEdges(PrintStream b) {
280 Iterator<?> iter = edges();
281
282 while (iter.hasNext()) {
283 Edge t = (Edge) iter.next();
284 int from = t.getInt(Graph.DEFAULT_SOURCE_KEY);
285 int to = t.getInt(Graph.DEFAULT_TARGET_KEY);
286 String fromId = getNode(from).getString(DOT_ID);
287 String toId = getNode(to).getString(DOT_ID);
288 b.append(idToDot(fromId) + " -> " + idToDot(toId) + "\n");
289 }
290 }
291
292 private void printNodes(PrintStream b) {
293 Iterator<?> iter = nodes();
294
295 while (iter.hasNext()) {
296 Node t = (Node) iter.next();
297 String id = idToDot(t.getString(DOT_ID));
298 storeNode(id, t);
299 b.append(id + " [");
300
301 for (int i = t.getColumnCount() - 1; i >= 0; i--) {
302 String key = t.getColumnName(i);
303 if (t.canGetString(key)) {
304 String value = t.getString(i);
305 if (value != null) {
306 b.append(" " + key + "=\"" + escape(value) + "\" ");
307 }
308 }
309 }
310 b.append(" ]\n");
311 }
312 }
313
314 private String escape(String string) {
315 StringBuffer result = new StringBuffer();
316 StringCharacterIterator i = new StringCharacterIterator(string);
317 char ch = i.current();
318
319 while (ch != CharacterIterator.DONE) {
320 switch (ch) {
321 case '\"':
322 result.append('\\');
323 result.append('\"');
324 break;
325 case '\n':
326 result.append('\\');
327 result.append('n');
328 break;
329 case '\t':
330 result.append('\\');
331 result.append('t');
332 break;
333 case '\\':
334 if (ch != CharacterIterator.DONE) {
335 ch = i.next();
336 switch (ch) {
337 case '\"':
338 case '\n':
339 case '\t':
340 result.append('\\');
341 result.append('\\');
342 result.append('\\');
343 break;
344 default:
345 result.append('\\');
346 }
347 } else {
348 result.append(ch);
349 }
350 default:
351 result.append(ch);
352 }
353
354 ch = i.next();
355 }
356
357 return result.toString();
358 }
359
360 /**
361 * A safe method to set an attribute of a node. If the attribute's column
362 * was not declared yet, it will be declared by this method first.
363 * @param node
364 * @param key
365 * @param value
366 */
367 public void setNodeAttribute(Node node, String key, Object value) {
368 if (node.getColumnIndex(key) == -1) {
369 addColumn(key, value.getClass());
370 }
371
372 node.set(key, value);
373 }
374
375 private String idToDot(String string) {
376 String result = escape(string);
377 return "\"" + result + "\"";
378 }
379
380 private String idFromDot(String id) {
381 if (id.charAt(0) == '\"') {
382 return id;
383 }
384
385 return "\"" + id + "\"";
386 }
387
388 public static void main(String[] args) {
389 DotAdapter a = new DotAdapter();
390
391 Node n = a.addNode();
392 n.set(DotAdapter.DOT_ID, "{ aap }");
393 n.set(DotAdapter.DOT_LABEL, "{ aap }");
394 a.setNodeAttribute(n, "height", "1.5");
395 a.setNodeAttribute(n, "width", "2.5");
396
397 Node m = a.addNode();
398 m.set(DotAdapter.DOT_ID, "[A-Z a-z]");
399 m.set(DotAdapter.DOT_LABEL, "[A-Z a-z]");
400 a.setNodeAttribute(n, "height", "2.5");
401 a.setNodeAttribute(n, "width", "1.25");
402
403 a.addEdge(m, n);
404
405 n = a.addNode();
406 n.set(DotAdapter.DOT_ID, "Aap");
407 n.set(DotAdapter.DOT_LABEL, "Aap");
408
409 m = a.addNode();
410 m.set(DotAdapter.DOT_ID, "Noot");
411 m.set(DotAdapter.DOT_LABEL, "Noot");
412
413 a.addEdge(m, n);
414 a.addEdge(m, n);
415 a.printDot(System.err);
416 a.doDotLayout();
417 return;
418 }
419
420
421 }