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

Computes strongly connected components (SCCs) in a directed graph using Tarjan's algorithm. More...

#include <Tarjan.H>

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

Classes
struct	Init_Tarjan_Node
	Functor to initialize node metadata for Tarjan traversal. More...

Public Member Functions
	Tarjan_Connected_Components (const Tarjan_Connected_Components &)=delete
	Tarjan instances should not be copied (they hold internal traversal state)
Tarjan_Connected_Components &	operator= (const Tarjan_Connected_Components &)=delete
	Tarjan_Connected_Components (Tarjan_Connected_Components &&)=default
	Move is allowed.
Tarjan_Connected_Components &	operator= (Tarjan_Connected_Components &&)=default
	Tarjan_Connected_Components (SA __sa=SA()) noexcept
	Constructs a Tarjan algorithm instance for computing strongly connected components.
void	connected_components (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list)
	Computes the strongly connected components (SCCs) of a digraph.
void	connected_components (const GT &g, DynList< DynList< typename GT::Node * > > &blks)
	Computes the strongly connected components (SCCs) of a digraph.
DynList< DynList< typename GT::Node * > >	connected_components (const GT &g)
size_t	num_connected_components (const GT &g)
	Returns the number of strongly connected components in the graph.
void	connected_components (const GT &g, DynList< size_t > &blks)
	Computes the sizes of the strongly connected components (SCCs).
