Connected components algorithm. More...

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

Inheritance diagram for components:

Collaboration diagram for components:

Public Types
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
	components ()
	Creates connected components algorithm object.

virtual	~components ()
	Destroys connected components algorithm object.

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

virtual void	reset ()
	Resets algorithm.

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

component_iterator	components_end ()
	End of iteration over all components.

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

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

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.

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

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

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

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

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

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

virtual	~algorithm ()
	Destroys the algorithm object.

Protected Attributes
int	num_of_components

list< pair< list< node >, list < edge > > >	comp

component_iterator	li

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

Connected components algorithm.

Definition at line 21 of file components.h.

View newest version in sPHENIX GitHub at line 21 of file components.h

Member Typedef Documentation

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

Definition at line 57 of file components.h.

View newest version in sPHENIX GitHub at line 57 of file components.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE components::components ( )

Creates connected components algorithm object.

See Also: dfs::dfs

Definition at line 24 of file components.cpp.

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

References num_of_components, and dfs::scan_whole_graph().

Here is the call graph for this function:

virtual components::~components ( )

inlinevirtual

Destroys connected components algorithm object.

See Also: dfs::~dfs

Definition at line 36 of file components.h.

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

Member Function Documentation

void components::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 57 of file components.cpp.

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

int components::check ( graph & G )

virtual

Checks whether the connected components algorithm can be applied.

Necessary preconditions:

G is undirected.
scanning of whole graph is enabled.
DFS may be applied

Parameters

G graph.

Returns: algorithm::GTL_OK if connected components can be computed for G.

See Also: dfs::scan_whole_graph

Reimplemented from dfs.

Definition at line 37 of file components.cpp.

View newest version in sPHENIX GitHub at line 37 of file components.cpp

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

Here is the call graph for this function:

component_iterator components::components_begin ( )

inline

Start iteration over all 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

Definition at line 71 of file components.h.

View newest version in sPHENIX GitHub at line 71 of file components.h

References mvtx_utils::comp().

Here is the call graph for this function:

component_iterator components::components_end ( )

inline

End of iteration over all components.

Returns: end of iteration over biconnected components

See Also: biconnectivity::store_components

Definition at line 81 of file components.h.

View newest version in sPHENIX GitHub at line 81 of file components.h

References mvtx_utils::comp().

Here is the call graph for this function:

void components::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 49 of file components.cpp.

View newest version in sPHENIX GitHub at line 49 of file components.cpp

References comp, li, and num_of_components.

int components::number_of_components ( ) const

inline

Number of components detected during the last run.

Returns: number of components.

Definition at line 89 of file components.h.

View newest version in sPHENIX GitHub at line 89 of file components.h

void components::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 64 of file components.cpp.

View newest version in sPHENIX GitHub at line 64 of file components.cpp

References dfs::dfs_num(), and node::opposite().

Here is the call graph for this function:

void components::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 30 of file components.cpp.

View newest version in sPHENIX GitHub at line 30 of file components.cpp

References comp, num_of_components, and dfs::reset().

Here is the call graph for this function: