Aleph::Unconnected_Components< GT, SA > Class Template Reference

Compute the connected components of a graph. More...

#include <tpl_components.H>

Public Member Functions
	Unconnected_Components (SA arc_filter=SA())
	Construct a component finder with optional arc filter.
template<template< class > class List>
void	compute_blocks (const GT &g, List< GT > &list)
	Compute connected components as mapped subgraphs.
template<template< class > class List>
void	compute_lists (const GT &g, List< List< typename GT::Node * > > &list)
	Compute connected components as lists of node pointers.
void	operator() (const GT &g, DynList< GT > &list)
	Compute connected components as mapped subgraphs.
void	operator() (const GT &g, DynList< DynList< typename GT::Node * > > &list)
	Compute connected components as lists of node pointers.
size_t	count_components (const GT &g)
	Count the number of connected components in a graph.
bool	is_connected (const GT &g)
	Check if a graph is connected.

Private Attributes
SA	sa

Detailed Description

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

Compute the connected components of a graph.

This class takes a graph g (possibly disconnected) and computes all its connected components, storing them as a list of mapped subgraphs or as lists of node pointers.

A connected component is a maximal subgraph in which any two vertices are connected to each other by paths.

Algorithm:

1. Iterate through all nodes of the graph
2. For each unvisited node, perform DFS to find all reachable nodes
3. Store each component as a separate subgraph or node list

Complexity:

• Time: O(V + E) where V is vertices and E is edges
• Space: O(V + E) for the output components

Usage example:

List_Graph<Graph_Node<int>, Graph_Arc<int>> g;
// ... populate possibly disconnected graph ...
 
DynList<decltype(g)> components;
Inconnected_Components<decltype(g)> cc;
cc(g, components);
 
std::cout << "Graph has " << components.size() << " components\n";

Note

The name "Inconnected" is maintained for backward compatibility. It refers to finding components in a potentially disconnected graph.

Uses the Build_Subtree control bit on nodes and arcs.

Template Parameters

GT	Graph type (must satisfy Aleph graph concept).
SA	Arc filter type (default: Dft_Show_Arc<GT>).

See also

Build_Subgraph For building a single component

copy_graph() For copying an entire connected graph

Definition at line 314 of file tpl_components.H.

Constructor & Destructor Documentation

Unconnected_Components()

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

Aleph::Unconnected_Components< GT, SA >::Unconnected_Components ( SA  arc_filter = SA() )

inline

Construct a component finder with optional arc filter.

Parameters

arc_filter

Arc filter to control which arcs are traversed (default: show all arcs).

Definition at line 325 of file tpl_components.H.

Member Function Documentation

compute_blocks()

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

template<template< class > class List>

void Aleph::Unconnected_Components< GT, SA >::compute_blocks ( const GT &  g, List< GT > &  list  )

inline

Compute connected components as mapped subgraphs.

Template Parameters

List	Container template for the output list.

Parameters

[in]	g	Source graph.
[out]	list	Output list of subgraphs, one per component.

Exceptions

std::bad_alloc

If memory allocation fails.

Definition at line 337 of file tpl_components.H.

References Aleph::DynList< T >::append(), Aleph::Build_Subtree, Aleph::count(), GraphCommon< GT, Node, Arc >::get_num_nodes(), IS_NODE_VISITED, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), and Aleph::Unconnected_Components< GT, SA >::sa.

compute_lists()

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

template<template< class > class List>

void Aleph::Unconnected_Components< GT, SA >::compute_lists ( const GT &  g, List< List< typename GT::Node * > > &  list  )

inline

Compute connected components as lists of node pointers.

Template Parameters

List	Container template for the output lists.

Parameters

[in]	g	Source graph.
[out]	list	Output list of node lists, one per component.

Exceptions

std::bad_alloc

If memory allocation fails.

Definition at line 369 of file tpl_components.H.

References Aleph::DynList< T >::append(), Aleph::Build_Subtree, Aleph::count(), GraphCommon< GT, Node, Arc >::get_num_nodes(), IS_NODE_VISITED, l, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), Aleph::Unconnected_Components< GT, SA >::sa, and Aleph::HTList::size().

count_components()

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

size_t Aleph::Unconnected_Components< GT, SA >::count_components ( const GT &  g )

inline

Count the number of connected components in a graph.

Parameters

[in]

g

Source graph.

Returns

Number of connected components.

Definition at line 433 of file tpl_components.H.

References Aleph::maps(), and Aleph::HTList::size().

Referenced by Aleph::Unconnected_Components< GT, SA >::is_connected().

is_connected()

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

bool Aleph::Unconnected_Components< GT, SA >::is_connected ( const GT &  g )

inline

Check if a graph is connected.

Parameters

[in]

g

Source graph.

Returns

true if the graph has exactly one connected component (or is empty), false otherwise.

Definition at line 447 of file tpl_components.H.

References Aleph::Unconnected_Components< GT, SA >::count_components(), and GraphCommon< GT, Node, Arc >::get_num_nodes().

operator()() [1/2]

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

void Aleph::Unconnected_Components< GT, SA >::operator() ( const GT &  g, DynList< DynList< typename GT::Node * > > &  list  )

inline

Compute connected components as lists of node pointers.

Finds all connected components and stores each as a list of pointers to the original nodes in g.

Parameters

[in]	g	Source graph.
[out]	list	Output list of node lists, one per component.

Exceptions

std::bad_alloc

If memory allocation fails.

Note

Uses the Build_Subtree control bit on nodes and arcs.

Definition at line 422 of file tpl_components.H.

References Aleph::maps().

operator()() [2/2]

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

void Aleph::Unconnected_Components< GT, SA >::operator() ( const GT &  g, DynList< GT > &  list  )

inline

Compute connected components as mapped subgraphs.

Finds all connected components in the graph and stores each as a separate mapped subgraph in the output list.

Parameters

[in]	g	Source graph.
[out]	list	Output list of subgraphs, one per component. Each subgraph is mapped to g via cookies.

Exceptions

std::bad_alloc

If memory allocation fails.

Note

Uses the Build_Subtree control bit on nodes and arcs.

Definition at line 405 of file tpl_components.H.

References Aleph::maps().

Member Data Documentation

sa

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

SA Aleph::Unconnected_Components< GT, SA >::sa

private

Definition at line 316 of file tpl_components.H.

Referenced by Aleph::Unconnected_Components< GT, SA >::compute_blocks(), and Aleph::Unconnected_Components< GT, SA >::compute_lists().

---

The documentation for this class was generated from the following file:

• tpl_components.H