001package stdlib;
002
003import java.io.File;
004import java.io.FileWriter;
005import java.io.IOException;
006import java.io.PrintWriter;
007import java.lang.reflect.AccessibleObject;
008import java.lang.reflect.Field;
009import java.util.ArrayList;
010import java.util.HashMap;
011import java.util.HashSet;
012import java.util.Locale;
013import java.util.Map;
014import java.util.Objects;
015import java.util.Set;
016
017// A fancy way to draw trees: http://stackoverflow.com/questions/10902745/enforcing-horizontal-node-ordering-in-a-dot-tree
018// GraphvizBuilder.nodesToFile (stack.first, "rankdir=\"LR\"");
019
020// TODO: Documentation
021public final class GraphvizBuilder {
022        private static enum Type { DIGRAPH, GRAPH }
023
024        private static ArrayList<String> DOT_EXTENSIONS;
025        static {
026                DOT_EXTENSIONS = new ArrayList<> ();
027                DOT_EXTENSIONS.add ("gv");
028                DOT_EXTENSIONS.add ("dot");
029        }
030        private static HashSet<String> DOT_OUTPUT_FORMATS;
031        static {
032                DOT_OUTPUT_FORMATS = new HashSet<> ();
033                DOT_OUTPUT_FORMATS.add ("bmp");
034                DOT_OUTPUT_FORMATS.add ("cgimage");
035                DOT_OUTPUT_FORMATS.add ("cmap");
036                DOT_OUTPUT_FORMATS.add ("cmapx");
037                DOT_OUTPUT_FORMATS.add ("eps");
038                DOT_OUTPUT_FORMATS.add ("exr");
039                DOT_OUTPUT_FORMATS.add ("fig");
040                DOT_OUTPUT_FORMATS.add ("gif");
041                DOT_OUTPUT_FORMATS.add ("icns");
042                DOT_OUTPUT_FORMATS.add ("ico");
043                DOT_OUTPUT_FORMATS.add ("imap");
044                DOT_OUTPUT_FORMATS.add ("ismap");
045                DOT_OUTPUT_FORMATS.add ("jp2");
046                DOT_OUTPUT_FORMATS.add ("jpe");
047                DOT_OUTPUT_FORMATS.add ("jpeg");
048                DOT_OUTPUT_FORMATS.add ("jpg");
049                DOT_OUTPUT_FORMATS.add ("pct");
050                DOT_OUTPUT_FORMATS.add ("pdf");
051                DOT_OUTPUT_FORMATS.add ("pic");
052                DOT_OUTPUT_FORMATS.add ("pict");
053                DOT_OUTPUT_FORMATS.add ("png");
054                DOT_OUTPUT_FORMATS.add ("pov");
055                DOT_OUTPUT_FORMATS.add ("ps");
056                DOT_OUTPUT_FORMATS.add ("ps2");
057                DOT_OUTPUT_FORMATS.add ("psd");
058                DOT_OUTPUT_FORMATS.add ("sgi");
059                DOT_OUTPUT_FORMATS.add ("svg");
060                DOT_OUTPUT_FORMATS.add ("svgz");
061                DOT_OUTPUT_FORMATS.add ("tga");
062                DOT_OUTPUT_FORMATS.add ("tif");
063                DOT_OUTPUT_FORMATS.add ("tiff");
064                DOT_OUTPUT_FORMATS.add ("tk");
065                DOT_OUTPUT_FORMATS.add ("vml");
066                DOT_OUTPUT_FORMATS.add ("vmlz");
067        }
068        private static ArrayList<String> POSSIBLE_DOT_LOCATIONS;
069        static {
070                POSSIBLE_DOT_LOCATIONS = new ArrayList<> ();
071                String os = System.getProperty ("os.name").toLowerCase ();
072                if (os.startsWith ("win")) {
073                        POSSIBLE_DOT_LOCATIONS.add ("c:/Program Files (x86)/Graphviz2.38/bin/dot.exe");
074                        POSSIBLE_DOT_LOCATIONS.add (System.getProperty ("user.dir") + "/lib/graphviz-windows/bin/dot.exe");
075                } else if (os.startsWith ("mac")) {
076                        POSSIBLE_DOT_LOCATIONS.add ("/usr/local/bin/dot");
077                        POSSIBLE_DOT_LOCATIONS.add ("/usr/bin/dot");
078                        POSSIBLE_DOT_LOCATIONS.add (System.getProperty ("user.dir") + "/lib/graphviz-mac/bin/dot");
079                } else {
080                        POSSIBLE_DOT_LOCATIONS.add ("/usr/local/bin/dot");
081                        POSSIBLE_DOT_LOCATIONS.add ("/usr/bin/dot");
082                }
083        }
084        public static void graphvizAddPossibleDotLocation (String value) {
085                POSSIBLE_DOT_LOCATIONS.add (value);
086        }
087
088        private static interface Element {
089                public String toString (Type type);
090        }
091        private static String getProperties (String label, String properties) {
092                if (properties == null || "".equals (properties)) {
093                        if (label == null || "".equals (label)) {
094                                return ";";
095                        } else {
096                                return "[label=\"" + label + "\"];";
097                        }
098                } else {
099                        if (label == null || "".equals (label)) {
100                                return "[" + properties + "];";
101                        } else {
102                                return "[label=\"" + label + "\"," + properties + "];";
103                        }
104                }
105        }
106        private static final class Node implements Element {
107                private final String id;
108                private final String properties;
109                public Node (String id, String label, String properties) {
110                        if (id == null || "".equals (id)) throw new IllegalArgumentException ();
111                        this.id = id;
112                        this.properties = getProperties (label, properties);
113                }
114                public String toString (Type type) {
115                        return "  " + id + properties;
116                }
117        }
118        private static final class Edge implements Element {
119                private final String src;
120                private final String dst;
121                private final String properties;
122                public Edge (String src, String dst, String label, String properties) {
123                        if (src == null || "".equals (src)) throw new IllegalArgumentException ();
124                        if (dst == null || "".equals (dst)) throw new IllegalArgumentException ();
125                        this.src = src;
126                        this.dst = dst;
127                        this.properties = getProperties (label, properties);
128                }
129                public String toString (Type type) {
130                        String arrow = (type == Type.DIGRAPH ? " -> " : " -- ");
131                        return "  " + src + arrow + dst + properties;
132                }
133        }
134
135        private static String defaultGraphProperties = "";
136        private static String defaultNodeProperties = "";
137        private static String defaultEdgeProperties = "fontsize=12";
138        private static String nullNodeProperties = "shape=\"point\"";
139        private static String nullEdgeProperties = "shape=\"point\"";
140
141        private static int fileCount = 0;
142        public static void binaryHeapToFile (double[] heap, int N) {
143                binaryHeapToFile (heap, N, "heap" + fileCount + ".png");
144                fileCount++;
145        }
146        public static void binaryHeapToFile (Object[] heap, int N) {
147                binaryHeapToFile (heap, N, "heap" + fileCount + ".png");
148                fileCount++;
149        }
150        public static void ufToFile (int[] uf) {
151                ufToFile (uf, "uf" + fileCount + ".png");
152                fileCount++;
153        }
154        /**
155         * Shows simple recursive data structures.
156         * The class of the root parameter is taken to be the must be an element of the recursive node class.
157         *
158         * @param root
159         */
160        public static void nodesToFile (Object root)                  { nodesToFile (root, defaultNodeProperties, true); }
161        public static void nodesToFile (Object root, String filename) { nodesToFile (root, filename, defaultNodeProperties, true); }
162        private static void nodesToFile (Object root, String properties, boolean withLabeledEdges) {
163                nodesToFile (root, "nodes" + fileCount + ".png", properties, withLabeledEdges);
164                fileCount++;
165        }
166
167
168        public static void binaryHeapToFile (double[] heap, int N, String filename) {
169                GraphvizBuilder gb = new GraphvizBuilder ();
170                gb.addBinaryHeap (heap, N);
171                gb.toFile (filename, "rankdir=\"BT\"");
172        }
173        public static void binaryHeapToFile (Object[] heap, int N, String filename) {
174                GraphvizBuilder gb = new GraphvizBuilder ();
175                gb.addBinaryHeap (heap, N);
176                gb.toFile (filename, "rankdir=\"BT\"");
177        }
178        public static void ufToFile (int[] uf, String filename) {
179                GraphvizBuilder gb = new GraphvizBuilder ();
180                gb.addUF (uf);
181                gb.toFile (filename, "rankdir=\"BT\"");
182        }
183        public static void nodesToFile (Object root, String filename, String properties, boolean withLabeledEdges) {
184                GraphvizBuilder gb = new GraphvizBuilder ();
185                gb.addNodes (root, withLabeledEdges);
186                gb.toFile (filename, properties);
187        }
188
189
190        private void addBinaryHeap (Object[] heap, int N) {
191                if (heap == null) throw new IllegalArgumentException ("null heap");
192                if (N<0 || N>heap.length) throw new IllegalArgumentException ("N=" + N + " is not in range [0.." + heap.length + "]");
193                String prefix = "heap__" + heap.hashCode ();
194                for (int i = 1; i <= N; i++) {
195                        addLabeledNodeString (prefix + i, heap[i].toString ());
196                }
197                for (int i = 2; i <= N; i++) {
198                        addEdgeString (prefix + i, prefix + (i/2));
199                }
200                int logN = 31 - Integer.numberOfLeadingZeros(N);
201                for (int i = N+1; i<2<<logN; i++) {
202                        addFromNullEdgeString (prefix + (i/2));
203                }
204//              if (N%2==0) {
205//                      addFromNullEdgeString (prefix + (N/2));
206//              }
207        }
208        private void addBinaryHeap (double[] heap, int N) {
209                if (heap == null) throw new IllegalArgumentException ("null heap");
210                if (N<0 || N>heap.length) throw new IllegalArgumentException ("N=" + N + " is not in range [0.." + heap.length + "]");
211                String prefix = "heap__" + heap.hashCode ();
212                for (int i = 1; i <= N; i++) {
213                        addLabeledNodeString (prefix + i, Double.toString(heap[i]));
214                }
215                for (int i = 2; i <= N; i++) {
216                        addEdgeString (prefix + i, prefix + (i/2));
217                }
218                int logN = 31 - Integer.numberOfLeadingZeros(N);
219                for (int i = N+1; i<2<<logN; i++) {
220                        addFromNullEdgeString (prefix + (i/2));
221                }
222//              if (N%2==0) {
223//                      addFromNullEdgeString (prefix + (N/2));
224//              }
225        }       
226        private void addUF (int[] uf) {
227                if (uf == null) throw new IllegalArgumentException ("null uf");
228                String prefix = "uf__" + uf.hashCode ();
229                for (int i = 0; i < uf.length; i++) {
230                        addLabeledNodeString (prefix + i, Integer.toString (i));
231                }
232                for (int i = 0; i < uf.length; i++) {
233                        if (i != uf[i])
234                                addEdgeString (prefix + i, prefix + uf[i]);
235                }
236        }
237        private void addNodes (Object root, boolean withLabeledEdges) {
238                if (root == null) {
239                        addNullEdge (null);
240                } else {
241                        addNodes (root, new HashSet<Object> (), root.getClass (), withLabeledEdges);
242                }
243        }
244        private void addNodes (Object obj, Set<Object> visited, Class<?> nodeClass, boolean withLabeledEdges) {
245                visited.add (obj);
246                Class<?> clazz = obj.getClass ();
247                if (clazz.isArray ()) {
248                        throw new Error ("Can't deal with arrays");
249                } else {
250                        StringBuilder labelBuilder = new StringBuilder ();
251                        Map<Object,Field> children = new HashMap<> ();
252
253                        Field[] fields = clazz.getDeclaredFields ();
254                        AccessibleObject.setAccessible (fields, true);
255                        boolean first = true;
256                        for (int i = 0; i < fields.length; i++) {
257                                Field field = fields[i];
258                                Object value;
259                                try { value = field.get (obj); } catch (IllegalAccessException e) { throw new Error (e); }
260                                if (field.getType () == nodeClass) {
261                                        if (value == null) {
262                                                if (withLabeledEdges)
263                                                        addLabeledNullEdge (obj, field.getName ());
264                                                else
265                                                        addNullEdge (obj);
266                                        } else {
267                                                children.put (value, field);
268                                        }
269                                } else {
270                                        if (first) { first = false; } else { labelBuilder.append (", "); }
271                                        labelBuilder.append (value == null ? "null" : value.toString ());
272                                }
273                        }
274                        addLabeledNode (obj, labelBuilder.toString ());
275                        for (Object child : children.keySet ()) {
276                                if (!visited.contains (child))
277                                        addNodes (child, visited, nodeClass, withLabeledEdges);
278                        }
279                        for (Object child : children.keySet ()) {
280                                if (withLabeledEdges)
281                                        addLabeledEdge (obj, child, children.get (child).getName ());
282                                else
283                                        addEdge (obj, child);
284                        }
285                }
286
287        }
288
289        private static String getId (Object o) {
290                return "hash__" + Objects.hashCode (o);
291        }
292        private static String getId (int i) {
293                return Integer.toString (i);
294        }
295
296        private static String getLabel (Object o) {
297                return quote (Objects.toString (o));
298        }
299        private static String getLabel (String s) {
300                return quote (s);
301        }
302        private static String getLabel (int i) {
303                return Integer.toString (i);
304        }
305        private static String getLabel (double d) {
306                return Double.toString (d);
307        }
308        private static String getLabel (float f) {
309                return Float.toString (f);
310        }
311        //private static final String canAppearUnquotedInLabelChars = " /$&*@#!-+()^%;_[],;.=";
312        private static boolean canAppearUnquotedInLabel (char c) {
313                return true;
314                //return canAppearUnquotedInLabelChars.indexOf (c) != -1 || Character.isLetter (c) || Character.isDigit (c);
315        }
316        private static final String quotable = "\\\"<>{}|";
317        protected static String quote (String s) {
318                s = unescapeJavaString (s);
319                StringBuffer sb = new StringBuffer ();
320                for (int i = 0, n = s.length (); i < n; i++) {
321                        char c = s.charAt (i);
322                        if (quotable.indexOf (c) != -1) sb.append ('\\').append (c);
323                        else if (canAppearUnquotedInLabel (c)) sb.append (c);
324                        else sb.append ("\\\\u").append (Integer.toHexString (c));
325                }
326                return sb.toString ();
327        }
328        /**
329         * Unescapes a string that contains standard Java escape sequences.
330         * <ul>
331         * <li><strong>\\b \\f \\n \\r \\t \\" \\'</strong> :
332         * BS, FF, NL, CR, TAB, double and single quote.</li>
333         * <li><strong>\\N \\NN \\NNN</strong> : Octal character
334         * specification (0 - 377, 0x00 - 0xFF).</li>
335         * <li><strong>\\uNNNN</strong> : Hexadecimal based Unicode character.</li>
336         * </ul>
337         *
338         * @param st
339         *            A string optionally containing standard java escape sequences.
340         * @return The translated string.
341         */
342        // from http://udojava.com/2013/09/28/unescape-a-string-that-contains-standard-java-escape-sequences/
343        private static String unescapeJavaString(String st) {
344                StringBuilder sb = new StringBuilder(st.length());
345                for (int i = 0; i < st.length(); i++) {
346                        char ch = st.charAt(i);
347                        if (ch == '\\') {
348                                char nextChar = (i == st.length() - 1) ? '\\' : st.charAt(i + 1);
349                                // Octal escape?
350                                if (nextChar >= '0' && nextChar <= '7') {
351                                        String code = "" + nextChar;
352                                        i++;
353                                        if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') {
354                                                code += st.charAt(i + 1);
355                                                i++;
356                                                if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') {
357                                                        code += st.charAt(i + 1);
358                                                        i++;
359                                                }
360                                        }
361                                        sb.append((char) Integer.parseInt(code, 8));
362                                        continue;
363                                }
364                                switch (nextChar) {
365                                case '\\': ch = '\\'; break;
366                                case 'b': ch = '\b'; break;
367                                case 'f': ch = '\f'; break;
368                                case 'n': ch = '\n'; break;
369                                case 'r': ch = '\r'; break;
370                                case 't': ch = '\t'; break;
371                                case '\"': ch = '\"'; break;
372                                case '\'': ch = '\''; break;
373                                // Hex Unicode: u????
374                                case 'u':
375                                        if (i >= st.length() - 5) { ch = 'u'; break; }
376                                        int code = Integer.parseInt(st.substring (i+2,i+6), 16);
377                                        sb.append(Character.toChars(code));
378                                        i += 5;
379                                        continue;
380                                }
381                                i++;
382                        }
383                        sb.append(ch);
384                }
385                return sb.toString();
386        }
387
388
389        private final ArrayList<Element> elements = new ArrayList<> ();
390
391        public void addNode (Object o)                                         { addLabeledNodeString (getId (o), getLabel (o), defaultNodeProperties); }
392        public void addNode (Object o, String properties)                      { addLabeledNodeString (getId (o), getLabel (o), properties); }
393        public void addLabeledNode (Object o, String label)                    { addLabeledNodeString (getId (o), getLabel (label), defaultNodeProperties); }
394        public void addLabeledNode (Object o, String label, String properties) { addLabeledNodeString (getId (o), getLabel (label), properties); }
395
396        public void addNode (int id)                                         { addLabeledNodeString (getId (id), getLabel (id), defaultNodeProperties); }
397        public void addNode (int id, String properties)                      { addLabeledNodeString (getId (id), getLabel (id), properties); }
398        public void addLabeledNode (int id, String label)                    { addLabeledNodeString (getId (id), getLabel (label), defaultNodeProperties); }
399        public void addLabeledNode (int id, String label, String properties) { addLabeledNodeString (getId (id), getLabel (label), properties); }
400
401        private void addNodeString (String id)                                         { addLabeledNodeString (id, id, defaultNodeProperties); }
402        private void addNodeString (String id, String properties)                      { addLabeledNodeString (id, id, properties); }
403        private void addLabeledNodeString (String id, String label)                    { addLabeledNodeString (id, getLabel (label), defaultNodeProperties); }
404        private void addLabeledNodeString (String id, String label, String properties) { elements.add (new Node (id, getLabel (label), properties)); }
405
406        public void addEdge (Object src, Object dst)                                         { addEdgeString (getId (src), getId (dst), defaultEdgeProperties); }
407        public void addEdge (Object src, Object dst, String properties)                      { addEdgeString (getId (src), getId (dst), properties); }
408        public void addLabeledEdge (Object src, Object dst, float label)                     { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
409        public void addLabeledEdge (Object src, Object dst, float label, String properties)  { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
410        public void addLabeledEdge (Object src, Object dst, double label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
411        public void addLabeledEdge (Object src, Object dst, double label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
412        public void addLabeledEdge (Object src, Object dst, int label)                       { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getId (label), defaultEdgeProperties); }
413        public void addLabeledEdge (Object src, Object dst, int label, String properties)    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getId (label), properties); }
414        public void addLabeledEdge (Object src, Object dst, String label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), defaultEdgeProperties); }
415        public void addLabeledEdge (Object src, Object dst, String label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), properties); }
416
417        public void addEdge (int src, int dst)                                         { addEdgeString (getId (src), getId (dst), defaultEdgeProperties); }
418        public void addEdge (int src, int dst, String properties)                      { addEdgeString (getId (src), getId (dst), properties); }
419        public void addLabeledEdge (int src, int dst, float label)                     { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
420        public void addLabeledEdge (int src, int dst, float label, String properties)  { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
421        public void addLabeledEdge (int src, int dst, double label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
422        public void addLabeledEdge (int src, int dst, double label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
423        public void addLabeledEdge (int src, int dst, int label)                       { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), defaultEdgeProperties); }
424        public void addLabeledEdge (int src, int dst, int label, String properties)    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label) + "\", length=\"" + getLabel (label), properties); }
425        public void addLabeledEdge (int src, int dst, String label)                    { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), defaultEdgeProperties); }
426        public void addLabeledEdge (int src, int dst, String label, String properties) { addLabeledEdgeString (getId (src), getId (dst), getLabel (label), properties); }
427
428        private void addEdgeString (String src, String dst)                                         { addEdgeString (src, dst, defaultEdgeProperties); }
429        private void addEdgeString (String src, String dst, String properties)                      { elements.add (new Edge (src, dst, null, properties)); }
430        private void addLabeledEdgeString (String src, String dst, float label)                     { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
431        private void addLabeledEdgeString (String src, String dst, float label, String properties)  { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
432        private void addLabeledEdgeString (String src, String dst, double label)                    { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
433        private void addLabeledEdgeString (String src, String dst, double label, String properties) { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
434        private void addLabeledEdgeString (String src, String dst, int label)                       { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), defaultEdgeProperties); }
435        private void addLabeledEdgeString (String src, String dst, int label, String properties)    { addLabeledEdgeString (src, dst, getLabel (label) + ", length=" + getLabel (label), properties); }
436        private void addLabeledEdgeString (String src, String dst, String label)                    { addLabeledEdgeString (src, dst, getLabel (label), defaultEdgeProperties); }
437        private void addLabeledEdgeString (String src, String dst, String label, String properties) { elements.add (new Edge (src, dst, getLabel (label), properties)); }
438
439        private int nullId = 0;
440        public void addNullEdge (Object src) { addNullEdgeString(getId (src)); }
441        public void addNullEdgeString (String src) {
442                String id = "null__" + nullId;
443                nullId++;
444                addLabeledNodeString (id, "", nullNodeProperties);
445                if (src != null) addEdgeString (src, id, nullEdgeProperties);
446        }
447        public void addFromNullEdgeString (String src) {
448                String id = "null__" + nullId;
449                nullId++;
450                addLabeledNodeString (id, "", nullNodeProperties);
451                if (src != null) addEdgeString (id, src, nullEdgeProperties);
452        }
453        public void addLabeledNullEdge (Object src, String label) { addLabeledNullEdgeString(getId (src), label); }
454        public void addLabeledNullEdgeString (String src, String label) {
455                String id = "null__" + nullId;
456                nullId++;
457                addLabeledNodeString (id, "", nullNodeProperties);
458                if (src != null) addLabeledEdgeString (src, id, getLabel (label), nullEdgeProperties);
459        }
460
461        private static PrintWriter getPrintWriter (File file) {
462                PrintWriter out;
463                try {
464                        out = new PrintWriter (new FileWriter (file));
465                } catch (IOException e) {
466                        throw new Error ("\n!!!! Cannot open " + file + " for writing");
467                }
468                return out;
469        }
470        private static String getGvExecutable () {
471                String executable = null;
472                for (String s : POSSIBLE_DOT_LOCATIONS) {
473                        if (new File (s).canExecute ()) executable = s;
474                }
475                if (executable == null)
476                        throw new Error  ("\n!!!! Cannot find dot executable in " + POSSIBLE_DOT_LOCATIONS
477                                        + "\n!!!! Check the value of POSSIBLE_DOT_LOCATIONS in " + GraphvizBuilder.class.getCanonicalName ());
478                return executable;
479        }
480
481        //public void toFileUndirected (boolean keepGvFile, String filename)                      { toFile (Type.GRAPH, keepGvFile, filename, defaultGraphProperties); }
482        //public void toFileUndirected (boolean keepGvFile, String filename, String properties)   { toFile (Type.GRAPH, keepGvFile, filename, properties); }
483        public void toFileUndirected (String filename)                                          { toFile (Type.GRAPH, false, filename, defaultGraphProperties); }
484        public void toFileUndirected (String filename, String properties)                       { toFile (Type.GRAPH, false, filename, properties); }
485        //public void toFile (boolean keepGvFile, String filename)                                { toFile (Type.DIGRAPH, keepGvFile, filename, defaultGraphProperties); }
486        //public void toFile (boolean keepGvFile, String filename, String properties)             { toFile (Type.DIGRAPH, keepGvFile, filename, properties); }
487        public void toFile (String filename)                                                    { toFile (Type.DIGRAPH, false, filename, defaultGraphProperties); }
488        public void toFile (String filename, String properties)                                 { toFile (Type.DIGRAPH, false, filename, properties); }
489        //public void toFile (Type type, boolean keepGvFile, String filename)                    { toFile (type, keepGvFile, filename, defaultGraphProperties); }
490        private void toFile (Type type, boolean keepGvFile, String filename, String properties) {
491                // keepGvFile = true;
492                // Get basename and ext
493                String basename;
494                String ext;
495                if (filename.indexOf ('.') < 0) {
496                        ext = "png";
497                        basename = filename;
498                } else {
499                        int period = filename.lastIndexOf ('.');
500                        ext = filename.substring (period + 1);
501                        basename = filename.substring (0, period);
502                }
503                if (!new File (basename).isAbsolute ()) {
504                        if (dirName == null) setDirName ();
505                        basename = dirName + basename;
506                }
507
508                boolean extIsDot = DOT_EXTENSIONS.contains (ext);
509                boolean extIsOut = DOT_OUTPUT_FORMATS.contains (ext);
510
511                if ((!extIsDot) && (!extIsOut))
512                        throw new Error ("\n!!!! unrecognized extension \"" + ext + "\""
513                                        + "\n!!!! filename must end in \".ext\", where ext is \"gv\" or one of the following:\n!!!! " + DOT_OUTPUT_FORMATS);
514
515                
516                String newBasename = basename;
517                File newFile = new File (newBasename + "." + ext);
518                int suffix = 0;
519                while (newFile.exists()) {                      
520                        suffix++; 
521                        newBasename = basename + " " + suffix;
522                        newFile = new File(newBasename + "." + ext);
523                }
524                basename = newBasename;
525                
526                // Create dot input file
527                File gvFile;
528                if (extIsDot) {
529                        gvFile = new File (basename + "." + ext);
530                } else {
531                        gvFile = new File (basename + ".gv");
532                }
533                PrintWriter out = getPrintWriter (gvFile);
534                switch (type) {
535                case DIGRAPH: out.print ("digraph"); break;
536                case GRAPH:   out.print ("graph"); break;
537                }
538                out.println (" G {");
539                if (properties != null && !"".equals (properties))
540                        out.println ("  graph [" + properties + "];");
541                for (Element e : elements)
542                        out.println (e.toString (type));
543                out.println ("}");
544                out.close ();
545
546
547                // Run dot
548                if (extIsOut) {
549                        File outFile = new File (basename + "." + ext);
550
551                        String executable = getGvExecutable ();
552                        ProcessBuilder pb = new ProcessBuilder (executable, "-T", ext);
553                        pb.redirectInput (gvFile);
554                        pb.redirectOutput (outFile);
555                        int result = -1;
556                        try {
557                                result = pb.start ().waitFor ();
558                        } catch (IOException e) {
559                                throw new Error ("\n!!!! Cannot execute \"" + executable + "\"\n!!!! Make sure you have installed http://www.graphviz.org/"
560                                                + "\n!!!! Check the value of POSSIBLE_DOT_LOCATIONS in " + GraphvizBuilder.class.getCanonicalName ());
561                        } catch (InterruptedException e) {
562                                throw new Error ("\n!!!! Execution of \"" + executable + "\" interrupted");
563                        }
564                        if (result == 0) {
565                                if (!keepGvFile) gvFile.delete ();
566                        } else {
567                                outFile.delete ();
568                        }
569                }
570        }
571        /**
572         * Graphics files are saved in directory baseDirName/Graphviz.
573         * If baseDirName is a relative pathname, then it is placed in the users Desktop folder.
574         * baseDirName directory is created if it does not already exist.
575         * If baseDirName/Graphviz exists, then numbers are appended to the directory name:
576         * "baseDirName/Graphviz 1", "baseDirName/Graphviz 2", etc.
577         */
578        public static void setBaseDirName (String baseDirName) {
579                if (baseDirName == null) throw new Error ("\n!!!! no nulls please");            
580                GraphvizBuilder.baseDirName = baseDirName;
581        }
582        private static String baseDirName = "GraphvizOutput";
583
584        private static boolean isWindows () {
585                String osName = System.getProperty("os.name");
586        if (osName == null) {
587            throw new Error("\n!!! os.name not found");
588        }
589        osName = osName.toLowerCase(Locale.ENGLISH);
590        return osName.contains("windows");
591        }
592        private static String getDesktop () {
593                if (isWindows()) {
594                        // Supposedly this selects the windows desktop folder:
595                        return javax.swing.filechooser.FileSystemView.getFileSystemView().getHomeDirectory().toString();
596                } else {
597                        return System.getProperty ("user.home") + File.separator + "Desktop";
598                }
599        }
600        private static String dirName = null;
601        private static void setDirName () {
602                // create dir
603                File dir = new File (baseDirName);
604                if (!dir.isAbsolute ()) {
605                        baseDirName = getDesktop() + File.separator + baseDirName;
606                        dir = new File (baseDirName);
607                }
608                if (dir.exists ()) {
609                        if (!dir.isDirectory ()) 
610                                throw new Error ("\n!!!! \"" + dir + "\" is not a directory");
611                        if (!dir.canWrite ()) 
612                                throw new Error ("\n!!!! Unable to write directory: \"" + dir + "\"");
613                } else {
614                        dir.mkdirs ();
615                }
616                
617                // create newDir
618                String mainClassName = "Graphviz";
619                String prefix = baseDirName + File.separator;
620                File newDir = new File (prefix + mainClassName);
621                int suffix = 0;
622                while (newDir.exists()) { 
623                        suffix++; 
624                        newDir = new File(prefix + mainClassName + " " + suffix);
625                }
626                newDir.mkdir ();
627                
628                if (!newDir.isDirectory () || !newDir.canWrite ())
629                        throw new Error ("Failed setOutputDirectory \"" + newDir + "\"");
630                dirName = newDir + File.separator;
631        }
632}