Topological Sort for Graph in C#

gistfile1.txt

/*

Given a directed graph, find the topological ordering of its vertices.

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0

Underlying concepts:

The basic idea behind the topological sort is to provide 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).

1. SOURCE: Any node that has no incoming edge and has only outgoing edges is called a Source.
2. SINK: Any node that has only incoming edges and no outgoing edge is called a Sink.
3. So, we can say that a topoligical ordering starts with one of the Sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directe 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.

Approach:

1. Traverse the graph in a BFS approach.
2. Start with all Sources, and in stepwise fashion, save all Sources to a Sorted List.
3. Remove all Sources and their edges from the graph.
4. After removing edges, we will have new Sources, and we will repeat the above process until all of the vertices are visited.

Implementation:

1. Initialization:

1a. Store the graph in Adjacency Lists, which means that each parent vertex will have a list containing all of its children.
We will do this using a HashMap where the 'key' will be the parent vertex number and the value will be a List containing children vertices. i.e. Dictionary<int, List<int>>
1b. To find the Sources, we will keep a HashMap to count the in-degrees, i.e.e count of incoming edges of each vertex. Any vertex with '0' in-degree is a Source.

2. Build the graph and find in-degrees of all vertices
2a. We will build the graph from the input and populate the in-degrees (count of incoming edges) HashMap.

3. Find all Sources
3a. All vertices with '0' in-degrees will be our Sources and we will store them in a Queue.

4. Sort
4a. For each Source, do the following things:
- Add it to the sorted list
- Get all of its children from the graph
- Decrement the in-degree of each child by 1
- If a child's in-degree becomes '0', add it to the sources Queue.
4b. Repeat Step 1 until the Queue of Sources is empty

*/

using System;
using System.Collections;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        int vertices = 4;
        int[,] edges = new int[,] {{3,2}, {3,0}, {2,0}, {2,1}};
        
        // Console.WriteLine(edges.GetLength(0));
        List<int> result = SortGraph(vertices, edges);
        foreach (int node in result)
        {
            Console.WriteLine(node);
        }
    }
    
    public static List<int> SortGraph (int vertices, int[,] edges)
    {
        // 0. Initialize Sorted List
        List<int> sortedOrder = new List<int>();
        if (vertices <= 0)
        {
            return sortedOrder;
        }
        
        // 1. Initialize the Graph (O(V))
        
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); // key = node, values = list of it's adjacent nodes
        Dictionary<int, int> inDegrees = new Dictionary<int, int>(); // key = vertex, value = number of incoming edges
        
        for (int i  = 0; i < vertices; i++)
        {
            inDegrees.Add(i , 0);
            graph.Add(i, new List<int>());
        }
        
        // 2. Build the Graph (O(E))
        
        for (int i = 0; i < edges.GetLength(0); i++)
        {
            int parent = edges[i,0]; // left node of directed edge
            int child = edges[i,1]; // right node of directed edge
            
            graph[parent].Add(child); // put the child into it's parent's adjacency list
            inDegrees[child] += 1;
        }
        
        // 3. Find all Sources and add to Queue
        
        Queue<int> sources = new Queue<int>();
        
        foreach (var entry in inDegrees)
        {
            if (entry.Value == 0)
            {
                sources.Enqueue(entry.Key);
            }
        }
        
        // 4. Sort
        
        // For each Source, add it to Sorted Order
        while (sources.Count > 0)
        {
            int source = sources.Dequeue();
            sortedOrder.Add(source);
            
            // Subtract one from all of it's children's inDegrees value
            foreach (int child in graph[source])
            {
                inDegrees[child] -= 1;
                
                // If a child's in-degree becomes zero, add to sources queue
                if (inDegrees[child] == 0)
                {
                    sources.Enqueue(child);
                }
            }
        }
        
        // 5. Check for Cycles
        // Check if there is a topological sort by seeing if the graph has a cycle
        if (sortedOrder.Count != vertices)
        {
            return new List<int>();
        }
        
        return sortedOrder;
        
    }
}