topological_sort_demo

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Filename: topological_sort_demo.py
# Version: 1.0.0
# Author: Jeoi Reqi

"""
Description:

    - Topological sorting arranges the vertices of a directed graph in a linear order.
    - This ensures that for every directed edge UV from vertex U to vertex V, vertex U precedes vertex V in the ordered sequence.
    - Topological Sorting is feasible only in Directed Acyclic Graphs (DAGs), where no cycles exist among the vertices.
    - Kahn's Algorithm is a common method for topological sorting.
    - It involves iteratively removing nodes with no incoming edges and subsequently removing their outgoing edges from the graph.

Requirements:
    - Python 3.x

Functions:
    - topological_sort(input_graph):
        Perform topological sorting on the given directed graph `input_graph` using Kahn's Algorithm.

Usage:
    - Run the script to see an example of topological sorting in action.

Additional Notes:
    - This implementation assumes the input graph `input_graph` is represented as a dictionary.
    - Keys are vertices and values are lists of vertices they have directed edges to.
    - Returns a list representing the topological order of vertices if the graph is a Directed Acyclic Graph (DAG).
    - If not a DAG it returns an error message indicating the presence of cycles in the graph.

Example:
    >>> example_graph = {
    ...     'A': ['B', 'C'],
    ...     'B': ['D', 'E'],
    ...     'C': ['F'],
    ...     'D': [],
    ...     'E': ['F'],
    ...     'F': [],
    ...     'G': ['H'],
    ...     'H': ['I'],
    ...     'I': []
    ... }
    >>> print(topological_sort(example_graph))
    ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
"""

from collections import deque

def topological_sort(input_graph):
    """
    Perform topological sorting on the given directed graph `input_graph` using Kahn's Algorithm.

    Args:
        input_graph (dict): A dictionary representing the directed graph. Keys are vertices,
                            and values are lists of vertices they have directed edges to.

    Returns:
        list or str: A list representing the topological order of vertices if the graph
                     is a Directed Acyclic Graph (DAG), otherwise returns an error message
                     indicating the presence of cycles in the graph.
    """
    # Calculate in-degree (number of incoming edges) for each node
    in_degree = {u: 0 for u in input_graph}  # Initialize in-degree as 0 for all vertices
    for u in input_graph:
        for v in input_graph[u]:
            in_degree[v] += 1

    # Queue for all nodes with no incoming edge
    queue = deque([u for u in input_graph if in_degree[u] == 0])

    top_order = []  # List to store the topological order

    while queue:
        # Sort vertices with the same in-degree lexicographically
        queue = deque(sorted(queue))

        u = queue.popleft()  # Choose the vertex with no incoming edges
        top_order.append(u)

        # Decrease in-degree by 1 for all its neighboring nodes
        for v in input_graph[u]:
            in_degree[v] -= 1
            # If in-degree becomes zero, add it to the queue
            if in_degree[v] == 0:
                queue.append(v)

    # Check if there was a cycle
    if len(top_order) != len(input_graph):
        return "The graph has at least one cycle and cannot be topologically sorted."
    else:
        return top_order

if __name__ == "__main__":
    # Example usage
    example_graph = {
        'A': ['B', 'C'],
        'B': ['D', 'E'],
        'C': ['F'],
        'D': [],
        'E': ['F'],
        'F': [],
        'G': ['H'],
        'H': ['I'],
        'I': []
    }

    # Print the example graph
    print("\n\t\tExample Graph:\n\t\t--------------")
    for vertex in example_graph:
        print(f"\t\t{vertex}: {example_graph[vertex]}")

    # Perform topological sort and print the result
    print("\n\t\tTopological Sort:\n\t\t-----------------")
    sorted_order = topological_sort(example_graph)
    print("\t       ", sorted_order)