Skip to content

Instantly share code, notes, and snippets.

@wingyplus
Created July 22, 2011 06:53
Show Gist options
  • Save wingyplus/1099001 to your computer and use it in GitHub Desktop.
Save wingyplus/1099001 to your computer and use it in GitHub Desktop.
Topology Sorting (convert code from python)
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);
}
}
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