Topological Sort: Ordering tasks with dependencies. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <tpl_graph.H>
#include <topological_sort.H>
#include <tclap/CmdLine.h>

Include dependency graph for topological_sort_example.C:

Typedefs
using	TaskNode = Graph_Node< string >

using	DependencyArc = Graph_Arc< int >

using	TaskGraph = List_Digraph< TaskNode, DependencyArc >

Functions
TaskGraph	build_project_graph ()
	Build a sample build system dependency graph.

TaskGraph	build_courses_graph ()
	Build a course prerequisites graph.

TaskGraph::Node *	find_task (TaskGraph &g, const string &name)
	Find a node by name.

void	print_graph (TaskGraph &g, const string &title)
	Print the graph structure.

void	demo_dfs_topological_sort (TaskGraph &g, bool verbose)
	Demonstrate DFS-based topological sort.

void	demo_bfs_topological_sort (TaskGraph &g, bool verbose)
	Demonstrate BFS-based topological sort (Kahn's algorithm)

void	demo_build_order ()
	Demonstrate practical application: build order.

void	demo_course_scheduling ()
	Demonstrate practical application: course scheduling.

int	main (int argc, char *argv[])

Detailed Description

Topological Sort: Ordering tasks with dependencies.

This example demonstrates topological sorting of directed acyclic graphs (DAGs), a fundamental algorithm for ordering tasks with dependencies. Topological sort is essential whenever you need to process items in a valid dependency order.

What is Topological Sort?

A topological ordering of a DAG is a linear ordering of vertices such that for every directed edge (u → v), vertex u comes before v in the ordering.

Key properties:

Only works on DAGs (Directed Acyclic Graphs)
If graph has cycles, topological sort is impossible
Multiple valid orderings may exist (not unique)

Example

Graph: A → B → D, A → C → D

Valid orderings:

A, B, C, D
A, C, B, D

Invalid: D, A, B, C (violates A → D dependency)

Algorithms

DFS-based (Topological_Sort)

Strategy: Post-order DFS traversal

Algorithm:

Topological_Sort(G):
  1. Mark all vertices as unvisited
  2. Create empty result list
  3. For each unvisited vertex u:
     DFS(u)
  4. Return reversed result
 
DFS(u):
  1. Mark u as visited
  2. For each neighbor v of u:
     If v not visited:
       DFS(v)
  3. Add u to result (post-order)

Key insight: Add vertex to result AFTER processing all descendants

Time complexity: O(V + E) Space complexity: O(V) for recursion stack

BFS-based / Kahn's Algorithm (Q_Topological_Sort)

Strategy: Iteratively remove sources (vertices with no incoming edges)

Algorithm:

Kahn_Topological_Sort(G):
  1. Compute in-degree for all vertices
  2. Queue all vertices with in-degree = 0
  3. While queue not empty:
     a. Remove vertex u from queue
     b. Add u to result
     c. For each neighbor v of u:
        Decrement in-degree[v]
        If in-degree[v] == 0:
          Add v to queue
  4. If result.size() != V:
     Graph has cycle (error)

Key insight: Process vertices with no dependencies first

Time complexity: O(V + E) Space complexity: O(V) for queue

Comparison

Aspect	DFS-based	Kahn's (BFS)
Approach	Post-order DFS	Remove sources
Cycles	Does not detect cycles; output may violate constraints	Can indicate cycles: if output size < V, graph is not a DAG
Order	Depth-first	Breadth-first
Implementation	Recursive	Iterative
Best for	General use	When cycle indication needed

Real-World Applications

Build Systems

Make, CMake: Compile source files in dependency order
Gradle, Maven: Build projects respecting module dependencies
Docker: Build images in dependency order

Package Management

apt, yum: Install packages respecting dependencies
npm, pip: Install packages in correct order
Linux kernel: Module loading order

Task Scheduling

Project management: Schedule tasks respecting dependencies
Workflow engines: Execute steps in valid order
CI/CD pipelines: Run jobs in dependency order

Course Prerequisites

University: Order courses by prerequisites
Online learning: Course completion paths
Certification: Prerequisite ordering

Spreadsheets

Excel, Google Sheets: Evaluate cells in dependency order
Formula evaluation: Compute dependent cells first

Compilers

Dependency analysis: Process declarations before uses
Module loading: Load modules in dependency order

Cycle Detection

Important: Topological sort only works on DAGs!

If graph has cycles:

DFS-based: Output is not guaranteed to be a valid topological order
Kahn's: Result will typically have fewer than V vertices

To detect cycles:

Use Kahn's algorithm: If the produced ordering has fewer than V vertices, a cycle exists
Or run a dedicated cycle/SCC algorithm before topological sort

Complexity

Operation	Time	Space
Topological sort	O(V + E)	O(V)
Cycle/SCC detection (separate)	O(V + E)	O(V)

Usage Examples

# Run all demos (default if no demo flags are given)
./topological_sort_example
 
# Run specific demo
./topological_sort_example --build
./topological_sort_example --courses
 
# Verbose output
./topological_sort_example --verbose