Computation of cut nodes (articulation points) of a graph. More...

#include <tpl_cut_nodes.H>

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

Public Member Functions
void	cut_nodes (typename GT::Node start, DynDlist< typename GT::Node > &list)
	Computes the cut nodes.

	Compute_Cut_Nodes (const GT &g, SA __sa=SA())
	Constructor for cut nodes calculator.

void	operator() (DynDlist< typename GT::Node * > &list)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute cut nodes starting from the first node of the graph.

void	operator() (typename GT::Node start, DynDlist< typename GT::Node > &list)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Compute cut nodes starting from a specific node.

long	paint_subgraphs ()
	Paints the connected components around the cut nodes.

void	map_subgraph (GT &sg, const long &color)
	Obtains a mapped copy of the component with the given color.

void	map_cut_graph (GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)
	Computes the mapped cut graph of a graph.

void	compute_blocks (DynDlist< GT > &block_list, GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)
	Build mapped graphs around cut nodes.

Private Types
enum	State { Init , Cut_Nodes_Computed , Painted }

Private Member Functions
void	cut_nodes (typename GT::Node p, typename GT::Arc a)

void	paint_subgraph (typename GT::Node *p)

void	paint_from_cut_node (typename GT::Node *p)

GT::Node *	create_and_map_node (typename GT::Node *gp, const long &color, GT &sg)

void	map_subgraph (GT &sg, typename GT::Node *gsrc, const long &color)

Private Attributes
SA	sa

GT *	gptr = nullptr

DynDlist< typename GT::Node * > *	list_ptr = nullptr

long	curr_df = 0

long	curr_color = 1

enum Aleph::Compute_Cut_Nodes::State	state

Detailed Description

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

Computation of cut nodes (articulation points) of a graph.

The Compute_Cut_Nodes class computes everything related to the cut nodes of a connected graph. To do this, it performs a depth-first traversal starting from a given node and appends each cut node found in the graph to a dynamic list.

The dynamic list is provided by the user.

  A cut node is defined as a node such that when removed (together
  with its arcs), the graph becomes disconnected.

  The algorithm uses the Depth_First bit to mark nodes and arcs
  that have been visited. Additionally, the Build_Subtree bit is
  used to construct mapped copies of connected components around
  a cut node.

  This class also provides methods to "paint" the various blocks
  that would be separated by the cut nodes, as well as to obtain
  mapped copies of the connected components around the cut nodes,
  the cut graph, and the cross arcs.

  It is assumed that g is connected and no verification is
  performed in this regard.

The class template parameters are:

GT: the graph type.
SA: the arc filter for arc iterators.

Note: If you need to compute the cut graph using the map_cut_graph() method, then the arc filter class must overload the operator () (GT&, GT::Arc*).

This class exports several operations with sequential dependencies:

cut_nodes(): computes the cut nodes and inserts them into a list. The operator () on the class is a synonym for this method.
paint_subgraphs(): "paints" the different components of the graph around the previously computed cut nodes. The routine returns the number of colors, one per component, that the graph has. The colors are placed in the counters associated with each node.
map_subgraph(): obtains a mapped copy of a connected component associated with a given color.
map_cut_graph(): obtains a mapped copy of the "cut graph"; that is, the one composed only of the cut nodes of the graph. This method also computes the cross arcs (those connecting a cut node with a connected block).

If you want to execute everything at once, the compute_blocks() method is provided, which computes the cut nodes, paints the components, and calculates the mapped copies of the connected components as well as the cross arcs.

  @ingroup Graphs

Definition at line 115 of file tpl_cut_nodes.H.

Member Enumeration Documentation

◆ State

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

enum Aleph::Compute_Cut_Nodes::State

private

Enumerator
Init
Cut_Nodes_Computed
Painted

Definition at line 123 of file tpl_cut_nodes.H.

Constructor & Destructor Documentation

◆ Compute_Cut_Nodes()

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

Aleph::Compute_Cut_Nodes< GT, SA >::Compute_Cut_Nodes	(	const GT &	g,
		SA	__sa = `SA()`
	)

inline

Constructor for cut nodes calculator.

Parameters

[in]	g	the graph for which to compute the cut nodes.
[in]	__sa	the arc filter for arc iterators.

Definition at line 337 of file tpl_cut_nodes.H.

Member Function Documentation

◆ compute_blocks()

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

void Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks	(	DynDlist< GT > &	block_list,
		GT &	cut_graph,
		DynDlist< typename GT::Arc * > &	cross_arc_list
	)

inline

Build mapped graphs around cut nodes.

This routine takes a previously computed list of cut nodes and builds, in a single pass over nodes, mapped copies of the connected components around the cut nodes, as well as the cut graph. Then, it performs a pass over arcs to determine the cross arcs.

If you need all mapped blocks and the cut graph, using this routine is more efficient than calling map_subgraph() and map_cut_graph() separately.

Parameters

[out]	block_list	list of graphs where mapped copies of connected components will be stored.
[out]	cut_graph	mapped cut graph.
[out]	cross_arc_list	list of cross arcs.

Exceptions

bad_alloc	if there is not enough memory.
logic_error	if cut nodes have not been computed.

Definition at line 523 of file tpl_cut_nodes.H.

◆ create_and_map_node()

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

GT::Node * Aleph::Compute_Cut_Nodes< GT, SA >::create_and_map_node	(	typename GT::Node *	gp,
		const long &	color,
		GT &	sg
	)

inlineprivate

Definition at line 283 of file tpl_cut_nodes.H.

References Aleph::Build_Subtree, Aleph::color(), Aleph::DynList< T >::get(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), and NODE_BITS.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), and Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph().

◆ cut_nodes() [1/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes	(	typename GT::Node *	p,
		typename GT::Arc *	a
	)

inlineprivate

Definition at line 125 of file tpl_cut_nodes.H.

References Aleph::DynDlist< T >::append(), ARC_BITS, Aleph::Compute_Cut_Nodes< GT, SA >::curr_df, Aleph::Cut, Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::Depth_First, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Compute_Cut_Nodes< GT, SA >::list_ptr, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, and Aleph::Compute_Cut_Nodes< GT, SA >::sa.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::Compute_Cut_Nodes< GT, SA >::operator()(), and Aleph::Compute_Cut_Nodes< GT, SA >::operator()().

◆ cut_nodes() [2/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes	(	typename GT::Node *	start,
		DynDlist< typename GT::Node * > &	list
	)

inline

Computes the cut nodes.

Parameters

[in]	start	starting node from which to begin the computation.
[out]	list	dynamic list where pointers to cut nodes of the graph are stored.

Exceptions

bad_alloc if there is no memory to insert into the dynamic list or if there is no memory for the internal computation data of the algorithm.

The list must be provided by the user and is cleared at the beginning of the computation.

Definition at line 178 of file tpl_cut_nodes.H.

References Aleph::DynDlist< T >::append(), ARC_BITS, Aleph::Compute_Cut_Nodes< GT, SA >::curr_df, Aleph::Cut, Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::Compute_Cut_Nodes< GT, SA >::Cut_Nodes_Computed, Aleph::Depth_First, Aleph::DynDlist< T >::empty(), GraphCommon< GT, Node, Arc >::for_each_node(), Aleph::Compute_Cut_Nodes< GT, SA >::gptr, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Compute_Cut_Nodes< GT, SA >::list_ptr, Aleph::maps(), NODE_BITS, NODE_COUNTER, GraphCommon< GT, Node, Arc >::reset_arcs(), Aleph::Compute_Cut_Nodes< GT, SA >::sa, and Aleph::Compute_Cut_Nodes< GT, SA >::state.

◆ map_cut_graph()

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

void Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph	(	GT &	cut_graph,
		DynDlist< typename GT::Arc * > &	cross_arc_list
	)

inline

Computes the mapped cut graph of a graph.

The cut graph of a graph is the one composed only of the cut nodes.

The cross arcs are also computed; that is, those that connect cut nodes with connected components.

The idea of this algorithm is that when used in combination with map_subgraph(), the original graph can be obtained from the mapped copies.

Parameters

[out]	cut_graph	the cut graph
[out]	cross_arc_list	the list of cross arcs; that is, the arcs that go from a cut node to a connected component. These arcs do not belong to the cut graph.

Exceptions

logic_error if the graph has not been previously painted.

Definition at line 460 of file tpl_cut_nodes.H.

References ah_logic_error_if, Aleph::DynList< T >::append(), Aleph::clear_graph(), Aleph::DynList< T >::get(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Compute_Cut_Nodes< GT, SA >::gptr, Aleph::Dlink::Iterator::has_curr(), Aleph::Compute_Cut_Nodes< GT, SA >::list_ptr, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::Compute_Cut_Nodes< GT, SA >::Painted, Aleph::Compute_Cut_Nodes< GT, SA >::sa, and Aleph::Compute_Cut_Nodes< GT, SA >::state.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks().

◆ map_subgraph() [1/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph	(	GT &	sg,
		const long &	color
	)

inline

Obtains a mapped copy of the component with the given color.

map_subgraph() extracts from the graph the component with the specified color and constructs a mapped graph in sg.

Parameters

[out]	sg	the graph where the mapped copy is to be obtained.
[in]	color	the color to be extracted.

Exceptions

logic_error	if the graph is not painted.
domain_error	if there is no component with the given color.

Definition at line 415 of file tpl_cut_nodes.H.

References ah_domain_error_if, ah_logic_error_if, Aleph::clear_graph(), Aleph::color(), Aleph::Compute_Cut_Nodes< GT, SA >::create_and_map_node(), Aleph::Compute_Cut_Nodes< GT, SA >::gptr, Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::maps(), Aleph::Compute_Cut_Nodes< GT, SA >::Painted, and Aleph::Compute_Cut_Nodes< GT, SA >::state.

◆ map_subgraph() [2/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph	(	GT &	sg,
		typename GT::Node *	gsrc,
		const long &	color
	)

inlineprivate

Definition at line 299 of file tpl_cut_nodes.H.

References ARC_BITS, Aleph::Build_Subtree, Aleph::color(), Aleph::Compute_Cut_Nodes< GT, SA >::create_and_map_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::Compute_Cut_Nodes< GT, SA >::sa.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), and Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph().

◆ operator()() [1/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::operator() ( DynDlist< typename GT::Node * > & 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 cut nodes starting from the first node of the graph.

Parameters

[out] list Output list of cut nodes.

Definition at line 349 of file tpl_cut_nodes.H.

References Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), and Aleph::Compute_Cut_Nodes< GT, SA >::gptr.

◆ operator()() [2/2]

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

void Aleph::Compute_Cut_Nodes< GT, SA >::operator()	(	typename GT::Node *	start,
		DynDlist< typename GT::Node * > &	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 cut nodes starting from a specific node.

Parameters

[in]	start	Starting node for the computation.
[out]	list	Output list of cut nodes.

Definition at line 361 of file tpl_cut_nodes.H.

References Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes().

◆ paint_from_cut_node()

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

void Aleph::Compute_Cut_Nodes< GT, SA >::paint_from_cut_node ( typename GT::Node * p )

inlineprivate

Definition at line 250 of file tpl_cut_nodes.H.

References ARC_BITS, Aleph::Cross_Arc, Aleph::Compute_Cut_Nodes< GT, SA >::curr_color, Aleph::Cut, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraph(), and Aleph::Compute_Cut_Nodes< GT, SA >::sa.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs().

◆ paint_subgraph()

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

void Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraph ( typename GT::Node * p )

inlineprivate

Definition at line 226 of file tpl_cut_nodes.H.

References Aleph::Compute_Cut_Nodes< GT, SA >::curr_color, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraph(), and Aleph::Compute_Cut_Nodes< GT, SA >::sa.

Referenced by Aleph::Compute_Cut_Nodes< GT, SA >::paint_from_cut_node(), and Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraph().

◆ paint_subgraphs()

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

long Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs ( )

inline

Paints the connected components around the cut nodes.

paint_subgraphs() paints the connected components around the cut nodes of a graph.

The routine requires that the cut_nodes() method has been previously invoked.

The "colors" of each component are placed in the NODE_COUNTER attribute of each node and arc. The first color starts at value 1.

Use this routine if it is not necessary or sufficient to obtain the components using the colors of the blocks. This saves the computation and memory of having to create new graphs.