Topological sort

• It is an ordering of vertices in a directed acyclic graph in which each node comes before all the nodes to which it has outgoing edges

• Topological sort for this graph will be : A, C, E, B, D

  

• We first find a vertex which has no incoming edge (Indegree = 0)

• Remove A, reduce the indegree of all its neighbors

• The next vertex in this sort the one with indegree 0

Indegree

• Number of inward directed graph edges for a given vertex

• If there were no vertices with 0 indegree, then there would have been no topological sort

  • A = 0

  • B = 2

  • C = 1

  • E = 1

  • D = 2

Complexity

• Running time for topological sort is O(V + E)

• Each edge and every vertex visited once

Implementation

Indegree of adjacency list

public int getIndegree(int v) {
    if (v < 0 || v >= numVertices) {
        throw new IllegalArgumentException("Vertex number is not valid");
    }
    int indegree = 0;
    for (int i = 0; i < numVertices; i++) {
        if (getAdjacentVertices(i).contains(v)) {
            indegree++;
        }
    }
    return indegree;
}

override
public int getIndegree(int v) {
    if (v < 0 || v >= numVertices) {
        throw new IllegalArgumentException("Vertex number is not valid");
    }
    int indegree = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if (getAdjacentMatrix[i][v] != 0) {
            indegree++;
        }
    }
    return indegree;
}

public static List<Integer> sort(Graph graph) {
    LinkedList<Integer> queue = new LinkedList<>();
    Map<Integer, Integer> indegreeMap = new HashMap<>();
    
    for (int vertex = 0; vertex < graph.getNumVertices(); vertex++) {
        int indegree = graph.getIndegree(vertex);
        indegreeMap.put(vertex, indegree);
        if (indegree == 0) {
            queue.add(vertex);
        }
    }
    
    List<Integer> sortedList = new ArrayList<>();
    while (!queue.isEmpty()) {
        int vertex = queue.pollLast();
        sortedList.add(vertex);
        
        List<Integer> adjancentVertices = graph.getAdjancentVertices(vertex);
        for (int adjancentVertex : adjancentVertices) {
            int updatedIndegree = indegreeMap.get(adjancentVertex) - 1;
            indegreeMap.remove(adjancentVertex);
            indegreeMap.put(adjancentVertex, updatedIndegree);
            if (updatedIndegree == 0) {
                queue.add(adjancentVertex);
            }
        }
    }
    
    if (sortedList.size() != graph.getNumVertices()) {
        throw new RuntimeException("Vertex number is not valid");
    }
    return sortedList;
}

Student schedule

• We have 2 lists

  • List of courses

  • List od pre-reqs for each course

• Pre-reqs are edges from one course to another - it is a relationship

• All nodes with indegree = 0 are potential courses the student could start with

  • There are many schedule possible

public static List<String> order(List<String> courseList, Map<String, List<String>> prereqs) {
    Graph courseGraph = new AdjancentMatrixGraph(courseList.size(), Graph.GraphType.DIRECTED);
    
    Map<String, Integer> courseMap = new HashMap<>();
    Map<Integer, String> idCourseMap = new HashMap<>();
    
    for (int i = 0; i < courseList.size(); i++) {
        courseMap.put(courseList.get(i), i);
        idCourseMap.put(i, courseList.get(i));
    }
    
    for (Map.Entry<String, List<String>> prereq : prereq.entrySet()) {  
        for (String course : prereq.getValue()) {
            courseGraph.addEdge(courseMap.get(prereq.getKey()),
                courseMap.get(course));
        }
    }
    
    List<Integer> courseIdList = TopologicalSort(courseGraph);
    List<Integer> courseScheduleList = new ArrayList<>();
    
    
    for (int courseId : courseIdList) {
        courseScheduleList.add(idCourseMap.get(courseId));
    }
    return courseScheduleList;
}