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 of a digraph.

void	connected_components (const GT &g, DynList< DynList< typename GT::Node * > > &blks)
	Computes the strongly connected components 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 strongly connected components of a digraph.

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
bool	is_node_in_stack (typename GT::Node *p) const noexcept
	Check if a node is currently on the traversal stack.

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.

void	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.

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

Constructor & Destructor Documentation

◆ Tarjan_Connected_Components() [1/3]

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

Member Function Documentation

◆ build_cycle()

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

References 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, Aleph::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 453 of file Tarjan.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_arc(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::HTList::is_empty(), Aleph::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 897 of file Tarjan.H.

References 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 926 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 707 of file Tarjan.H.

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

◆ connected_components() [2/4]

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

This overloaded version of connected_components() takes a digraph g (supposedly weakly connected), computes its disconnected subgraphs or components, and stores them in a dynamic list of node lists.

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

Use this function if you do not need to obtain mapped copies of the strongly connected components.

The function is based on Tarjan's algorithm.

The function uses the build_subtree bit to mark visited nodes and arcs.

The algorithm internally discovers components through depth-first search.

Since mapping is avoided, this routine is faster and less memory intensive than the previous version. The disadvantage is perhaps that it does not compute the possible arcs that could interconnect a block in a single direction.

Parameters

[in]	g	the graph on which to compute its blocks.
[out]	blks	list of node lists. Each list contains the nodes that form a connected component.

Exceptions

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

See also: copy_graph()

Definition at line 698 of file Tarjan.H.

References 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::maps(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_lists().

◆ connected_components() [3/4]

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

connected_components() takes a digraph g (supposedly weakly connected), computes its disconnected subgraphs or components, and stores them in a dynamic list blk_list of mapped subdigraphs (both nodes and arcs are mapped). The emphasis on the supposed connected character of the graph is because if the graph were not connected, then the resulting list would contain only one element corresponding to the mapped copy digraph of g. If this were the case, then it is preferable to use the copy_graph() function instead.

The function is based on Tarjan's algorithm.

The function uses the build_subtree bit to mark visited nodes and arcs.

The algorithm internally discovers components through depth-first search.

Parameters

[in]	g	the graph on which to compute its blocks.
[out]	blk_list	list of subgraphs mapped to g containing the disconnected subgraphs or components of g.
[out]	arc_list	list of arcs connecting the blocks.

Exceptions

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

See also: copy_graph()

Definition at line 626 of file Tarjan.H.

References Aleph::DynList< T >::append(), 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, GraphCommon< GT, Node, Arc >::map_arcs(), Aleph::maps(), 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()(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()().

◆ connected_components() [4/4]

template<class GT , template< typename, class > class Itor = Out_Iterator, class 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 strongly connected components of a digraph.

This overloaded version of connected_components() takes a digraph g (supposedly weakly connected) and counts its disconnected subgraphs or components along with their sizes.

The function is based on Tarjan's algorithm.

The function uses the build_subtree bit to mark visited nodes and arcs.

The algorithm internally discovers components through depth-first search.

Parameters

[in]	g	the graph on which to compute its blocks.
[out]	blks	list of positive integers. Each entry contains the size of a distinct connected component.

Exceptions

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

See also: copy_graph()

Definition at line 751 of file Tarjan.H.

References 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::maps(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n, and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_len().

◆ get_filter() [1/2]

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

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

◆ get_filter() [2/2]

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

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

◆ get_graph()

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

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

◆ has_computation()

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

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

◆ has_cycle() [1/2]

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

References 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, Aleph::maps(), and Aleph::Tarjan_Connected_Components< GT, Itor, SA >::n.

◆ has_cycle() [2/2]

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

References 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 236 of file Tarjan.H.

References Aleph::Depth_First, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::df_count, Aleph::Tarjan_Connected_Components< GT, Itor, SA >::is_node_in_stack(), Aleph::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 385 of file Tarjan.H.

References 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 572 of file Tarjan.H.

References 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 879 of file Tarjan.H.

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

◆ is_node_in_stack()

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

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

inlineprivatenoexcept

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 223 of file Tarjan.H.

References IS_NODE_VISITED, Aleph::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 724 of file Tarjan.H.

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

◆ operator()() [1/5]

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

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

◆ operator()() [2/5]

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

References Aleph::DynList< T >::append(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::DynList< T >::remove_first().

◆ operator()() [3/5]

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

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

◆ operator()() [4/5]

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

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

◆ operator()() [5/5]

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

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

◆ operator=() [1/2]

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

References Aleph::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void 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 265 of file Tarjan.H.

References Aleph::DynList< T >::append(), 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(), Aleph::maps(), 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(), Aleph::HTList::size(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 344 of file Tarjan.H.

References Aleph::DynList< T >::append(), 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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 307 of file Tarjan.H.

References Aleph::DynList< T >::append(), 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::maps(), 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<class GT , template< typename, class > class Itor = Out_Iterator, class 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.