Computes topological ordering using breadth-first search (Kahn's algorithm). More...

#include <topological_sort.H>

Public Member Functions
	Q_Topological_Sort (SA &&__sa=SA())
	Constructor with rvalue arc filter.

	Q_Topological_Sort (SA &__sa)
	Constructor with lvalue arc filter.

template<template< class > class List>
List< typename GT::Node * >	perform (const GT &g)
	Compute topological ordering using BFS (Kahn's algorithm).

template<template< class > class RankList = DynList, template< class > class List = DynList>
RankList< List< typename GT::Node * > >	ranks (const GT &g)
	Compute rank-based topological ordering.

void	operator() (const GT &g, DynDlist< DynList< typename GT::Node * > > &list)
	Operator() overload returning ranks as DynDlist of DynList.

void	operator() (const GT &g, DynList< DynList< typename GT::Node * > > &list)
	Operator() overload returning ranks as DynList of DynList.

void	operator() (const GT &g, DynDlist< typename GT::Node * > &list)
	Operator() overload for backward compatibility (flat list).

Private Attributes
SA &	sa

Detailed Description

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Q_Topological_Sort< GT, Itor, SA >

Computes topological ordering using breadth-first search (Kahn's algorithm).

This class performs topological sorting using a queue-based approach. It repeatedly:

Finds all source nodes (in-degree 0)
Removes them from the graph (conceptually)
Updates in-degrees of their successors
Repeats until all nodes are processed

Also provides rank-based ordering where nodes at the same "level" (same topological depth) are grouped together, useful for identifying parallelizable tasks.

Template Parameters

GT	The directed graph type.
Itor	Iterator type for traversing outgoing arcs (default: Out_Iterator).
SA	Arc filter/selector (default: Dft_Show_Arc<GT>).

Definition at line 193 of file topological_sort.H.

Constructor & Destructor Documentation

◆ Q_Topological_Sort() [1/2]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Q_Topological_Sort< GT, Itor, SA >::Q_Topological_Sort ( SA && __sa = SA() )

inline

Constructor with rvalue arc filter.

Parameters

__sa	Arc filter/selector (moved).

Definition at line 202 of file topological_sort.H.

◆ Q_Topological_Sort() [2/2]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Q_Topological_Sort< GT, Itor, SA >::Q_Topological_Sort ( SA & __sa )

inline

Constructor with lvalue arc filter.

Parameters

__sa	Arc filter/selector (referenced).

Definition at line 208 of file topological_sort.H.

Member Function Documentation

◆ operator()() [1/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Q_Topological_Sort< GT, Itor, SA >::operator()	(	const GT &	g,
		DynDlist< DynList< typename GT::Node * > > &	list
	)

inline

Operator() overload returning ranks as DynDlist of DynList.

Parameters

g	The directed acyclic graph.
list	Output list to receive the rank-based ordering.

Definition at line 336 of file topological_sort.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [2/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Q_Topological_Sort< GT, Itor, SA >::operator()	(	const GT &	g,
		DynDlist< typename GT::Node * > &	list
	)

inline

Operator() overload for backward compatibility (flat list).

Parameters

g	The directed acyclic graph.
list	Output list to receive the topological ordering.

Definition at line 357 of file topological_sort.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [3/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Q_Topological_Sort< GT, Itor, SA >::operator()	(	const GT &	g,
		DynList< DynList< typename GT::Node * > > &	list
	)

inline

Operator() overload returning ranks as DynList of DynList.

Parameters

g	The directed acyclic graph.
list	Output list to receive the rank-based ordering.

Definition at line 348 of file topological_sort.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ perform()

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<template< class > class List>

List< typename GT::Node * > Aleph::Q_Topological_Sort< GT, Itor, SA >::perform ( const GT & g )

inline

Compute topological ordering using BFS (Kahn's algorithm).

Uses in-degree counting and a queue to process source nodes, producing a valid topological ordering.

Template Parameters

List	Container type for the result (e.g., DynList, DynDlist).

Parameters

g	The directed acyclic graph.

Returns: A list of nodes in topological order.

Exceptions

std::bad_alloc	If memory allocation fails.
std::domain_error	If g is not a digraph.

Note: This function does not verify that g is acyclic. If g contains cycles, not all nodes will be in the result.

Definition at line 227 of file topological_sort.H.

References Aleph::Dlink::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::DynListQueue< T >::is_empty(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COUNTER, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_counter_nodes(), and Aleph::Q_Topological_Sort< GT, Itor, SA >::sa.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ ranks()

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<template< class > class RankList = DynList, template< class > class List = DynList>

RankList< List< typename GT::Node * > > Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks ( const GT & g )

inline

Compute rank-based topological ordering.

Returns the topological ordering organized by ranks (levels). Each rank contains nodes that can be processed in parallel, as they have no dependencies on each other within the same rank.

Template Parameters