DepthFirstSearch.java

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

TopologicalSort.java

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

}