Beispiel gerichteter Graph und topologischer Sortiercode

Question

Wer weiß, wo ich eine Beispielimplementierung eines gerichteten Graphen und Beispielcode für eine topologische Sortierung auf einem gerichteten Graph erhalten kann? (Vorzugsweise in Java)

Answer 1

geht hier eine Implementierung ich vor einiger Zeit tat

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

Und hier ein Beispiel für die Verwendung:

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

Zwei zusätzliche Funktionen (oder Komplikationen) in meinem Code : Ich musste Schleifen (Zyklen) in meinem Fall unterstützen, so dass, wenn der Graph Schleifen hat, macht es einige "bestem Aufwand" Bestellung. Dieses Verhalten wird durch ein Flag gesteuert, das an den Konstruktor übergeben wird. In jedem Fall können (sollten) Sie hadLoops() anrufen, um zu fragen, ob Zyklen erkannt wurden. Außerdem wollte ich, dass der Sortieralgorithmus im Falle der Freiheit die ursprüngliche Reihenfolge vorzieht.

Answer 2

Hier ist eine einfache Implementierung des ersten Algorithmus aus den 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())); 
    } 
    } 
} 

Answer 3

I this implementation codierte vor ein paar Wochen. Es ist in Java und verwendet eine benutzerdefinierte gerichtete Grafikklasse. Hoffentlich sind die Kommentare nützlich!

Answer 4

Sie können auch Open-Source-Projekte von Drittanbietern verwenden, z. B. JGraphT. Es bietet viele einfache und komplizierte Graphstrukturen und ihre visuelle Darstellung. Auch müssen Sie sich auf diese Weise nicht mit strukturellen Problemen auseinandersetzen.

Answer 5

Sie müssen auch die hashCode() Funktion außer Kraft setzen, da Sie HashSet in Kanten verwenden.

Andernfalls werden unerwartete Fehler auftreten.

EXP: Fügen Sie zwei Instanzen mit gleichen von und in die hashset. Die zweite wird nicht überschrieben ohne hashCode(), die überschrieben werden soll.

Answer 6

Stimmen Sie mit Jeremy überein.

ich hier denke, ist eine Implementierung der Hash-Code basiert auf den effektiven Java zu erhalten: http://www.javapractices.com/topic/TopicAction.do?Id=28

Wie wäre es unter Methode hinzufügen, um den Hash-Code zu überschreiben?

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

Answer 7

Eine Implementierung ich auf der zweiten Alternative auf Wikipedia-Seite basiert hat: 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(); 
    } 
} 

Answer 8

einfach die große Lösung von @templatetypedef ein wenig zu erweitern, habe ich einige Unit-Tests hinzugefügt einige zusätzliche Sicherheit zu geben, für mich und andere zu benutzen. Hoffe, das hilft ...

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