Skip to content

Instantly share code, notes, and snippets.

@dain
Created August 30, 2012 21:31
Show Gist options
  • Save dain/3541632 to your computer and use it in GitHub Desktop.
Save dain/3541632 to your computer and use it in GitHub Desktop.
package org.weakref.algorithms.graph;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import static java.lang.String.format;
import static java.util.Arrays.asList;
public class DepthFirstSearch
{
public static void depthFirstSearch(Graph graph, TraversalCallback callback)
{
Map<Node, Integer> discovery = new HashMap<Node, Integer>();
int count = 0;
for (Node node : graph.getNodes()) {
if (!discovery.containsKey(node)) {
Deque<Node> stack = new ArrayDeque<Node>(asList(node));
discovery.put(node, ++count);
callback.before(node, count);
while (!stack.isEmpty()) {
Node top = stack.peek();
boolean doneWithBranch = true;
for (Node child : top.getChildren()) {
if (discovery.containsKey(child) && discovery.get(child) <= discovery.get(top)) {
callback.cycleDetected(top, child);
}
if (!discovery.containsKey(child)) {
stack.push(child);
discovery.put(child, ++count);
callback.before(child, count);
doneWithBranch = false;
}
}
if (doneWithBranch) {
Node visited = stack.pop();
callback.after(visited, discovery.get(visited), ++count);
}
}
}
}
}
public static void main(String[] args)
{
Graph graph = new Graph();
Node shirt = new Node("shirt");
Node watch = new Node("watch");
Node undershorts = new Node("undershorts");
Node socks = new Node("socks");
Node pants = new Node("pants");
Node shoes = new Node("shoes");
Node belt = new Node("belt");
Node tie = new Node("tie");
Node jacket = new Node("jacket");
undershorts.addChild(pants);
undershorts.addChild(shoes);
pants.addChild(shoes);
pants.addChild(belt);
shirt.addChild(tie);
shirt.addChild(belt);
tie.addChild(jacket);
belt.addChild(jacket);
graph.addNode(shirt);
graph.addNode(watch);
graph.addNode(undershorts);
graph.addNode(socks);
// Node u = new Node("u");
// Node v = new Node("v");
// Node w = new Node("w");
// Node x = new Node("x");
// Node y = new Node("y");
// Node z = new Node("z");
//
// u.addChild(x);
// u.addChild(v);
// v.addChild(y);
// w.addChild(z);
// x.addChild(v);
// y.addChild(x);
// z.addChild(z);
//
// graph.addNode(u);
// graph.addNode(w);
// graph.addNode(w);
// graph.addNode(x);
// graph.addNode(y);
// graph.addNode(z);
depthFirstSearch(graph, new TraversalCallback()
{
@Override
public void before(Node node, int discoveryTime)
{
System.out.println(format("before (%d): %s", discoveryTime, node));
}
@Override
public void after(Node node, int discoveryTime, int visitTime)
{
System.out.println(String.format("after (%d/%d): %s", discoveryTime, visitTime, node));
}
@Override
public void cycleDetected(Node node, Node child)
{
System.out.println(format("cycle detected: %s -> %s", node, child));
}
});
}
}
package org.weakref.algorithms.graph;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import static java.lang.String.format;
public class TopologicalSort
{
public static List<Node> topologicalSort(Graph graph)
{
final Deque<Node> stack = new ArrayDeque<Node>();
DepthFirstSearch.depthFirstSearch(graph, new TraversalCallback()
{
@Override
public void before(Node node, int discoveryTime) { }
@Override
public void after(Node node, int discoveryTime, int visitTime)
{
stack.push(node);
}
@Override
public void cycleDetected(Node node, Node child)
{
throw new IllegalArgumentException(format("cycle detected at %s -> %s", node, child));
}
});
return new ArrayList<Node>(stack);
}
public static void main(String[] args)
{
Graph graph = new Graph();
Node u = new Node("u");
Node v = new Node("v");
Node w = new Node("w");
Node x = new Node("x");
Node y = new Node("y");
Node z = new Node("z");
u.addChild(x);
u.addChild(v);
v.addChild(y);
w.addChild(z);
x.addChild(v);
graph.addNode(u);
graph.addNode(w);
graph.addNode(w);
graph.addNode(x);
graph.addNode(y);
graph.addNode(z);
System.out.println(topologicalSort(graph));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment