001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.examples.graph;
018
019import java.io.Writer;
020import java.util.HashMap;
021import java.util.Map;
022
023import net.automatalib.commons.dotutil.DOT;
024import net.automatalib.graphs.base.compact.CompactEdge;
025import net.automatalib.graphs.base.compact.CompactSimpleGraph;
026import net.automatalib.graphs.dot.EmptyDOTHelper;
027import net.automatalib.util.graphs.dot.GraphDOT;
028import net.automatalib.util.graphs.traversal.BaseDFSVisitor;
029import net.automatalib.util.graphs.traversal.GraphTraversal;
030
031public class DFSExample {
032        
033        public static enum EdgeType {
034                TREE("bold"),
035                FORWARD("dotted"),
036                BACK("solid"),
037                CROSS("dashed");
038                
039                private final String style;
040                
041                private EdgeType(String style) {
042                        this.style = style;
043                }
044                
045                public String getStyle() {
046                        return style;
047                }
048        }
049        
050        public static class MyDFSVisitor<N,E> extends BaseDFSVisitor<N, E, Void> {
051                private final Map<N,Integer> dfsNumbers = new HashMap<>();
052                private final Map<E,EdgeType> edgeTypes = new HashMap<>();
053                
054                /* (non-Javadoc)
055                 * @see net.automatalib.util.graphs.traversal.BaseDFSVisitor#explore(java.lang.Object, java.lang.Object)
056                 */
057                @Override
058                public void explore(N node, Void data) {
059                        dfsNumbers.put(node, dfsNumbers.size());
060                }
061
062                @Override
063                public Void treeEdge(N srcNode, Void srcData, E edge,
064                                N tgtNode) {
065                        edgeTypes.put(edge, EdgeType.TREE);
066                        return null;
067                }
068                
069                @Override
070                public void backEdge(N srcNode, Void srcData, E edge,
071                                N tgtNode, Void tgtData) { 
072                        edgeTypes.put(edge, EdgeType.BACK);
073                }
074                
075                @Override
076                public void crossEdge(N srcNode, Void srcData, E edge,
077                                N tgtNode, Void tgtData) {
078                        edgeTypes.put(edge, EdgeType.CROSS);
079                }
080                @Override
081                public void forwardEdge(N srcNode, Void srcData, E edge,
082                                N tgtNode, Void tgtData) {
083                        edgeTypes.put(edge, EdgeType.FORWARD);
084                }
085                
086                public Map<N,Integer> getDfsNumbers() {
087                        return dfsNumbers;
088                }
089                
090                public Map<E,EdgeType> getEdgeTypes() {
091                        return edgeTypes;
092                }
093        }
094        
095        public static class DFSResultDOTHelper<N,E> extends EmptyDOTHelper<N,E> {
096                private final Map<N,Integer> dfsNumbers;
097                private final Map<E,EdgeType> edgeTypes;
098                
099                /* (non-Javadoc)
100                 * @see net.automatalib.graphs.dot.EmptyDOTHelper#getNodeProperties(java.lang.Object, java.util.Map)
101                 */
102                @Override
103                public boolean getNodeProperties(N node,
104                                Map<String, String> properties) {
105                        String lbl = properties.get("label");
106                        Integer dfsNum = dfsNumbers.get(node);
107                        assert dfsNum != null;
108                        properties.put("label", lbl + " [#" + dfsNum + "]");
109                        return true;
110                }
111                
112                /* (non-Javadoc)
113                 * @see net.automatalib.graphs.dot.EmptyDOTHelper#getEdgeProperties(java.lang.Object, java.util.Map)
114                 */
115                @Override
116                public boolean getEdgeProperties(N src, E edge, N tgt,
117                                Map<String, String> properties) {
118                        EdgeType et = edgeTypes.get(edge);
119                        assert et != null;
120                        properties.put("style", et.getStyle());
121                        return true;
122                }
123                
124                public DFSResultDOTHelper(Map<N, Integer> dfsNumbers,
125                                Map<E,EdgeType> edgeTypes) {
126                        this.dfsNumbers = dfsNumbers;
127                        this.edgeTypes = edgeTypes;
128                }
129                
130                public DFSResultDOTHelper(MyDFSVisitor<N,E> vis) {
131                        this(vis.getDfsNumbers(), vis.getEdgeTypes());
132                }
133        }
134
135        
136        public static void main(String[] args) throws Exception {
137                CompactSimpleGraph<Void> graph = new CompactSimpleGraph<>();
138                
139                int n0 = graph.addIntNode(), n1 = graph.addIntNode(), n2 = graph.addIntNode(), n3 = graph.addIntNode(), n4 = graph.addIntNode();
140                
141                graph.connect(n0, n1);
142                graph.connect(n0, n2);
143                graph.connect(n1, n1);
144                graph.connect(n1, n2);
145                graph.connect(n2, n3);
146                graph.connect(n3, n1);
147                graph.connect(n3, n0);
148                graph.connect(n0, n4);
149                graph.connect(n4, n3);
150                
151                MyDFSVisitor<Integer,CompactEdge<Void>> vis = new MyDFSVisitor<>();
152                GraphTraversal.dfs(graph, n0, vis);
153                DFSResultDOTHelper<Integer,CompactEdge<Void>> helper = new DFSResultDOTHelper<>(vis);
154                
155                Writer w = DOT.createDotWriter(true);
156                GraphDOT.write(graph, w, helper);
157                w.close();
158        }
159
160}