1
\$\begingroup\$

For a course I'm doing I need to get up to speed with Java, but unfortunately only Java 1.6 - here is a topological sorting algorithm in said Java version, for practice reasons:

import java.util.*;

class Graph {
    private Map<Integer, Set<Integer>> adjList = new HashMap<Integer, Set<Integer>>();

    void add(int from, int...to) {
        if (!adjList.containsKey(from)) {
            adjList.put(from, new HashSet<Integer>());
        }

        for (int t : to) {
            adjList.get(from).add(t);
        }
    }

    Map<Integer, Set<Integer>> getAdjList() {
        return adjList;
    }
}

class TopologicalSort {
    private Graph g;
    private HashMap<Integer, Integer> incomingEdges;
    private Set<Integer> onlyNoIncomingEdges;

    TopologicalSort(Graph g) {
        this.g = g;
    }

    private void computeIncomingEdgesLookup() {
        incomingEdges = new HashMap<Integer, Integer>();
        onlyNoIncomingEdges = new HashSet<Integer>();

        Map<Integer, Set<Integer>> a = g.getAdjList();

        for (Map.Entry<Integer, Set<Integer>> e : a.entrySet()) {
            int cur = e.getKey();

            // this node is not yet in the list of nodes that have incoming edges
            // so we assume it maybe has no incoming edges
            if (!incomingEdges.containsKey(cur)) {
                onlyNoIncomingEdges.add(cur);
            }

            for (int i : a.get(cur)) {
                // we found an incoming edge {cur, i} for i,
                // so we need to remove it from the list of nodes that have no incoming
                // edge, if we put it there in a previous iteration (see above)
                onlyNoIncomingEdges.remove(i);

                if (!incomingEdges.containsKey(i)) {
                    incomingEdges.put(i, 1);
                } else {
                    incomingEdges.put(i, incomingEdges.get(i) + 1);
                }
            }
        }
    }

    List<Integer> getSorting() {
        computeIncomingEdgesLookup();

        if (onlyNoIncomingEdges.size() == 0) {
            throw new RuntimeException("Graph has cycles - no nodes found without incoming edges.");
        }

        Map<Integer, Set<Integer>> a = g.getAdjList();
        List<Integer> l = new LinkedList<Integer>();

        while (!onlyNoIncomingEdges.isEmpty()) {
            // pop any entry off from set of nodes that have no incoming edges
            int cur = onlyNoIncomingEdges.iterator().next();
            onlyNoIncomingEdges.remove(cur);

            l.add(cur);

            for (int i : a.get(cur)) {
                // get count of incoming edges for each neighbor of cur
                int cnt = incomingEdges.get(i);

                // since we "remove" the edge {cur, i} (as we remove cur from G),
                // i has one incomingEdges less
                int newCnt = cnt - 1;
                incomingEdges.put(i, newCnt);

                // if i has no more incoming edges, we can add it to the sorting list
                if (newCnt == 0) {
                    onlyNoIncomingEdges.add(i);
                }
            }
        }

        if (l.size() != a.size()) {
            throw new RuntimeException("Graph has cycles - couldn't remove all nodes from G.");
        }

        return l;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.add(5, 11);
        g.add(7, 11, 8);
        g.add(3, 8, 10);
        g.add(11, 2, 9, 10);
        g.add(8, 9);
        g.add(2);
        g.add(9);
        g.add(10);

        // -- client code --
        TopologicalSort t = new TopologicalSort(g);

        try {
            List<Integer> l = t.getSorting();

            System.out.println("Topological sort of G:");

            for (int i : l) {
                System.out.print(i + " ");
            }

            System.out.println();
        } catch (Exception e) {
            System.out.println("FAIL: Can't build topological sorting for G: " + e);
        }
    }
}

The graph for this example looks like the one from the wikipedia page:

enter image description here

The output should be one of the possible, topological sorts for that graph, in this case:

3 5 7 8 11 2 9 10

Any feedback appreciated, but it has to work in Java 1.6 though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.