Java 示例有向图和拓扑排序代码

Sample Directed Graph and Topological Sort Code

提问by

Anyone know where I can obtain a sample implementation of a Directed Graph and sample code for performing a topological sort on a directed graph? (preferably in Java)

任何人都知道我可以在哪里获得有向图的示例实现和在有向图上执行拓扑排序的示例代码？（最好是在 Java 中）

回答by leonbloy

Here goes a implementation I did some time ago:

这是我前段时间做的一个实现：

/**
 * 
 * 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<T extends DirectedGraphNode> {

    private final boolean permitLoops;
    private final Collection<T> graph; // original graph. this is not touched.
    private final List<T> sorted = new ArrayList<T>(); // result
    private final Set<T> visited = new HashSet<T>(); // auxiliar list
    private final Set<T> withLoops = new HashSet<T>();

    // auxiliar: all succesors (also remote) of each node; this is only used if permitLoops==true
    private HashMap<T, Set<T>> succesors = null;

    public TopologicalSorter(Collection<T> 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<T>());
        }
    }

    private void init() {
        sorted.clear();
        visited.clear();
        withLoops.clear();
        // build succesors map: only it permitLoops == true 
        if( permitLoops ) {
            succesors = new HashMap<T, Set<T>>();
            HashMap<T, Set<T>> addTo = new HashMap();
            for( T n : graph ) {
                succesors.put(n, new HashSet<T>());
                addTo.put(n, new HashSet<T>());
            }
            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<T> 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<T> getSorted() {
        return sorted;
    }

    public Set<T> 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<DirectedGraphNode> getPredecessors();
}

And here one example of use:

这是一个使用示例：

public class TopologicalSorterExample {

    public static class Node implements DirectedGraphNode {
        public final String x;
        public ArrayList<DirectedGraphNode> antec = new ArrayList<DirectedGraphNode>(); // immediate antecesors
        public Node(String x) {this.x= x;}
        public Collection<DirectedGraphNode> getPredecessors() {
            return antec;
        }
        public String toString() {
            return x;
        }
    }

    public static void main(String[] args) {
        List<DirectedGraphNode> graph = new ArrayList<DirectedGraphNode>();
        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();
    }
 }

Two additional features (or complications) in my code: I needed to support loops (cycles) in my case, so that if the graph has loops it makes some "best effort" ordering. This behaviour is controlled by a flag passed to the constructor. In any case, you can (should) call hadLoops()to ask if there were cycles detected. Besides, I wanted the sorting algorithm to prefer the original ordering in case of freedom.

我的代码中的两个附加功能（或复杂性）：在我的情况下，我需要支持循环（循环），以便如果图形具有循环，它会进行一些“尽力而为”的排序。此行为由传递给构造函数的标志控制。在任何情况下，您都可以（应该）打电话hadLoops()询问是否检测到循环。此外，我希望排序算法在自由的情况下更喜欢原始排序。

回答by M. Jessup

Here is a simple implementation of the first algorithm from the Wikipedia page on Topological Sort:

这是维基百科关于拓扑排序的第一个算法的简单实现：

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<Edge> inEdges;
    public final HashSet<Edge> outEdges;
    public Node(String name) {
      this.name = name;
      inEdges = new HashSet<Edge>();
      outEdges = new HashSet<Edge>();
    }
    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<Node> L = new ArrayList<Node>();

    //S <- Set of all nodes with no incoming edges
    HashSet<Node> S = new HashSet<Node>(); 
    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<Edge> 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()));
    }
  }
}

回答by tugcem

You can also use third party open source projects, such as JGraphT. It provides many simple and complicated graph structures and their visual representation. Also you dont have to deal with structural issues with this way.

您还可以使用第三方开源项目，例如JGraphT。它提供了许多简单和复杂的图形结构及其可视化表示。此外，您不必以这种方式处理结构性问题。

回答by Jeremy

You need to override hashCode()function as well since you are using HashSetin edges.

hashCode()由于您HashSet在边缘使用，因此您还需要覆盖功能。

Otherwise, it will raise unexpected bugs.

否则，它会引发意想不到的错误。

EXP: Add two instances with same from and to into the hashset. The 2nd one won't be overritten without hashCode()which it's supposed to be overwritten.

EXP：将两个具有相同 from 和 to 的实例添加到hashset. 第二个不会被覆盖hashCode()，否则它应该被覆盖。

回答by hart

Agree with jeremy.

同意杰里米。

I think here is a implementation to get the hashcode based on effective Java: http://www.javapractices.com/topic/TopicAction.do?Id=28

我认为这是基于有效 Java 获取哈希码的实现：http: //www.javapractices.com/topic/TopicAction.do?Id =28

How about to add below method to override the hashcode?

如何添加以下方法来覆盖哈希码？

@Override
    public int hashCode(){
         if (fHashCode == 0) {
              int result = HashCodeUtil.SEED;
              result = HashCodeUtil.hash(result, from);
              result = HashCodeUtil.hash(result, to);
         }
         return fHashCode;
    }

回答by user3267322

An implementation I did based on second alternative on wikipedia page: http://en.wikipedia.org/wiki/Topological_sorting

我基于维基百科页面上的第二个替代方案所做的实现：http: //en.wikipedia.org/wiki/Topological_sorting

public class Graph {

    Hashtable<Node, ArrayList<Node>> adjList = new Hashtable<Node, ArrayList<Node>>();
    ArrayList<Node> nodes = new ArrayList<Node>();
    LinkedList<Node> topoSorted;

    public Graph() {}

    public void add(Node node) { 
        if (adjList.contains(node)) { 
            return;
        } else { 
            adjList.put(node, new ArrayList<Node>());
            nodes.add(node);
        }
    }

    public void addNeighbor(Node from, ArrayList<Node> 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<Node>();

        /* Use set to keep track of permanently visited nodes
         * in constant time. Does have pointer overhead */
        HashSet<Node> visited = new HashSet<Node>();

        /* 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<Node> 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 (i.e. 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<Node> inNodes = new ArrayList<Node>();


        public Node (String value) { 
            this.value = value;
        }
    }

    public static void main(String[] args) { 
        Graph g = new Graph();
        g.instantiateGraph();
    }
}

回答by rimsky

Just to augment the great solution by @templatetypedef a bit, I added some unit tests to give some added confidence for myself and others to use. Hope this helps...

只是为了增加@templatetypedef 的出色解决方案，我添加了一些单元测试，以增加我自己和其他人使用的信心。希望这可以帮助...

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<String> orderedLayers = TopologicalSort.sort(null);
    }

    @Test
    public void testEmptyGraph() {
        final DirectedGraph<String> dag = new DirectedGraph<String>();        
        final List<String> orderedLayers = TopologicalSort.sort(dag);
        assertEquals(0, orderedLayers.size());
    }

    @Test
    public void testSingleVertex() {
        final DirectedGraph<String> dag = new DirectedGraph<String>();
        dag.addNode("a");
        final List<String> orderedLayers = TopologicalSort.sort(dag);
        assertEquals(1, orderedLayers.size());
        assertTrue(orderedLayers.contains("a"));
    }

    @Test
    public void testMultipleVertices() {
        final DirectedGraph<String> dag = new DirectedGraph<String>();
        dag.addNode("a");
        dag.addNode("b");
        final List<String> 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<String> dag = new DirectedGraph<String>();
        dag.addNode("a");
        dag.addEdge("a", "b");
    }

    @Test
    public void testSimpleDag() {
        final DirectedGraph<String> dag = new DirectedGraph<String>();
        dag.addNode("b");        
        dag.addNode("a");
        dag.addEdge("a", "b");
        final List<String> 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<String> dag = new DirectedGraph<String>();
        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<String> 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<String> dag = new DirectedGraph<String>();
        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<String> orderedLayers = TopologicalSort.sort(dag);
    }
}