Find bridge edges (isthmuses) of a connected undirected graph. More...

#include <tpl_cut_nodes.H>

Collaboration diagram for Aleph::Compute_Bridges< GT, SA >:

Public Member Functions
	Compute_Bridges (const GT &g, SA sa=SA())
	Constructor.

DynList< typename GT::Arc * >	find_bridges (typename GT::Node *start)
	Find all bridge edges in the graph, starting from `start`.

DynList< typename GT::Arc * >	find_bridges ()
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Starts the DFS from the first node returned by the graph.

DynList< typename GT::Arc * >	operator() (typename GT::Node *start)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Synonym for `find_bridges(start)`.

DynList< typename GT::Arc * >	operator() ()
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Synonym for `find_bridges()` (from first node).

Private Member Functions
void	__dfs (typename GT::Node p, typename GT::Arc parent_arc, long &curr_df, DynList< typename GT::Arc * > &bridges)

Private Attributes
SA	sa

GT *	gptr

Related Symbols
(Note that these are not member symbols.)
	find_bridges
	Starts from the first node of the graph.

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Compute_Bridges< GT, SA >

Find bridge edges (isthmuses) of a connected undirected graph.

A bridge (also called isthmus or cut edge) is an arc whose removal disconnects the graph. This class implements Tarjan's O(V + E) algorithm: a single DFS that tracks discovery time df[v] and low-link low[v] (earliest discovery time reachable from the subtree of v via back-edges).

Bridge condition: a DFS tree edge (p → tgt) is a bridge if and only if low[tgt] > df[p], i.e., no back-edge in tgt's subtree reaches an ancestor of p.

Parallel edges are handled correctly: only the exact parent arc (by pointer identity) is skipped; a second parallel edge acts as a back-edge and prevents either copy from being a bridge.

Usage:

Compute_Bridges<Graph> cb(g);
DynList<Graph::Arc *> bridges = cb.find_bridges();
for (auto * a : bridges)
  std::cout << "bridge endpoint ids: "
            << g.get_src_node(a)->get_info() << " -- "
            << g.get_tgt_node(a)->get_info() << '\n';

Template Parameters

GT	Graph type (must be undirected; see tpl_graph.H).
SA	Arc filter (default: `Dft_Show_Arc<GT>`).

Note: Complexity: O(V + E) time and O(V) extra space.; The graph must be undirected. A domain_error is thrown for digraphs.

See also: Compute_Cut_Nodes, find_bridges(), is_an_cut_arc()

Definition at line 652 of file tpl_cut_nodes.H.

Constructor & Destructor Documentation

◆ Compute_Bridges()

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Compute_Bridges< GT, SA >::Compute_Bridges	(	const GT &	g,
		SA	sa = `SA()`
	)

inline

Constructor.

Parameters

[in]	g	Undirected connected graph.
[in]	sa	Arc filter.

Definition at line 699 of file tpl_cut_nodes.H.

Member Function Documentation

◆ __dfs()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Compute_Bridges< GT, SA >::__dfs	(	typename GT::Node *	p,
		typename GT::Arc *	parent_arc,
		long &	curr_df,
		DynList< typename GT::Arc * > &	bridges
	)

inlineprivate

Definition at line 657 of file tpl_cut_nodes.H.

References Aleph::Compute_Bridges< GT, SA >::__dfs(), ARC_BITS, Aleph::Depth_First, Aleph::divide_and_conquer_partition_dp(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, and Aleph::Compute_Bridges< GT, SA >::sa.

Referenced by Aleph::Compute_Bridges< GT, SA >::__dfs(), and Aleph::Compute_Bridges< GT, SA >::find_bridges().

◆ find_bridges() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::Compute_Bridges< GT, SA >::find_bridges ( )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Starts the DFS from the first node returned by the graph.

Returns an empty list immediately if the graph has no nodes.

Definition at line 758 of file tpl_cut_nodes.H.

References Aleph::Compute_Bridges< GT, SA >::find_bridges(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::Compute_Bridges< GT, SA >::gptr.

Referenced by Aleph::Compute_Bridges< GT, SA >::find_bridges(), Aleph::Compute_Bridges< GT, SA >::operator()(), and Aleph::Compute_Bridges< GT, SA >::operator()().

◆ find_bridges() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::Compute_Bridges< GT, SA >::find_bridges ( typename GT::Node * start )

inline

Find all bridge edges in the graph, starting from start.

Performs a DFS from start and then visits any nodes not reachable from start (disconnected components), returning every arc identified as a bridge. The graph's Depth_First bits and NODE_COUNTER fields are used internally and reset before the search; NODE_COOKIE is used for low-link storage and cleared on return.

Parameters

[in] start Starting node for the first DFS.

Returns: DynList of pointers to bridge arcs (order: DFS post-order).

Exceptions

std::domain_error	If the graph is a digraph.
std::invalid_argument	If `start` is `nullptr` and the graph is non-empty.

Definition at line 719 of file tpl_cut_nodes.H.

References Aleph::Compute_Bridges< GT, SA >::__dfs(), ah_domain_error_if, ah_invalid_argument_if, Aleph::Depth_First, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::for_each_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Compute_Bridges< GT, SA >::gptr, GraphCommon< GT, Node, Arc >::is_digraph(), IS_NODE_VISITED, NODE_BITS, NODE_COOKIE, NODE_COUNTER, and GraphCommon< GT, Node, Arc >::reset_arcs().

◆ operator()() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::Compute_Bridges< GT, SA >::operator() ( )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Synonym for find_bridges() (from first node).

Definition at line 778 of file tpl_cut_nodes.H.

References Aleph::Compute_Bridges< GT, SA >::find_bridges().

◆ operator()() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::Compute_Bridges< GT, SA >::operator() ( typename GT::Node * start )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Synonym for find_bridges(start).

Definition at line 769 of file tpl_cut_nodes.H.

References Aleph::Compute_Bridges< GT, SA >::find_bridges().