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<class GT, template< typename, class > class Itor = Out_Iterator, class 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 191 of file topological_sort.H.

Constructor & Destructor Documentation

◆ Q_Topological_Sort() [1/2]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 200 of file topological_sort.H.

◆ Q_Topological_Sort() [2/2]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 206 of file topological_sort.H.

Member Function Documentation

◆ operator()() [1/3]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 334 of file topological_sort.H.

References Aleph::maps().

◆ operator()() [2/3]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 355 of file topological_sort.H.

References Aleph::maps(), and Aleph::DynList< T >::swap().

◆ operator()() [3/3]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 346 of file topological_sort.H.

References Aleph::maps(), and Aleph::DynList< T >::swap().

◆ perform()

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 225 of file topological_sort.H.

References Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::DynListQueue< T >::is_empty(), Aleph::maps(), 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.

◆ ranks()

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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