Topological Sort

title: Topological Sorting excerpt: This covers implementation of topological sorting of a graph.

The vertices in a graph can have dependencies that needs to be satisified before we can perform the work in a given vertex. A partial ordering is a set of dependencies that defines an ordering relationship for some but not necessarily all the objects in a set. The partial ordering must be extended to a complete ordering in order to perform the tasks in the right order.

Topological sorting is the process of extending a partial ordering to a full ordering in a graph. One way to extend a partial ordering is simple. If the tasks can be completed in a valid order, there must be some task with with no prerequisites that can be performed first. Find that task, add it to the extended ordering and remove it from the graph. Then repeat those steps, finding another task with no prerequisites, adding it to the extended ordering and removing it from the graph until all the tasks have been completed.

If you reach a point where every remaining task has a prerequisite, then the tasks have a circular dependency so the partial ordering cannot be extended to a full ordering.

Topological Sort of a directed graph is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex V, U comes before V in the ordering.

Given a directed graph, find the topological ordering of its vertices. The input is given as the vertices and the edges of the graph. There are many valid topological ordering of the graph.

The topological sort provides a partial ordering among the vertices of the graph such that if there is an edge from U to V then U ≤ V i.e., U comes before V in the ordering.

Let’s look at some basic terminology related to topological sort:

Source: Any node that has no incoming edge and has only outgoing edges. Sink: Any node that has only incoming edges and no outgoing edge.

So, topological ordering starts with one of the sources and ends at one of the sinks.

A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can use Breadth First Search traversal. We will start with all the sources, save it in a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

Implementation

Initialization

We will store the graph in Adjacency Lists, each parent vertex will have a list containing all of its children. We will use a HashMap where the ‘key’ will be the parent vertex number and the value will be a List containing children vertices.

To find the sources, we will use a HashMap to count the in-degrees i.e., count of incoming edges of each vertex. Any vertex with ‘0’ in-degree will be a source.

Build the graph and find in-degrees of all vertices

Build the graph from the input and find in-degrees of all vertices. Populate the in-degrees hash table.

Find all Sources

All vertices with 0 in-degrees will be the sources and it will be stored in a queue.

Sort

For each source:

  1. Add it to the sorted list.
  2. Get all of its children from the graph.
  3. Decrement the in-degree of each child by 1.
  4. If a child’s in-degree becomes 0, add it to the sources Queue.
  5. Repeat step 1, until the source queue becomes empty.

Time Complexity

In step 4, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity will be O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.

Space Complexity

The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list.

Language Agnostic Coding Drills

Here is how we can break down the Topological Sort Algorithm:

  1. Understanding of Graphs: In topological sorting, we primarily deal with directed acyclic graphs (DAGs). The learner needs to understand what graphs are, how they are represented (adjacency list, adjacency matrix), and what makes a graph directed and acyclic.

  2. Graph Creation: Understand how to add edges to a graph and form a directed acyclic graph (DAG).

  3. Depth-First Search (DFS): Topological sort uses the Depth-First Search algorithm as its backbone. DFS starts at a given node (selecting some arbitrary node if the graph is disconnected), and explores as far as possible along each branch before backtracking.

  4. Stack Data Structure: Understand the concept of a stack, how to push and pop elements. The stack is used in the implementation of the Depth-First Search (DFS) in topological sorting.

  5. Tracking Visited Nodes: Learning to keep track of visited nodes, which is a critical part in avoiding cycles in a graph traversal.

  6. Implementing Topological Sort: Putting it all together to implement the topological sort algorithm. This algorithm returns a list of nodes such that for every directed edge uv from node u to node v, u comes before v in the ordering.

  7. Multiple Valid Outputs: Understand that in topological sorting, multiple correct answers are possible, and it does not always return a unique sort order.

  8. Applications of Topological Sort: Understand the applications of topological sort in real-world scenarios, like task scheduling, determining the order of compilation tasks to perform in makefiles, data serialization, etc.

Topological sort cannot be applied to graphs with cycles, and it is crucial to detect and manage such scenarios.

Solution for Coding Drills in Python

Let’s take each of the learning units and provide a coding drill in Python:

  1. Understanding of Graphs:

    Here, let’s create a graph and add some nodes:

    1
2
3
4
5
6
7

    graph = {"A": ["B", "C"],
         "B": ["D", "E"],
         "C": ["F"],
         "D": [],
         "E": ["F"],
         "F": []}
print(graph)

  2. Graph Creation:

    This example shows how to create a directed graph using adjacency lists:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    class Graph:
    def __init__(self, nodes):
        self.adj_list = {node: [] for node in nodes}

    def add_edge(self, source, target):
        self.adj_list[source].append(target)

nodes = ["A", "B", "C", "D", "E", "F"]
g = Graph(nodes)
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("B", "E")
g.add_edge("C", "F")
g.add_edge("E", "F")
print(g.adj_list)

  3. Depth-First Search (DFS):

    Let’s implement the DFS algorithm for our created graph:

    1
2
3
4
5
6
7
8
9

    def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

visited = dfs(graph, "A", [])
print(visited)

  4. Stack Data Structure:

    This is a simple exercise of creating a stack and using push and pop operations:

    1
2
3
4
5
6

    stack = []
stack.append("A")
stack.append("B")
stack.append("C")
print(stack.pop())
print(stack)

  5. Tracking Visited Nodes:

    In our DFS algorithm above, we’ve kept track of the visited nodes. No separate drill for this.

  6. Implementing Topological Sort:

    Now, let’s implement the topological sorting. It’s a bit complex, as it brings together all the concepts we learned above:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

    def topological_sort(graph):
    visited = set()
    stack = []

    def helper(node):
        visited.add(node)
        for n in graph[node]:
            if n not in visited:
                helper(n)
        stack.append(node)

    for node in graph:
        if node not in visited:
            helper(node)

    return stack[::-1]  # return in reverse order

print(topological_sort(graph))

  7. Multiple Valid Outputs:

    No separate drill for this concept, it’s more about understanding that the output of topological sorting is not unique and depends on the ordering of the nodes.

  8. Applications of Topological Sort:

    No specific code for this point. It’s about understanding the use cases of the topological sort in real-world problems.

Replace graph with the actual graph object in your code.