Biconnectivity-test and low-numbers. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/biconnectivity.h>

Inheritance diagram for biconnectivity:

Collaboration diagram for biconnectivity:

Public Types
typedef list< node >::iterator	cutpoint_iterator

typedef list< pair< list< node > , list< edge > > >::iterator	component_iterator

Public Types inherited from dfs
typedef list< edge > ::const_iterator	tree_edges_iterator
	Iterator for the tree edges of the DFS-tree.

typedef list< node > ::const_iterator	dfs_iterator
	Iterator for the (reached) nodes in DFS-order.

typedef list< edge > ::const_iterator	non_tree_edges_iterator
	Iterator for the non-tree-edges.

typedef list< dfs_iterator > ::const_iterator	roots_iterator
	Iterator for the roots of the DFS-forest.

Public Types inherited from algorithm
enum	{ GTL_OK = 1, GTL_ERROR = 0 }
	Return values for algorithm::check and algorithm::run. More...

Public Member Functions
	biconnectivity ()
	Creates biconnectivity algorithm object.

virtual	~biconnectivity ()
	Destroys biconnectivity algorithm object.

virtual int	check (graph &G)
	Checks whether the algorithm can be applied.

virtual void	reset ()
	Resets algorithm.

int	low_number (const node &n) const
	low-number.

bool	is_biconnected () const
	Biconnectivity-test.

bool	store_components () const
	Returns whether the storing of components is enabled.

void	store_components (bool set)
	Enables or disables the storing of biconnected components.

void	make_biconnected (bool set)
	If enabled edges will be added to the graph in order to make it biconnected, if cutpoints are discovered.

bool	make_biconnected () const
	Returns whether addition of edges neccessary to make graph biconnected is enabled.

list< edge >::iterator	additional_begin ()
	Begin of edges added to make graph biconnected.

list< edge >::iterator	additional_end ()
	End of edges added to make graph biconnected.

cutpoint_iterator	cut_points_begin ()
	Start iteration over all cutpoints found.

cutpoint_iterator	cut_points_end ()
	End of iteration over all cutpoints.

component_iterator	components_begin ()
	Start iteration over all biconnected components (if enabled during last call to run).

component_iterator	components_end ()
	End of iteration over all biconnected components.

int	number_of_components () const
	Number von biconnected components detected during the last run.

virtual void	init_handler (graph &)
	Handler called before the start of DFS.

virtual void	entry_handler (graph &, node &, node &)
	Handler called when touching node n.

virtual void	before_recursive_call_handler (graph &, edge &, node &)
	Handler called when a unused node n connected to the actual node by e is found.

virtual void	after_recursive_call_handler (graph &, edge &, node &)
	Handler called after the algorithm returns from the subtree starting at n connected to the actual node by e.

virtual void	old_adj_node_handler (graph &, edge &, node &)
	Handler called when a already marked node n connected to the actual node by e is found during the search of all adjacent edges of the actual node.

virtual void	new_start_handler (graph &, node &)
	Called when DFS is started with start-node n.

virtual void	leave_handler (graph &, node &, node &)
	Handler called after all the adjacent edges of n have been examined.

virtual void	end_handler (graph &)
	Handler called at the end of DFS.

Public Member Functions inherited from dfs
	dfs ()
	Constructor.

virtual	~dfs ()
	Destructor.

int	run (graph &G)
	Applies algorithm to graph g.

void	start_node (const node &n)
	Sets start-node for DFS.

node	start_node () const
	Returns start-node for DFS.

void	scan_whole_graph (bool set)
	Enables or disables scanning of the whole graph.

bool	scan_whole_graph () const
	Returns true iff the whole graph will be scanned.

void	calc_comp_num (bool set)
	Enables or Disables the calculation of the completion number.

bool	calc_comp_num () const
	Returns true iff completion-numbers will be calculated.

void	store_preds (bool set)
	Enables or disables the storing of predecessors.

bool	store_preds () const
	Returns true iff the storing of predecessors is enabled.

void	store_non_tree_edges (bool set)
	Enables the storing of back-edges.

bool	store_non_tree_edges () const
	Returns true iff the storing of non-tree-edges is enabled.

bool	reached (const node &n) const
	Checks whether node n was reached in last DFS.

