Created
July 22, 2011 06:53
-
-
Save wingyplus/1099001 to your computer and use it in GitHub Desktop.
Topology Sorting (convert code from python)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList; | |
public class Node { | |
private LinkedList<Node> edges; | |
private char name; | |
Node(char name) { | |
this.name = name; | |
edges = new LinkedList<Node>(); | |
} | |
public char getName() { | |
return name; | |
} | |
public LinkedList<Node> getEdges() { | |
return edges; | |
} | |
public void addEdge(Node node) { | |
edges.add(node); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.LinkedList; | |
import java.util.List; | |
public class TopologySort { | |
public static void main(String[] args) throws Exception { | |
Node a = new Node("a"); | |
Node b = new Node("b"); | |
Node c = new Node("c"); | |
Node d = new Node("d"); | |
Node e = new Node("e"); | |
a.addEdge(b); // a depends on b | |
a.addEdge(d); // a depends on d | |
b.addEdge(c); // b depends on c | |
b.addEdge(e); // b depends on e | |
c.addEdge(d); // c depends on d | |
c.addEdge(e); // c depends on e | |
//d.addEdge(b); | |
//dep_resolve(a); | |
List<Node> resolved = new LinkedList<Node>(); | |
dep_resolve(a, resolved, new LinkedList<Node>()); | |
for (Node node : resolved) { | |
System.out.print(node.getName() + " "); | |
} | |
} | |
public static void dep_resolve(Node node) { | |
System.out.println(node.getName()); | |
for (Node list : node.getEdges()) { | |
dep_resolve(list); | |
} | |
} | |
public static void dep_resolve(Node node, List<Node> resolved) { | |
for (Node list : node.getEdges()) { | |
if (!resolved.contains(list)) | |
dep_resolve(list, resolved); | |
} | |
System.out.print(node.getName() + " "); | |
resolved.add(node); | |
} | |
public static void dep_resolve(Node node, List<Node> resolved, List<Node> unresolved) throws Exception { | |
unresolved.add(node); | |
for (Node list : node.getEdges()) { | |
if (!resolved.contains(list)) { | |
if (unresolved.contains(list)) | |
throw new Exception ("Circular reference detected: " + node.getName() + " -> " + list.getName()); | |
dep_resolve(list, resolved, unresolved); | |
} | |
} | |
resolved.add(node); | |
unresolved.remove(node); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment