Tarjan's strongly connected components algorithm

Question

Can anyone suggest to me how I can make this "nicer"? If you can see any glaring details that I could change to speed things up too, that would be great -- though it's not priority.

public class Tarjans {

    private static class Node {
        // -1, -1, our node is unvisited
        // by default.
        public int index = -1, lowLink = -1;
        public String name;

        public Node(String name) {
            this.name = name;
        }

        public String toString() {
            return name;
        }
    }

    // graph representation
    HashMap<String, Node> nodes = new HashMap<>();
    HashMap<String, ArrayList<Node>> graph = new HashMap<>();

    private int index = 0;

    // for a DFS, basically
    private ArrayDeque<Node> visited = new ArrayDeque<>();
    private HashSet<String> stack = new HashSet<>();

    // stores our strongly connected componts
    // from the algorithm pass
    private HashSet<HashSet<Node>> scc = new HashSet<>();

    public HashSet<HashSet<Node>> tarjan() {
        for (Node n : nodes.values()) {
            if (n != null && n.index == -1) {
                strongConnect(n);
            }
        }
        return scc;
    }

    private void strongConnect(Node node) {
        node.index = index;
        node.lowLink = index;
        index += 1;

        visited.push(node);
        stack.add(node.name);

        ArrayList<Node> neighbours = graph.get(node.name);
        if (neighbours != null) {
            neighbours.forEach(n -> {
                if (n.index == -1) {
                    strongConnect(n);
                    node.lowLink = Math.min(node.lowLink, n.lowLink);
                }
                else if (stack.contains(n.name)) {
                    node.lowLink = Math.min(node.lowLink, n.index);
                }
            });
        }

        if (node.lowLink == node.index) {
            HashSet<Node> cycle = new HashSet<>();
            while (true) {
                Node p = visited.pop();
                stack.remove(p.name);
                cycle.add(p);

                if (p == node) {
                    break;
                }
            }
            if (cycle.size() > 1) {
                scc.add(cycle);         
            }
        }
    }

    private void foo() {
        nodes.put("bs", new Node("bs"));
        nodes.put("a", new Node("a"));
        nodes.put("b", new Node("b"));
        nodes.put("c", new Node("c"));

        graph.put("bs", new ArrayList<>(Arrays.asList(nodes.get("a"))));
        graph.put("a", new ArrayList<>(Arrays.asList(nodes.get("b"))));
        graph.put("b", new ArrayList<>(Arrays.asList(nodes.get("c"))));
        graph.put("c", new ArrayList<>(Arrays.asList(nodes.get("a"))));

        HashSet<HashSet<Node>> cycles = tarjan();
        for (HashSet<Node> cycle : cycles) {
            System.out.println("[" + cycle.stream().map(Node::toString).collect(Collectors.joining(",")) + "]");
        }
    }

    public static void main(String[] args) {
        new Tarjans().foo();
    }

}

Answer 1

There is no reason to use String as keys in graph. By default an object can be used as a key in a hashmap based on it's uniqueness.

There is no reason that the values have to be ArrayLists instead just use List.

HashMap<Node, List<Node>> graph = new HashMap<>();

This can clean up the init code as you don't have to do new ArrayList<> and can instead just pass Arrays.asList(nodes.get("a")) directly.

Though having said all that you can just put the List of neighbours straight in the Node and not deal with having to look it up in strongConnect.