int	dfs_num (const node &n) const
	DFS-Number of n.

int	operator[] (const node &n) const
	DFS-Number of n.

int	comp_num (const node &n) const
	Completion-number of node n, if enabled in last run.

node	father (const node &n) const
	Returns father of node n in DFS-forest.

tree_edges_iterator	tree_edges_begin () const
	Iterate through all edges picked in last DFS.

tree_edges_iterator	tree_edges_end () const
	End-iterator for iteration through all edges picked in last DFS.

dfs_iterator	begin () const
	Iterate through all (reached) nodes in DFS-order.

dfs_iterator	end () const
	End-Iterator for iteration through all (reached) nodes in DFS-order.

non_tree_edges_iterator	non_tree_edges_begin () const
	Iterate through all non-tree-edges (if enabled).

non_tree_edges_iterator	non_tree_edges_end () const
	End-iterator for iteration through all non-tree-edges (if enabled).

roots_iterator	roots_begin () const
	Iterator pointing towards the first root in the DFS-forest.

roots_iterator	roots_end () const
	Iterator pointing to the end of all roots.

int	number_of_reached_nodes () const
	Number of nodes reached in last DFS.

Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.

virtual	~algorithm ()
	Destroys the algorithm object.

Protected Attributes
list< edge >	self_loops

node_map< component_iterator >	in_component

node_map< int >	low_num

int	num_of_components

bool	store_comp

bool	add_edges

node	last

stack< node >	node_stack

stack< edge >	edge_stack

list< pair< list< node >, list < edge > > >	components

list< node >	cut_points

node_map< int >	cut_count

list< edge >	additional

node_map< node >	first_child

Protected Attributes inherited from dfs
int	act_dfs_num

int	act_comp_num

list< edge >	tree

list< node >	dfs_order

node_map< int >	dfs_number

int	reached_nodes

edge_map< int > *	used

list< dfs_iterator >	roots

node_map< int > *	comp_number

node_map< node > *	preds

list< edge > *	back_edges

node	start

bool	whole_graph

Detailed Description

Biconnectivity-test and low-numbers.

Date:: 2003/03/26 13:37:14

Revision:: 1.18

Obviously there is a close relationship between DFS and the testing of biconnectivity. Thus this test takes advantage of the possibility to add pieces of code to the DFS-class in order to calculate the low-numbers.

As default no biconnected components will be stored and no edges will be added to make the graph biconnected. The test will run on the whole graph, even if it is not connected.

Definition at line 36 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 36 of file biconnectivity.h

Member Typedef Documentation

typedef list<pair<list<node>, list<edge> > >::iterator biconnectivity::component_iterator

Definition at line 181 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 181 of file biconnectivity.h

typedef list<node>::iterator biconnectivity::cutpoint_iterator

Definition at line 154 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 154 of file biconnectivity.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE biconnectivity::biconnectivity ( )

Creates biconnectivity algorithm object.

See Also: dfs::dfs

Definition at line 24 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 24 of file biconnectivity.cpp

References add_edges, num_of_components, dfs::scan_whole_graph(), store_comp, and dfs::store_preds().

Here is the call graph for this function:

virtual biconnectivity::~biconnectivity ( )

inlinevirtual

Destroys biconnectivity algorithm object.

See Also: dfs::~dfs

Definition at line 51 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 51 of file biconnectivity.h

Member Function Documentation

list<edge>::iterator biconnectivity::additional_begin ( )

inline

Begin of edges added to make graph biconnected.

Returns: begin of additional edges

See Also: biconnectivity::make_biconnected

Definition at line 139 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 139 of file biconnectivity.h

Referenced by planarity::run().

Here is the caller graph for this function:

list<edge>::iterator biconnectivity::additional_end ( )

inline

End of edges added to make graph biconnected.

Returns: end of additional edges

See Also: biconnectivity::make_biconnected

Definition at line 148 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 148 of file biconnectivity.h

Referenced by planarity::run().

Here is the caller graph for this function:

void biconnectivity::after_recursive_call_handler	(	graph &	G,
		edge &	e,
		node &	n
	)

virtual

Handler called after the algorithm returns from the subtree starting at n connected to the actual node by e.

Parameters

