Sample Directed Graph and Topological Sort Code

Question

Hello
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) Thanks

Answer 1

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.

Answer 2

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()));
    }
  }
}