void	operator() (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as mapped subgraphs with bridges (arcs connecting different SCCs).
void	operator() (const GT &g, DynList< DynList< typename GT::Node * > > &blks)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as lists of nodes.
DynList< DynList< typename GT::Node * > >	operator() (const GT &g)
void	operator() (const GT &g, DynDlist< GT > &blk_list, DynDlist< typename GT::Arc * > &arc_list)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as mapped subgraphs with bridges, using DynDlist containers.
void	operator() (const GT &g, DynDlist< DynDlist< typename GT::Node * > > &blks)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as lists of nodes, using DynDlist containers.
bool	has_cycle (const GT &g)
	Determines whether the digraph contains at least one cycle.
bool	is_dag (const GT &g)
	Determines whether the directed graph is acyclic (a DAG).
bool	compute_cycle (const GT &g, Path< GT > &path)
	Finds and constructs a cycle in the digraph, if one exists.
bool	compute_cycle (const GT &g, typename GT::Node *src, Path< GT > &path)
	Finds and constructs a cycle starting from a specific node, if one exists.
bool	test_connectivity (const GT &g)
	Tests whether the digraph is strongly connected.
Accessors
SA &	get_filter () noexcept
	Returns the arc filter used by this instance.
const SA &	get_filter () const noexcept
	Returns the arc filter used by this instance (const version).
bool	has_computation () const noexcept
	Check if a computation has been performed.
GT *	get_graph () const noexcept
	Get the graph of the last computation.

Private Member Functions
void	init_node_and_push_in_stack (typename GT::Node *p)
	Initialize a node and push it onto the traversal stack.
GT::Node *	pop_from_stack ()
	Pop a node from the traversal stack.
long	scc_by_blocks (typename GT::Node *v, DynList< GT > &blk_list)
	Recursive DFS to find SCCs and build mapped subgraphs.
void	scc_by_lists (typename GT::Node *v, DynList< DynList< typename GT::Node * > > &blks)
	Recursive DFS to find SCCs and collect nodes into lists.
void	scc_by_len (typename GT::Node *v, DynList< size_t > &sizes)
	Recursive DFS to find SCCs and count their sizes.
void	init_tarjan (const GT &g)
	Initialize internal state for a Tarjan traversal.
bool	has_cycle (typename GT::Node *v)
	Recursive DFS to detect if a cycle exists starting from v.
void	build_path (const GT &block, DynMapAvlTree< typename GT::Node *, typename GT::Node * > &table)
	Build a cycle path from a strongly connected block.
bool	build_cycle (typename GT::Node *v)
	Recursive DFS to find and construct a cycle starting from v.
bool	is_connected (typename GT::Node *v)
	Recursive DFS to test if the graph is strongly connected.

Static Private Member Functions
static bool	is_node_in_stack (typename GT::Node *p) noexcept
	Check if a node is currently on the traversal stack.

Private Attributes
SA	sa_
GT *	g_ptr_ = nullptr
DynListStack< typename GT::Node * >	stack_
long	df_count_ = 0
size_t	n_ = 0
Path< GT > *	path_ptr_ = nullptr

Detailed Description

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

Computes strongly connected components (SCCs) in a directed graph using Tarjan's algorithm.

This class implements Tarjan's algorithm for finding strongly connected components in directed graphs. A strongly connected component is a maximal set of vertices where every vertex is reachable from every other vertex in the component.

Tarjan's algorithm performs a single depth-first traversal to identify all SCCs in O(V + E) time complexity, where V is the number of vertices and E is the number of edges.

Template Parameters

GT	The directed graph type (based on List_Graph or similar).
Itor	The iterator template for traversing adjacent nodes/arcs. Defaults to Out_Iterator for outgoing arcs.
SA	The arc filter class used by the internal iterator. Defaults to Dft_Show_Arc<GT> which shows all arcs.

The class provides multiple overloaded methods for computing SCCs in different output formats:

• As a list of subgraphs (mapped copies of original graph components)
• As a list of node lists (lightweight, no graph copying)
• As a list of component sizes (counts only)

Additional functionality:

• Cycle detection: has_cycle(), is_dag()
• Cycle construction: compute_cycle()
• Strong connectivity testing: test_connectivity()

Usage example:

List_Digraph<int> g;
// ... build graph ...
 
Tarjan_Connected_Components<List_Digraph<int>> tarjan;
 
// Get SCCs as node lists
auto sccs = tarjan.connected_components(g);
for (auto & scc : sccs)
  {
    // Process each SCC
    for (auto node : scc)
      process(node);
  }
 
// Check for cycles
if (tarjan.has_cycle(g))
  std::cout << "Graph contains a cycle" << '\n';

Note

The algorithm uses node bits (Aleph::Min, Aleph::Depth_First) and node counters/cookies for bookkeeping during traversal.

Warning

This class is NOT thread-safe. Concurrent access to the same instance or to the same graph from multiple threads will result in undefined behavior.

See also

Compute_Cycle_In_Digraph

Author

Leandro Rabindranath León (lrleon at ula dot ve)

Definition at line 168 of file Tarjan.H.

Constructor & Destructor Documentation

Tarjan_Connected_Components() [1/3]

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

Aleph::Tarjan_Connected_Components< GT, Itor, SA >::Tarjan_Connected_Components ( const Tarjan_Connected_Components< GT, Itor, SA > &  )

delete

Tarjan instances should not be copied (they hold internal traversal state)

Tarjan_Connected_Components() [2/3]

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

Aleph::Tarjan_Connected_Components< GT, Itor, SA >::Tarjan_Connected_Components ( Tarjan_Connected_Components< GT, Itor, SA > &&  )

default

Move is allowed.

Tarjan_Connected_Components() [3/3]

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

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

inlinenoexcept

Constructs a Tarjan algorithm instance for computing strongly connected components.

Parameters

[in]

__sa

Arc filter functor used by the internal iterator. Defaults to Dft_Show_Arc<GT> which shows all arcs.

Definition at line 197 of file Tarjan.H.

Member Function Documentation

build_cycle()

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle ( typename GT::Node *  v )

inlineprivate

Recursive DFS to find and construct a cycle starting from v.

If a cycle is found (including self-loops), constructs it in path_ptr.

Parameters

v	The current node being visited.

Returns

true if a cycle is found and stored in path_ptr, false otherwise.

Definition at line 483 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Depth_First, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, k, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::path_ptr_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle().

build_path()

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path ( const GT &  block, DynMapAvlTree< typename GT::Node *, typename GT::Node * > &  table  )

inlineprivate

Build a cycle path from a strongly connected block.

Takes a mapped strongly connected subgraph and constructs the cycle path in path_ptr using the node mapping table.

Parameters

block	The strongly connected subgraph (mapped from original).
table	Bidirectional mapping between original and block nodes.

Definition at line 456 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Dlink::Iterator::has_curr(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::path_ptr_, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle().

compute_cycle() [1/2]

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle ( const GT &  g, Path< GT > &  path  )

inline

Finds and constructs a cycle in the digraph, if one exists.

Uses Tarjan's algorithm to detect a cycle in the directed graph. If a cycle is found, it is stored in the provided path parameter.

Parameters

[in]	g	The directed graph to search for cycles.
[out]	path	A Path object where the cycle will be stored if found. The path will form a cycle (start node == end node). If no cycle exists, path is emptied.

Returns

true if a cycle was found and stored in path, false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

See also

has_cycle(), is_dag()

Definition at line 867 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Path< GT >::empty(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::path_ptr_, and Aleph::Path< GT >::set_graph().

Referenced by Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator()().

compute_cycle() [2/2]

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle ( const GT &  g, typename GT::Node *  src, Path< GT > &  path  )

inline

Finds and constructs a cycle starting from a specific node, if one exists.

Uses Tarjan's algorithm starting from the specified source node to detect a cycle. If a cycle is found that includes the source node, it is stored in the provided path parameter.

Parameters

[in]	g	The directed graph to search for cycles.
[in]	src	The source node from which to start the cycle search.
[out]	path	A Path object where the cycle will be stored if found. The path will form a cycle containing the source node.

Returns

true if a cycle was found starting from src, false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

See also

has_cycle(), compute_cycle(const GT &, Path<GT> &)

Definition at line 896 of file Tarjan.H.

References ah_domain_error_if, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::path_ptr_, and Aleph::Path< GT >::set_graph().

connected_components() [1/4]

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

DynList< DynList< typename GT::Node * > > Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g )

inline

Definition at line 692 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

connected_components() [2/4]

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< DynList< typename GT::Node * > > &  blks  )

inline

Computes the strongly connected components (SCCs) of a digraph.

This overloaded version of connected_components() runs Tarjan's algorithm on g and stores each SCC as a list of node pointers in blks.

Each inner list contains the nodes belonging to one strongly connected component.

Use this function if you do not need mapped subgraph copies of the SCCs. Since mapping is avoided, this routine is faster and uses less memory than the subgraph overload; the trade-off is that it does not compute the arcs that interconnect the blocks.

The algorithm performs a single depth-first search and marks progress with the Aleph::Depth_First and Aleph::Min node bits.

Parameters

[in]	g	the digraph whose SCCs are computed.
[out]	blks	list of node lists; each inner list holds the nodes of one SCC.

Exceptions

bad_alloc

if there is not enough memory to insert into the list.

Definition at line 684 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

connected_components() [3/4]

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< GT > &  blk_list, DynList< typename GT::Arc * > &  arc_list  )

inline

Computes the strongly connected components (SCCs) of a digraph.

connected_components() runs Tarjan's algorithm on g and stores one mapped subdigraph per SCC in blk_list (both nodes and arcs are mapped back to g). Arcs that connect different SCCs are collected in arc_list. The number of blocks depends on the cyclic structure: an acyclic digraph yields one singleton block per node, while a single strongly connected digraph yields exactly one block.

The algorithm performs a single depth-first search and marks progress with the Aleph::Depth_First and Aleph::Min node bits.

Parameters

[in]	g	the digraph whose SCCs are computed.
[out]	blk_list	list of mapped subdigraphs, one per SCC of g.
[out]	arc_list	arcs connecting distinct SCCs (inter-block arcs).

Exceptions

bad_alloc

if there is not enough memory to build a block or insert into a list.

Definition at line 622 of file Tarjan.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::HTList::Iterator::has_curr(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::DynListStack< T >::is_empty(), IS_NODE_VISITED, k, GraphCommon< GT, Node, Arc >::map_arcs(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, NODE_COUNTER, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::num_connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Two_Sat< GT >::solve(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

connected_components() [4/4]

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< size_t > &  blks  )

inline

Computes the sizes of the strongly connected components (SCCs).

This overloaded version of connected_components() runs Tarjan's algorithm on g and records the size (node count) of each SCC in blks.

The algorithm performs a single depth-first search and marks progress with the Aleph::Depth_First and Aleph::Min node bits.

Parameters

[in]	g	the digraph whose SCCs are computed.
[out]	blks	list of sizes; each entry is the node count of one SCC.

Exceptions

bad_alloc

if there is not enough memory to insert into the list.

Definition at line 729 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len().

get_filter() [1/2]

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

const SA & Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_filter ( ) const

inlinenoexcept

Returns the arc filter used by this instance (const version).

Returns

Const reference to the arc filter.

Definition at line 954 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_.

get_filter() [2/2]

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

SA & Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_filter ( )

inlinenoexcept

Returns the arc filter used by this instance.

Returns

Reference to the arc filter.

Definition at line 946 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_.

Referenced by TEST().

get_graph()

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

GT * Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_graph ( ) const

inlinenoexcept

Get the graph of the last computation.

Returns

Pointer to the graph, or nullptr if no computation done.

Definition at line 970 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_.

has_computation()

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_computation ( ) const

inlinenoexcept

Check if a computation has been performed.

Returns

true if a graph has been processed, false otherwise.

Definition at line 962 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_.

has_cycle() [1/2]

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle ( const GT &  g )

inline

Determines whether the digraph contains at least one cycle.

Uses Tarjan's algorithm to detect if the directed graph has any cycles. A directed graph has a cycle if there exists a path from a vertex back to itself.

Parameters

[in]

g

The directed graph to check for cycles.

Returns

true if the graph contains at least one cycle, false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

See also

is_dag(), compute_cycle()

Definition at line 828 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), IS_NODE_VISITED, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_.

has_cycle() [2/2]

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle ( typename GT::Node *  v )

inlineprivate

Recursive DFS to detect if a cycle exists starting from v.

Detects cycles including self-loops (cycles of length 1) and strongly connected components with 2+ nodes.

Parameters

v	The current node being visited.

Returns

true if a cycle is found, false otherwise.

Definition at line 407 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_dag().

init_node_and_push_in_stack()

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack ( typename GT::Node *  p )

inlineprivate

Initialize a node and push it onto the traversal stack.

Sets the Min and Depth_First bits, assigns df and low values, and pushes the node onto the stack.

Parameters

p	The node to initialize and push.

Definition at line 233 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), Aleph::Min, NODE_BITS, Aleph::DynListStack< T >::push(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

init_tarjan()

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan ( const GT &  g )

inlineprivate

Initialize internal state for a Tarjan traversal.

Resets node metadata, clears the stack, and stores a pointer to the graph.

Parameters

g	The graph to traverse.

Note

Uses const_cast internally because the algorithm modifies node metadata (bits, counters, cookies) but not the graph structure itself.

Definition at line 389 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::DynListStack< T >::empty(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity().

is_connected()

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected ( typename GT::Node *  v )

inlineprivate

Recursive DFS to test if the graph is strongly connected.

Returns true if and only if all nodes belong to a single SCC. The algorithm detects early if multiple SCCs exist.

Parameters

v	The current node being visited.

Returns

true if all visited nodes so far form one SCC, false otherwise.

Definition at line 574 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::DynListStack< T >::is_empty(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_, and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity().

is_dag()

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_dag ( const GT &  g )

inline

Determines whether the directed graph is acyclic (a DAG).

A Directed Acyclic Graph (DAG) is a directed graph with no cycles. This method is equivalent to !has_cycle(g).

Parameters

[in]

g

The directed graph to check.

Returns

true if the graph is a DAG (has no cycles), false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

See also

has_cycle(), compute_cycle()

Definition at line 849 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle().

is_node_in_stack()

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

static bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack ( typename GT::Node *  p )

inlinestaticprivatenoexcept

Check if a node is currently on the traversal stack.

Parameters

p	The node to check.

Returns

true if the node is on the stack, false otherwise.

Definition at line 220 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), IS_NODE_VISITED, and Aleph::Min.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

num_connected_components()

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

size_t Aleph::Tarjan_Connected_Components< GT, Itor, SA >::num_connected_components ( const GT &  g )

inline

Returns the number of strongly connected components in the graph.

This is a convenience method that computes SCCs and returns only the count, which is more efficient than getting the full list when only the count is needed.

Parameters

[in]

g

The directed graph.

Returns

The number of strongly connected components.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 709 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::HTList::size().

Referenced by TEST().

operator()() [1/5]

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

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

inline

Definition at line 763 of file Tarjan.H.

References Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

operator()() [2/5]

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

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

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as lists of nodes, using DynDlist containers.

Parameters

[in]	g	The directed graph.
[out]	blks	List of strongly connected components, each as a list of nodes.

Definition at line 802 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

operator()() [3/5]

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynDlist< GT > &  blk_list, DynDlist< typename GT::Arc * > &  arc_list  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as mapped subgraphs with bridges, using DynDlist containers.

Parameters

[in]	g	The directed graph.
[out]	blk_list	List of strongly connected components as mapped subgraphs.
[out]	arc_list	List of bridge arcs connecting different SCCs.

Definition at line 777 of file Tarjan.H.

References Aleph::DynDlist< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::HTList::Iterator::has_curr(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::swap().

operator()() [4/5]

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

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

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as lists of nodes.

Parameters

[in]	g	The directed graph.
[out]	blks	List of strongly connected components, each as a list of nodes.

Definition at line 758 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

operator()() [5/5]

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynList< GT > &  blk_list, DynList< typename GT::Arc * > &  arc_list  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute strongly connected components and return them as mapped subgraphs with bridges (arcs connecting different SCCs).

Parameters

[in]	g	The directed graph.
[out]	blk_list	List of strongly connected components as mapped subgraphs.
[out]	arc_list	List of bridge arcs connecting different SCCs.

Definition at line 746 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components().

operator=() [1/2]

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

Tarjan_Connected_Components & Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator= ( const Tarjan_Connected_Components< GT, Itor, SA > &  )

delete

operator=() [2/2]

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

Tarjan_Connected_Components & Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator= ( Tarjan_Connected_Components< GT, Itor, SA > &&  )

default

pop_from_stack()

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

GT::Node * Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack ( )

inlineprivate

Pop a node from the traversal stack.

Returns

The popped node.

Definition at line 246 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Min, NODE_BITS, Aleph::DynListStack< T >::pop(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

scc_by_blocks()

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

long Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks ( typename GT::Node *  v, DynList< GT > &  blk_list  )

inlineprivate

Recursive DFS to find SCCs and build mapped subgraphs.

For each SCC found, creates a mapped copy subgraph and appends it to block_list.

Parameters

	v	The current node being visited.
[out]	blk_list	block list where the SCC will be put

Definition at line 262 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_nodes(), NODE_COOKIE, NODE_COUNTER, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks().

scc_by_len()

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len ( typename GT::Node *  v, DynList< size_t > &  sizes  )

inlineprivate

Recursive DFS to find SCCs and count their sizes.

For each SCC found, counts the number of nodes and appends the count to list_len_ptr.

Parameters

v	The current node being visited.
sizes	list of block sizes in number of nodes

Definition at line 348 of file Tarjan.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len().

scc_by_lists()

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

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists ( typename GT::Node *  v, DynList< DynList< typename GT::Node * > > &  blks  )

inlineprivate

Recursive DFS to find SCCs and collect nodes into lists.

For each SCC found, collects the node pointers into a list and appends it to list_list_ptr.

Parameters

v	The current node being visited.
blks	block list where the SCC node lists will be put

Definition at line 312 of file Tarjan.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), IS_NODE_VISITED, l, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists(), and w.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

test_connectivity()

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

bool Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity ( const GT &  g )

inline

Tests whether the digraph is strongly connected.

A directed graph is strongly connected if there is a path from every vertex to every other vertex. This method uses Tarjan's algorithm to determine strong connectivity.

Parameters

[in]

g

The directed graph to test.

Returns

true if the graph is strongly connected, false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

See also

connected_components()

Definition at line 917 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::DynListStack< T >::is_empty(), IS_NODE_VISITED, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_.

Member Data Documentation

df_count_

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

long Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count_ = 0

private

Definition at line 176 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity().

g_ptr_

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

GT* Aleph::Tarjan_Connected_Components< GT, Itor, SA >::g_ptr_ = nullptr

private

Definition at line 172 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_graph(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_computation(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

n_

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

size_t Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n_ = 0

mutableprivate

Definition at line 177 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity().

path_ptr_

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

Path<GT>* Aleph::Tarjan_Connected_Components< GT, Itor, SA >::path_ptr_ = nullptr

private

Definition at line 179 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle().

sa_

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

SA Aleph::Tarjan_Connected_Components< GT, Itor, SA >::sa_

private

Definition at line 170 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_filter(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::get_filter(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::has_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

stack_

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

DynListStack<typename GT::Node *> Aleph::Tarjan_Connected_Components< GT, Itor, SA >::stack_

private

Definition at line 174 of file Tarjan.H.

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_node_and_push_in_stack(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::init_tarjan(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_connected(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::pop_from_stack(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::test_connectivity().

---

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

• Tarjan.H