G	graph for which DFS was invoked.
e	edge connecting the actual node to the unused one.
n	unused node.

Reimplemented from dfs.

Definition at line 160 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 160 of file biconnectivity.cpp

References add_edges, additional, cut_count, dfs::dfs_num(), edge_stack, dfs::end(), dfs::father(), first_child, in_component, low_num, n, graph::new_edge(), node_stack, num_of_components, node::opposite(), edge::source(), store_comp, edge::target(), and Acts::Test::tmp().

Here is the call graph for this function:

void biconnectivity::before_recursive_call_handler	(	graph &	G,
		edge &	e,
		node &	n
	)

virtual

Handler called when a unused node n connected to the actual node by e is found.

Parameters

G	graph for which DFS was invoked.
e	edge connecting the actual node to the unused one.
n	unused node.

Reimplemented from dfs.

Definition at line 152 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 152 of file biconnectivity.cpp

References node_stack, and store_comp.

int biconnectivity::check ( graph & G )

virtual

Checks whether the algorithm can be applied.

Necessary preconditions:

G is undirected.
storing of predecessors is enabled.
DFS may be applied

Parameters

G graph.

Returns: algorithm::GTL_OK if binconnectivity-test can be applied to G.

See Also: dfs::scan_whole_graph, dfs::store_preds

Reimplemented from dfs.

Definition at line 57 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 57 of file biconnectivity.cpp

References dfs::check(), algorithm::GTL_ERROR, algorithm::GTL_OK, graph::is_undirected(), and dfs::preds.

Referenced by planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

component_iterator biconnectivity::components_begin ( )

inline

Start iteration over all biconnected components (if enabled during last call to run).

Components are represented as a pair consisting of a list of nodes and a list of edges, i.e. if it is of type component_iterator then *it is of type pair<list<node>,list<edge> >.

Returns: iterator to first component

See Also: biconnectivity::store_components

Definition at line 196 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 196 of file biconnectivity.h

References dfs::begin().

Referenced by planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

component_iterator biconnectivity::components_end ( )

inline

End of iteration over all biconnected components.

Returns: end of iteration over biconnected components

See Also: biconnectivity::store_components

Definition at line 206 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 206 of file biconnectivity.h

References dfs::end().

Referenced by planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

cutpoint_iterator biconnectivity::cut_points_begin ( )

inline

Start iteration over all cutpoints found.

A cutpoints is a node whose removal will disconnect the graph, thus a graph with no cutpoints is biconnected and vice versa.

Returns: iterator to first cutpoint.

See Also: biconnectivity::cut_points_end

Definition at line 165 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 165 of file biconnectivity.h

cutpoint_iterator biconnectivity::cut_points_end ( )

inline

End of iteration over all cutpoints.

Returns: one-past-the-end iterator.

See Also: biconnectivity::cut_points_begin

Definition at line 174 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 174 of file biconnectivity.h

void biconnectivity::end_handler ( graph & G )

virtual

Handler called at the end of DFS.

Parameters

G	graph for which DFS was invoked.

Reimplemented from dfs.

Definition at line 267 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 267 of file biconnectivity.cpp

References dfs::end(), in_component, it, graph::restore_edge(), self_loops, and store_comp.

Here is the call graph for this function:

void biconnectivity::entry_handler	(	graph &	G,
		node &	n,
		node &	f
	)

virtual

Handler called when touching node n.

Parameters

G	graph for which DFS was invoked.
n	actual node.
f	predecessor.

Reimplemented from dfs.

Definition at line 112 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 112 of file biconnectivity.cpp

References add_edges, dfs::dfs_number, dfs::father(), first_child, and low_num.

Here is the call graph for this function:

void biconnectivity::init_handler ( graph & G )

virtual

Handler called before the start of DFS.

Parameters

G	graph for which DFS was invoked.

Reimplemented from dfs.

Definition at line 69 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 69 of file biconnectivity.cpp

References add_edges, additional, assert, dfs::check(), cut_count, Acts::UnitConstants::e, graph::edges_begin(), graph::edges_end(), dfs::end(), first_child, graph::hide_edge(), in_component, ne_map< Key, Value, Graph, Alloc >::init(), it, low_num, graph::new_edge(), dfs::roots_begin(), dfs::roots_end(), dfs::run(), dfs::scan_whole_graph(), self_loops, edge::source(), dfs::start, and edge::target().

