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 DotNodeLayout.java 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 return "\"" + id + "\""; 385 } 386 387 public static void main(String[] args) { 388 DotAdapter a = new DotAdapter(); 389 390 Node n = a.addNode(); 391 n.set(DotAdapter.DOT_ID, "{ aap }"); 392 n.set(DotAdapter.DOT_LABEL, "{ aap }"); 393 a.setNodeAttribute(n, "height", "1.5"); 394 a.setNodeAttribute(n, "width", "2.5"); 395 396 Node m = a.addNode(); 397 m.set(DotAdapter.DOT_ID, "[A-Z a-z]"); 398 m.set(DotAdapter.DOT_LABEL, "[A-Z a-z]"); 399 a.setNodeAttribute(n, "height", "2.5"); 400 a.setNodeAttribute(n, "width", "1.25"); 401 402 a.addEdge(m, n); 403 404 n = a.addNode(); 405 n.set(DotAdapter.DOT_ID, "Aap"); 406 n.set(DotAdapter.DOT_LABEL, "Aap"); 407 408 m = a.addNode(); 409 m.set(DotAdapter.DOT_ID, "Noot"); 410 m.set(DotAdapter.DOT_LABEL, "Noot"); 411 412 a.addEdge(m, n); 413 a.addEdge(m, n); 414 a.printDot(System.err); 415 a.doDotLayout(); 416 return; 417 } 418 419 420 }