Aleph::Topological_Sort< GT, Itor, SA > Class Template Reference

Computes topological ordering using depth-first search. More...

#include <topological_sort.H>

Collaboration diagram for Aleph::Topological_Sort< GT, Itor, SA >:

Public Member Functions
	Topological_Sort (SA &&__sa=SA())
	Constructor with rvalue arc filter.
	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 DFS.
void	operator() (const GT &g, DynDlist< typename GT::Node * > &list)
	Operator() overload for backward compatibility.

Private Member Functions
template<template< class > class List>
void	topological_sort (typename GT::Node *curr, List< typename GT::Node * > &list)
	Recursive helper for DFS-based topological sort.

Private Attributes
SA &	sa
const GT *	gptr

Detailed Description

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Topological_Sort< GT, Itor, SA >

Computes topological ordering using depth-first search.

This class performs topological sorting by recursively visiting nodes in depth-first order and inserting them in postfix order (after all successors have been visited).

The resulting order is a valid topological ordering where for every directed edge (u, v), u appears before v in the list.

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 78 of file topological_sort.H.

Constructor & Destructor Documentation

Topological_Sort() [1/2]

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

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

inline

Constructor with rvalue arc filter.

Parameters

__sa	Arc filter/selector (moved).

Definition at line 88 of file topological_sort.H.

Topological_Sort() [2/2]

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

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

inline

Constructor with lvalue arc filter.

Parameters

__sa	Arc filter/selector (referenced).

Definition at line 94 of file topological_sort.H.

Member Function Documentation

operator()()

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

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

inline

Operator() overload for backward compatibility.

Parameters

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

Definition at line 163 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::Topological_Sort< GT, Itor, SA >::perform ( const GT &  g )

inline

Compute topological ordering using DFS.

Performs depth-first traversal of the graph, inserting nodes in postfix order to produce 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.

Note

This function does not verify that g is acyclic. If g contains cycles, the result is undefined.

Definition at line 139 of file topological_sort.H.

References Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Topological_Sort< GT, Itor, SA >::gptr, IS_NODE_VISITED, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), Aleph::HTList::size(), and Aleph::Topological_Sort< GT, Itor, SA >::topological_sort().

topological_sort()

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

template<template< class > class List>

void Aleph::Topological_Sort< GT, Itor, SA >::topological_sort ( typename GT::Node *  curr, List< typename GT::Node * > &  list  )

inlineprivate

Recursive helper for DFS-based topological sort.

Parameters

curr	Current node being visited.
list	Output list accumulating sorted nodes.

Definition at line 103 of file topological_sort.H.

References Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Topological_Sort< GT, Itor, SA >::gptr, IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::Topological_Sort< GT, Itor, SA >::sa, Aleph::HTList::size(), and Aleph::Topological_Sort< GT, Itor, SA >::topological_sort().

Referenced by Aleph::Topological_Sort< GT, Itor, SA >::perform(), and Aleph::Topological_Sort< GT, Itor, SA >::topological_sort().

Member Data Documentation

gptr

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

const GT* Aleph::Topological_Sort< GT, Itor, SA >::gptr

private

Definition at line 81 of file topological_sort.H.

Referenced by Aleph::Topological_Sort< GT, Itor, SA >::perform(), and Aleph::Topological_Sort< GT, Itor, SA >::topological_sort().

sa

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

SA& Aleph::Topological_Sort< GT, Itor, SA >::sa

private

Definition at line 80 of file topological_sort.H.

Referenced by Aleph::Topological_Sort< GT, Itor, SA >::topological_sort().

---

The documentation for this class was generated from the following file:

• topological_sort.H