Here is the call graph for this function:

bool biconnectivity::is_biconnected ( ) const

inline

Biconnectivity-test.

Returns: true iff graph is biconnected.

Definition at line 84 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 84 of file biconnectivity.h

Referenced by planarity::run().

Here is the caller graph for this function:

void biconnectivity::leave_handler	(	graph &	G,
		node &	n,
		node &	f
	)

virtual

Handler called after all the adjacent edges of n have been examined.

Parameters

G	graph for which DFS was invoked.
n	actual node.
f	predecessor.

Reimplemented from dfs.

Definition at line 260 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 260 of file biconnectivity.cpp

References cut_count, and cut_points.

int biconnectivity::low_number ( const node & n ) const

inline

low-number.

Parameters

n node.

Returns: low-number of n.

Definition at line 76 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 76 of file biconnectivity.h

References n.

void biconnectivity::make_biconnected ( bool set )

inline

If enabled edges will be added to the graph in order to make it biconnected, if cutpoints are discovered.

The list of added edges can be accessed via additional_begin and additional_end.

Parameters

set	if true additional edges will we inserted to make the graph biconnected.

See Also: biconnectivity::additional_begin, biconnectivity::additional_end

Definition at line 120 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 120 of file biconnectivity.h

References dfs::scan_whole_graph().

Referenced by planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

bool biconnectivity::make_biconnected ( ) const

inline

Returns whether addition of edges neccessary to make graph biconnected is enabled.

Returns: true iff addition edges is enabled.

See Also: biconnectivity::additional_begin, biconnectivity::additional_end

Definition at line 130 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 130 of file biconnectivity.h

void biconnectivity::new_start_handler	(	graph &	G,
		node &	n
	)

virtual

Called when DFS is started with start-node n.

This is particularly useful when DFS was invoked with the scan_whole_graph option.

Parameters

G	graph for which DFS was invoked.
n	start-node.

Reimplemented from dfs.

Definition at line 125 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 125 of file biconnectivity.cpp

References cut_count, node::degree(), dfs::end(), in_component, num_of_components, and store_comp.

Here is the call graph for this function:

int biconnectivity::number_of_components ( ) const

inline

Number von biconnected components detected during the last run.

Returns: number of biconnected components.

Definition at line 214 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 214 of file biconnectivity.h

void biconnectivity::old_adj_node_handler	(	graph &	G,
		edge &	e,
		node &	n
	)

virtual

Handler called when a already marked node n connected to the actual node by e is found during the search of all adjacent edges of the actual node.

Parameters

G	graph for which DFS was invoked.
e	edge connecting the actual node to the old one.
n	used node.

Reimplemented from dfs.

Definition at line 241 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 241 of file biconnectivity.cpp

References dfs::dfs_num(), dfs::dfs_number, edge_stack, low_num, n, node::opposite(), and store_comp.

Here is the call graph for this function:

void biconnectivity::reset ( )

virtual

Resets algorithm.

Prepares the algorithm to be applied to another graph. Please note: The options an algorithm may support do not get reset by this. It is just to reset internally used datastructures.

Reimplemented from dfs.

Definition at line 33 of file biconnectivity.cpp.

View newest version in sPHENIX GitHub at line 33 of file biconnectivity.cpp

References add_edges, additional, dfs::begin(), cut_points, edge_stack, dfs::end(), node_stack, num_of_components, dfs::reset(), and store_comp.

Here is the call graph for this function:

bool biconnectivity::store_components ( ) const

inline

Returns whether the storing of components is enabled.

Returns: true iff storing of components is enabled.

See Also: biconnectivity::components_begin, biconnectivity::components_end

Definition at line 93 of file biconnectivity.h.

View newest version in sPHENIX GitHub at line 93 of file biconnectivity.h

Referenced by planarity::run().

Here is the caller graph for this function:

void biconnectivity::store_components ( bool set )

inline

Enables or disables the storing of biconnected components.

If this feature is enabled, the whole graph will be scanned in order to get all the biconnected components even if the graph isn't connected. By default this feature is disabled.

Parameters