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}