Пример ориентированного графа и кода топологической сортировки

Вот простая реализация первого алгоритма со страницы Википедии о топологической сортировке:

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

Реализация, которую я сделал на основе второго варианта на странице википедии: 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();
    }
}

Вы также можете использовать сторонние проекты с открытым исходным кодом, такие как 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<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();
}

А вот один пример использования:

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

Две дополнительные функции (или сложности) в моем коде: мне нужно было поддерживать циклы (циклы) в моем случае, чтобы, если в графе есть циклы, он упорядочивал "наилучшие усилия". Это поведение управляется флагом, переданным конструктору. В любом случае вы можете (должны) вызвать 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, я добавил несколько модульных тестов, чтобы придать дополнительную уверенность себе и другим в использовании. Надеюсь это поможет...

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

Вам также необходимо переопределить функцию hashCode(), так как вы используете HashSet в краях.

В противном случае это вызовет неожиданные ошибки.

EXP: добавьте два экземпляра с одинаковыми значениями from и to в файл hashset. Второй не будет перезаписан без hashCode(), который должен быть перезаписан.