Topologial sort : Java Implementation

Hello Friends,

I am here with you with another algorithm. Its Topological sorting of a directed graph. Suppose we have few tasks which are interdependent. Lets represent this system in a graph. Each task is represented by a Vertex and will be connected to the Vertices with which it has dependency relation. All Vertices connected to a Vertex V with INCOMING edges on V will be the vertices on  which  Vertex V is dependent upon. So all the tasks represented by the such vertices should be performed before task represented by Vertex V is completed.


A such system represented as graph is as below :





Here for example Before task represented by C is performed , Tasks represented by  A and B must be performed as C has dependency on A and B.

Friends Please find below the code for the same. I have used my own custom HashMap and Stack for its implementation, so you can see a basic internal working of HashMap and Stack also.

public class TopologicalSort {

    public static class Graph {
        int maxSize;
        int size;
        Vertex vertices[];
        HashMap map;
        Stack stack;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
            map = new HashMap();
            stack = new Stack(maxSize);
        }

        public static class Vertex {
            char name;
            Neighbour adj;
            State state = State.NEW;

            public Vertex(char name) {
                this.name = name;
            }
        }

        public enum State {
            NEW, INPROGRESS, VISITED
        }

        public static class Neighbour {
            Vertex vertex;
            Neighbour next;

            public Neighbour(Vertex vertex, Neighbour next) {
                this.vertex = vertex;
                this.next = next;
            }
        }

        public void invokeTopologicalSorting() {
            for (int i = 0; i < maxSize; i++) {
                exploreVertex(vertices[i]);
            }
            for (int i = 0; !stack.isEmpty(); i++) {
                System.out.println(stack.pop().name);
            }
        }

        /**
         * 
         * The basic idea in this method is to fully explore the vertex, and
         * check if its any Neighbor has been left un explored, if so then need
         * to explore the Neighbor by recursive call to this method. After fully
         * exploring we need to add the vertex to the stack. Thus first the
         * leaves will be pushed to the stack and then when the vertex is re
         * visited by recurrence stack then we see if there are any more
         * neighbor left un explored , if so we need to repeat the process else
         * we come out of the while loop and push the explored vertex in the
         * stack.
         * 
         * Point to note here is: A vertex if considered a Task has dependencies
         * on the vertices which are connected to it by In-coming edges. So for
         * any Vertex, V we need to explore its neighbor first so that they are
         * pushed to the stack first (and will be popped after the current
         * vertex, V).
         */
        public void exploreVertex(Vertex v) {
            if (v.state != State.VISITED) {
                v.state = State.VISITED;
                Neighbour adj = v.adj;
                while (adj != null) {
                    Vertex neighbour = adj.vertex;
                    if (neighbour.state != State.VISITED) {
                        exploreVertex(adj.vertex);
                    }
                    adj = adj.next;
                }
                stack.push(v);
            }
        }

        public void addVertex(char name) {
            vertices[size++] = new Vertex(name);
            map.put(name, vertices[size - 1]);
        }

        public void addNeighbour(char source, char destination) {
            Vertex sourceV = map.get(source);
            Vertex destinationV = map.get(destination);
            sourceV.adj = new Neighbour(destinationV, sourceV.adj);
        }

        public static class Stack {
            Vertex[] stack;
            int maxSize;
            int top = -1;

            public Stack(int maxSize) {
                this.maxSize = maxSize;
                stack = new Vertex[maxSize];
            }

            public void push(Vertex u) {
                stack[++top] = u;
            }

            public Vertex pop() {
                Vertex v = stack[top];
                stack[top] = null;
                top--;
                return v;
            }

            public boolean isEmpty() {
                return top == -1;
            }
        }

        public static class HashMap {
            int prime = 499;
            MapNode[] map = new MapNode[prime];

            public static class MapNode {
                char key;
                Vertex value;
                MapNode next;

                MapNode(char key, Vertex value, MapNode next) {
                    this.key = key;
                    this.value = value;
                    this.next = next;
                }
            }

            public int index(char key) {
                return hashcode(key) % prime;
            }

            public int hashcode(char key) {
                return 31 * key;
            }

            public boolean put(char key, Vertex value) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return false;
                    }
                    temp = temp.next;
                }
                map[index] = new MapNode(key, value, map[index]);
                return true;
            }

            public Vertex get(char key) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return temp.value;
                    }
                    temp = temp.next;
                }
                return null;
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');
        graph.addVertex('G');
        graph.addVertex('H');
        graph.addNeighbour('A', 'C');
        graph.addNeighbour('B', 'C');
        graph.addNeighbour('B', 'D');
        graph.addNeighbour('C', 'E');
        graph.addNeighbour('D', 'F');
        graph.addNeighbour('E', 'F');
        graph.addNeighbour('E', 'H');
        graph.addNeighbour('F', 'G');
        graph.invokeTopologicalSorting();
    }
}