topological_sort.H File Reference

Topological sorting algorithms for directed acyclic graphs (DAGs). More...

#include <tpl_dynListQueue.H>
#include <tpl_graph.H>

Include dependency graph for topological_sort.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Topological_Sort< GT, Itor, SA >
	Computes topological ordering using depth-first search. More...
class	Aleph::Q_Topological_Sort< GT, Itor, SA >
	Computes topological ordering using breadth-first search (Kahn's algorithm). More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Topological sorting algorithms for directed acyclic graphs (DAGs).

This header provides two implementations of topological sorting:

1. Topological_Sort: Uses depth-first search with postfix ordering. Visits nodes recursively and inserts them in reverse postorder.
2. Q_Topological_Sort: Uses breadth-first search (Kahn's algorithm). Repeatedly removes source nodes (in-degree 0) and updates degrees. Also provides rank-based ordering for parallel execution.

Both algorithms assume the input is a DAG. Behavior is undefined if the graph contains cycles.

Author

Leandro Rabindranath León

Definition in file topological_sort.H.