lal::properties::connected_components< graph_t > Class Template Reference

The connected components of a graph. More...

#include <connected_components.hpp>

Public Types
typedef std::vector< graph_t >::const_iterator	const_iterator
	Useful typedef for constant iterators.
typedef std::vector< graph_t >::iterator	iterator
	Useful typedef for non-constant iterators.

Public Member Functions
graph_t &	operator[] (const std::size_t i) noexcept
	Access operator.
const graph_t &	operator[] (const std::size_t i) const noexcept
	Access operator.
void	init (const std::size_t n) noexcept
	Initializes this object.
void	add_graph (graph_t &&g) noexcept
	Add a graph to the list of connected components.
void	add_graph (const graph_t &g) noexcept
	Add a graph to the list of connected components.
void	set_node_cc (const node u, const std::size_t label) noexcept
	Relates vertex u to the label of its connected component.
void	set_label_graph_node_to_cc_node (const node u, const std::size_t label) noexcept
	Relates vertex u to the corresponding vertex within its connected component.
void	set_label_cc_node_to_graph_node (const std::size_t cc_idx, const node u, const std::size_t label) noexcept
	Relates vertex u to the corresponding vertex within its connected component.
std::size_t	size () const noexcept
	Returns the number of connected components.
std::size_t	get_cc_node (const node u) const noexcept
	Returns the label of the connected component u belongs to.
std::size_t	get_label_graph_node_to_cc_node (const node u) const noexcept
	The corresponding vertex within its connected component.
std::size_t	get_label_cc_node_to_graph_node (const std::size_t cc_idx, const node u) const noexcept
	The corresponding vertex within its connected component.
const_iterator	begin () const noexcept
	A pointer to the beginning of the sequence of connected components.
iterator	begin () noexcept
	A pointer to the beginning of the sequence of connected components.
const_iterator	end () const noexcept
	A pointer to the end of the sequence of connected components.
iterator	end () noexcept
	A pointer to the end of the sequence of connected components.

Private Attributes
std::vector< graph_t >	m_connected_components
	The connected components of the graph.
std::vector< detail::array< std::size_t > >	m__cc_node__to__graph_node
detail::array< std::size_t >	m__graph_node__to__cc_node
detail::array< std::size_t >	m_node_to_cc
	The label of the connected component a vertex belongs to.

Detailed Description

template<class graph_t>
class lal::properties::connected_components< graph_t >

The connected components of a graph.

This class is to be used paired with another graph.

Template Parameters

graph_t

Type of graph.

Member Function Documentation

get_cc_node()

template<class graph_t >

std::size_t lal::properties::connected_components< graph_t >::get_cc_node ( const node u ) const

inlinenodiscardnoexcept

Returns the label of the connected component u belongs to.

Parameters

u	Node of the original graph.

Returns

A numeric value from 0 to the number of connected components (see size())

get_label_cc_node_to_graph_node()

template<class graph_t >

std::size_t lal::properties::connected_components< graph_t >::get_label_cc_node_to_graph_node ( const std::size_t cc_idx, const node u ) const

inlinenodiscardnoexcept

The corresponding vertex within its connected component.

Parameters

cc_idx	The label of the connected component of u.
u	Input node (within the connected component).

Returns

The label of u in the whole graph.

get_label_graph_node_to_cc_node()

template<class graph_t >

std::size_t lal::properties::connected_components< graph_t >::get_label_graph_node_to_cc_node ( const node u ) const

inlinenodiscardnoexcept

The corresponding vertex within its connected component.

Parameters

u	Input node (of the original graph).

Returns

The label of the vertex u within its connected component.

init()

template<class graph_t >

void lal::properties::connected_components< graph_t >::init ( const std::size_t n )

inlinenoexcept

Initializes this object.

Parameters

n	Number of nodes.

Postcondition

m_node_to_cc is initialized.

set_label_cc_node_to_graph_node()

template<class graph_t >

void lal::properties::connected_components< graph_t >::set_label_cc_node_to_graph_node ( const std::size_t cc_idx, const node u, const std::size_t label )

inlinenoexcept

Relates vertex u to the corresponding vertex within its connected component.

Parameters

cc_idx	The label of the connected component of u.
u	Input node (within the connected component).
label	The label of u in the whole graph.

set_label_graph_node_to_cc_node()

template<class graph_t >

void lal::properties::connected_components< graph_t >::set_label_graph_node_to_cc_node ( const node u, const std::size_t label )

inlinenoexcept

Relates vertex u to the corresponding vertex within its connected component.

Parameters

u	Input node (of the original graph).
label	The label of the vertex u within its connected component.

set_node_cc()

template<class graph_t >

void lal::properties::connected_components< graph_t >::set_node_cc ( const node u, const std::size_t label )

inlinenoexcept

Relates vertex u to the label of its connected component.

Parameters

u	Input node (of the original graph).
label	The label of the connected component of u.

Member Data Documentation

m__cc_node__to__graph_node

template<class graph_t >

std::vector<detail::array<std::size_t> > lal::properties::connected_components< graph_t >::m__cc_node__to__graph_node

private

Relates the vertices in each connected components to their corresponding vertex in the original graph.

m__graph_node__to__cc_node

template<class graph_t >

detail::array<std::size_t> lal::properties::connected_components< graph_t >::m__graph_node__to__cc_node

private

Relates the vertices in the original graph components to their corresponding vertex in the connected_component.

---

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

• lal/properties/connected_components.hpp