示例定向图和拓扑排序代码
任何人都知道我在哪里可以获得有向图的示例实现和用于在有向图上执行拓扑排序的示例代码？ （最好是Java）
以下是拓扑排序中维基百科页面中第一个算法的简单实现：
import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; public class Graph { static class Node{ public final String name; public final HashSet inEdges; public final HashSet outEdges; public Node(String name) { this.name = name; inEdges = new HashSet (); outEdges = new HashSet (); } public Node addEdge(Node node){ Edge e = new Edge(this, node); outEdges.add(e); node.inEdges.add(e); return this; } @Override public String toString() { return name; } } static class Edge{ public final Node from; public final Node to; public Edge(Node from, Node to) { this.from = from; this.to = to; } @Override public boolean equals(Object obj) { Edge e = (Edge)obj; return e.from == from && e.to == to; } } public static void main(String[] args) { Node seven = new Node("7"); Node five = new Node("5"); Node three = new Node("3"); Node eleven = new Node("11"); Node eight = new Node("8"); Node two = new Node("2"); Node nine = new Node("9"); Node ten = new Node("10"); seven.addEdge(eleven).addEdge(eight); five.addEdge(eleven); three.addEdge(eight).addEdge(ten); eleven.addEdge(two).addEdge(nine).addEdge(ten); eight.addEdge(nine).addEdge(ten); Node[] allNodes = {seven, five, three, eleven, eight, two, nine, ten}; //L <- Empty list that will contain the sorted elements ArrayList L = new ArrayList (); //S <- Set of all nodes with no incoming edges HashSet S = new HashSet (); for(Node n : allNodes){ if(n.inEdges.size() == 0){ S.add(n); } } //while S is non-empty do while(!S.isEmpty()){ //remove a node n from S Node n = S.iterator().next(); S.remove(n); //insert n into L L.add(n); //for each node m with an edge e from n to m do for(Iterator it = n.outEdges.iterator();it.hasNext();){ //remove edge e from the graph Edge e = it.next(); Node m = e.to; it.remove();//Remove edge from n m.inEdges.remove(e);//Remove edge from m //if m has no other incoming edges then insert m into S if(m.inEdges.isEmpty()){ S.add(m); } } } //Check to see if all edges are removed boolean cycle = false; for(Node n : allNodes){ if(!n.inEdges.isEmpty()){ cycle = true; break; } } if(cycle){ System.out.println("Cycle present, topological sort not possible"); }else{ System.out.println("Topological Sort: "+Arrays.toString(L.toArray())); } } }
几个星期前我对这个实现进行了编码。 它使用Java并使用自定义有向图类。 希望这些评论很有用！
我在维基百科页面上基于第二个替代方案所做的实现： http ： //en.wikipedia.org/wiki/Topological_sorting
public class Graph { Hashtable> adjList = new Hashtable>(); ArrayList nodes = new ArrayList (); LinkedList topoSorted; public Graph() {} public void add(Node node) { if (adjList.contains(node)) { return; } else { adjList.put(node, new ArrayList ()); nodes.add(node); } } public void addNeighbor(Node from, ArrayList list) { for (Node to: list) { addNeighbor(from, to); } } public void addNeighbor(Node from, Node to) { if (!adjList.containsKey(from)) { add(from); } if (!adjList.containsKey(to)) { add(to); } adjList.get(from).add(to); to.inDegree++; to.inNodes.add(from); } public void remove(Node node) { for (Node n: nodes) { for (Node x: adjList.get(n)) { if (x.equals(node)) removeNeighbor(n, x); } } adjList.remove(node); nodes.remove(node); } public void removeNeighbor(Node from, Node to) { adjList.get(from).remove(to); to.inDegree--; to.inNodes.remove(from); } public void resetVisited() { for (Node node: nodes) { node.visited = false; } } public boolean hasEdge(Node from, Node to) { return adjList.get(from).contains(to) ? true : false; } /** * for DAGS only * @throws Exception */ public void topologicalSort() throws Exception { /* L <-- Empty list that will contain the sorted elements */ topoSorted = new LinkedList (); /* Use set to keep track of permanently visited nodes * in constant time. Does have pointer overhead */ HashSet visited = new HashSet (); /* while there are unmarked nodes do */ for (Node n: nodes) { /* select an unmarked node n * visit(n) */ if (!visited.contains(n)) visit(n, visited); } } /* function: visit(node n) */ public void visit(Node node, HashSet set) throws Exception { /* if n has a temporary mark then stop (not a DAG) */ if (node.visited) { throw new Exception("graph cyclic"); /* if n is not marked (ie has not been visited) then... */ } else { /* mark n temporarily [using boolean field in node]*/ node.visited = true; /* for each node m with an edge n to m do... */ for (Node m: adjList.get(node)) { /* visit(m) */ if (!set.contains(m)) visit(m, set); } /* mark n permanently */ set.add(node); /* unmark n temporarily */ node.visited = false; /* add n to head of L */ topoSorted.addFirst(node); } } public void printGraph() { for (Node node: nodes) { System.out.print("from: " + node.value + " | to: "); for (Node m: adjList.get(node)) { System.out.print(m.value + " "); } System.out.println(); } } public void instantiateGraph() { Node seven = new Node("7"); Node five = new Node("5"); Node three = new Node("3"); Node eleven = new Node("11"); Node eight = new Node("8"); Node two = new Node("2"); Node nine = new Node("9"); Node ten = new Node("10"); addNeighbor(seven, eleven); addNeighbor(seven, eight); addNeighbor(five, eleven); addNeighbor(three, eight); addNeighbor(three, ten); addNeighbor(eleven, two); addNeighbor(eleven, nine); addNeighbor(eleven, ten); addNeighbor(eight, nine); try { topologicalSort(); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } for (Node node: topoSorted) { System.out.print(node.value + " "); } } public class Node { String value; boolean visited = false; int inDegree = 0; ArrayList inNodes = new ArrayList (); public Node (String value) { this.value = value; } } public static void main(String[] args) { Graph g = new Graph(); g.instantiateGraph(); } }
您还可以使用第三方开源项目，例如JGraphT 。 它提供了许多简单而复杂的图形结构及其可视化表示。 此外，您不必以这种方式处理结构问题。
这是我前段时间做过的一个实现：
/** * * Sorts a directed graph, obtaining a visiting sequence ("sorted" list) * that respects the "Predecessors" (as in a job/task requirements list). * (when there is freedom, the original ordering is preferred) * * The behaviour in case of loops (cycles) depends on the "mode": * permitLoops == false : loops are detected, but result is UNDEFINED (simpler) * permitLoops == true : loops are detected, result a "best effort" try, original ordering is privileged * * http://en.wikipedia.org/wiki/Topological_sort */ public class TopologicalSorter { private final boolean permitLoops; private final Collection graph; // original graph. this is not touched. private final List sorted = new ArrayList (); // result private final Set visited = new HashSet (); // auxiliar list private final Set withLoops = new HashSet (); // auxiliar: all succesors (also remote) of each node; this is only used if permitLoops==true private HashMap> succesors = null; public TopologicalSorter(Collection graph, boolean permitLoops) { this.graph = graph; this.permitLoops = permitLoops; } public void sort() { init(); for( T n : graph ) { if( permitLoops ) visitLoopsPermitted(n); else visitLoopsNoPermitted(n, new HashSet ()); } } private void init() { sorted.clear(); visited.clear(); withLoops.clear(); // build succesors map: only it permitLoops == true if( permitLoops ) { succesors = new HashMap>(); HashMap> addTo = new HashMap(); for( T n : graph ) { succesors.put(n, new HashSet ()); addTo.put(n, new HashSet ()); } for( T n2 : graph ) { for( DirectedGraphNode n1 : n2.getPredecessors() ) { succesors.get(n1).add(n2); } } boolean change = false; do { change = false; for( T n : graph ) { addTo.get(n).clear(); for( T ns : succesors.get(n) ) { for( T ns2 : succesors.get(ns) ) { if( !succesors.get(n).contains(ns2) ) { change = true; addTo.get(n).add(ns2); } } } } for( DirectedGraphNode n : graph ) { succesors.get(n).addAll(addTo.get(n)); } } while(change); } } private void visitLoopsNoPermitted(T n, Set visitedInThisCallStack) { // this is simpler than visitLoopsPermitted if( visited.contains(n) ) { if( visitedInThisCallStack.contains(n) ) { withLoops.add(n); // loop! } return; } //System.out.println("visiting " + n.toString()); visited.add(n); visitedInThisCallStack.add(n); for( DirectedGraphNode n1 : n.getPredecessors() ) { visitLoopsNoPermitted((T) n1, visitedInThisCallStack); } sorted.add(n); } private void visitLoopsPermitted(T n) { if( visited.contains(n) ) return; //System.out.println("visiting " + n.toString()); visited.add(n); for( DirectedGraphNode n1 : n.getPredecessors() ) { if( succesors.get(n).contains(n1) ) { withLoops.add(n); withLoops.add((T) n1); continue; } // loop! visitLoopsPermitted((T) n1); } sorted.add(n); } public boolean hadLoops() { return withLoops.size() > 0; } public List getSorted() { return sorted; } public Set getWithLoops() { return withLoops; } public void showResult() { // for debugging for( DirectedGraphNode node : sorted ) { System.out.println(node.toString()); } if( hadLoops() ) { System.out.println("LOOPS!:"); for( DirectedGraphNode node : withLoops ) { System.out.println(" " + node.toString()); } } } } /** * Node that conform a DirectedGraph * It is used by TopologicalSorter */ public interface DirectedGraphNode { /** * empty collection if no predecessors * @return */ public Collection getPredecessors(); }
这里有一个使用示例：
public class TopologicalSorterExample { public static class Node implements DirectedGraphNode { public final String x; public ArrayList antec = new ArrayList (); // immediate antecesors public Node(String x) {this.x= x;} public Collection getPredecessors() { return antec; } public String toString() { return x; } } public static void main(String[] args) { List graph = new ArrayList (); Node na = new Node("A"); Node nb = new Node("B"); Node nc = new Node("C"); Node nd = new Node("D"); Node ne = new Node("E"); nc.antec.add(na); nc.antec.add(nb); nd.antec.add(ne); ne.antec.add(na); na.antec.add(nd); graph.add(nc); graph.add(na); graph.add(nb); graph.add(ne); graph.add(nd); TopologicalSorter ts = new TopologicalSorter(graph, false); ts.sort(); ts.showResult(); } }
我的代码中还有两个额外的function（或复杂function）：我需要在我的情况下支持循环（循环），这样如果图形有循环，它会做出一些“尽力而为”的排序。 此行为由传递给构造函数的标志控制。 在任何情况下，您都可以（应该）调用hadLoops()来询问是否检测到周期。 此外，我希望排序算法在自由的情况下更喜欢原始排序。
同意杰里米。
我认为这是一个基于有效Java获取哈希码的实现： http ： //www.javapractices.com/topic/TopicAction.do？ Id = 28
如何添加以下方法来覆盖哈希码？
@Override public int hashCode(){ if (fHashCode == 0) { int result = HashCodeUtil.SEED; result = HashCodeUtil.hash(result, from); result = HashCodeUtil.hash(result, to); } return fHashCode; }
为了稍微增加@templatetypedef的优秀解决方案，我添加了一些unit testing，为自己和其他人提供了一些额外的信心。 希望这可以帮助…
import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; import java.util.List; import org.junit.Test; public class TestTopologicalSort { @Test (expected=java.lang.NullPointerException.class) public void testNullGraph() { final List orderedLayers = TopologicalSort.sort(null); } @Test public void testEmptyGraph() { final DirectedGraph dag = new DirectedGraph (); final List orderedLayers = TopologicalSort.sort(dag); assertEquals(0, orderedLayers.size()); } @Test public void testSingleVertex() { final DirectedGraph dag = new DirectedGraph (); dag.addNode("a"); final List orderedLayers = TopologicalSort.sort(dag); assertEquals(1, orderedLayers.size()); assertTrue(orderedLayers.contains("a")); } @Test public void testMultipleVertices() { final DirectedGraph dag = new DirectedGraph (); dag.addNode("a"); dag.addNode("b"); final List orderedLayers = TopologicalSort.sort(dag); assertEquals(2, orderedLayers.size()); assertTrue(orderedLayers.contains("a")); assertTrue(orderedLayers.contains("b")); } @Test (expected=java.util.NoSuchElementException.class) public void testBogusEdge() { final DirectedGraph dag = new DirectedGraph (); dag.addNode("a"); dag.addEdge("a", "b"); } @Test public void testSimpleDag() { final DirectedGraph dag = new DirectedGraph (); dag.addNode("b"); dag.addNode("a"); dag.addEdge("a", "b"); final List orderedLayers = TopologicalSort.sort(dag); assertEquals(2, orderedLayers.size()); assertTrue(orderedLayers.get(0).equals("a")); assertTrue(orderedLayers.get(1).equals("b")); } @Test public void testComplexGraph() { // node b has two incoming edges final DirectedGraph dag = new DirectedGraph (); dag.addNode("a"); dag.addNode("b"); dag.addNode("c"); dag.addNode("d"); dag.addNode("e"); dag.addNode("f"); dag.addNode("g"); dag.addNode("h"); dag.addEdge("a", "b"); dag.addEdge("a", "c"); dag.addEdge("c", "d"); dag.addEdge("d", "b"); dag.addEdge("c", "e"); dag.addEdge("f", "g"); final List orderedLayers = TopologicalSort.sort(dag); assertEquals(8, orderedLayers.size()); assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("b")); assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("c")); assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("d")); assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("e")); assertTrue(orderedLayers.indexOf("d") < orderedLayers.indexOf("b")); assertTrue(orderedLayers.indexOf("f") < orderedLayers.indexOf("g")); } @Test (expected=java.lang.IllegalArgumentException.class) public void testCycle() { // cycle between a, c, and d final DirectedGraph dag = new DirectedGraph (); dag.addNode("a"); dag.addNode("b"); dag.addNode("c"); dag.addNode("d"); dag.addNode("e"); dag.addNode("f"); dag.addNode("g"); dag.addNode("h"); dag.addEdge("a", "b"); dag.addEdge("a", "c"); dag.addEdge("c", "d"); dag.addEdge("d", "a"); dag.addEdge("c", "e"); dag.addEdge("f", "g"); final List orderedLayers = TopologicalSort.sort(dag); } }
您需要覆盖hashCode()函数，因为您在边缘使用HashSet 。
否则，它会引发意外的错误。
EXP：在hashset添加两个具有相同from和to的hashset 。 如果没有hashCode()它将被覆盖，第二个将不会被覆盖。