ConnectedComponentsFinder< T, CompareOrHashT, Eq > Class Template Reference

#include <connected_components.h>

Public Types
using	Set

Public Member Functions
	ConnectedComponentsFinder ()
	Constructs a connected components finder.
	ConnectedComponentsFinder (const ConnectedComponentsFinder &)=delete
ConnectedComponentsFinder &	operator= (const ConnectedComponentsFinder &)=delete
void	AddNode (T node)
bool	AddEdge (T node1, T node2)
bool	Connected (T node1, T node2)
int	GetSize (T node)
std::vector< std::vector< T > >	FindConnectedComponents ()
void	FindConnectedComponents (std::vector< Set > *components)
int	GetNumberOfComponents () const
int	GetNumberOfNodes () const

Detailed Description

template<typename T, typename CompareOrHashT = std::less<T>, typename Eq = void>
class ConnectedComponentsFinder< T, CompareOrHashT, Eq >

Usage: ConnectedComponentsFinder<MyNodeType> cc; cc.AddNode(node1); cc.AddNode(node2); cc.AddEdge(node1, node2); ... repeating, adding nodes and edges as needed. Adding an edge will automatically also add the two nodes at its ends, if they haven't already been added. vector<set<MyNodeType> > components; cc.FindConnectedComponents(&components); Each entry in components now contains all the nodes in a single connected component.

Protocol buffers can be used as the node type. Equality and hash functions for protocol buffers can be found in ortools/base/message_hasher.h.

Usage with flat_hash_set: using ConnectedComponentType = flat_hash_set<MyNodeType>; ConnectedComponentsFinder<ConnectedComponentType::key_type, ConnectedComponentType::hasher, ConnectedComponentType::key_equal> cc; ... vector<ConnectedComponentType> components; cc.FindConnectedComponents(&components);

If you want to, you can continue adding nodes and edges after calling FindConnectedComponents, then call it again later.

If your node type isn't STL-friendly, then you can use pointers to it instead: ConnectedComponentsFinder<MySTLUnfriendlyNodeType*> cc; cc.AddNode(&node1); ... and so on... Of course, in this usage, the connected components finder retains these pointers through its lifetime (though it doesn't dereference them).

Definition at line 229 of file connected_components.h.

Member Typedef Documentation

Set

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

using ConnectedComponentsFinder< T, CompareOrHashT, Eq >::Set

Initial value:

 
      typename internal::ConnectedComponentsTypeHelper<T, CompareOrHashT,
                                                       Eq>::Set

Definition at line 231 of file connected_components.h.

Constructor & Destructor Documentation

ConnectedComponentsFinder() [1/2]

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

ConnectedComponentsFinder< T, CompareOrHashT, Eq >::ConnectedComponentsFinder ( )

inline

Constructs a connected components finder.

Definition at line 236 of file connected_components.h.

ConnectedComponentsFinder() [2/2]

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

ConnectedComponentsFinder< T, CompareOrHashT, Eq >::ConnectedComponentsFinder ( const ConnectedComponentsFinder< T, CompareOrHashT, Eq > & )

delete

Member Function Documentation

AddEdge()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

bool ConnectedComponentsFinder< T, CompareOrHashT, Eq >::AddEdge ( T node1, T node2 )

inline

Adds an edge in the graph. Also adds both endpoint nodes as necessary. It is not an error to add the same edge twice. Self-edges are OK too. Returns true if the two nodes are newly connected, and false if they were already connected.

Definition at line 250 of file connected_components.h.

AddNode()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

void ConnectedComponentsFinder< T, CompareOrHashT, Eq >::AddNode ( T node )

inline

Adds a node in the graph. It is OK to add the same node more than once; additions after the first have no effect.

Definition at line 244 of file connected_components.h.

Connected()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

bool ConnectedComponentsFinder< T, CompareOrHashT, Eq >::Connected ( T node1, T node2 )

inline

Returns true iff both nodes are in the same connected component. Returns false if either node has not been already added with AddNode.

Definition at line 257 of file connected_components.h.

FindConnectedComponents() [1/2]

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

std::vector< std::vector< T > > ConnectedComponentsFinder< T, CompareOrHashT, Eq >::FindConnectedComponents ( )

inline

Finds all the connected components and assigns them to components. Components are ordered in the same way nodes were added, i.e. if node 'b' was added before node 'c', then either:

• 'c' belongs to the same component as a node 'a' added before 'b', or
• the component for 'c' comes after the one for 'b'. There are two versions:
• The first one returns the result, and stores each component in a vector. This is the preferred version.
• The second one populates the result, and stores each component in a set.

Definition at line 278 of file connected_components.h.

FindConnectedComponents() [2/2]

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

void ConnectedComponentsFinder< T, CompareOrHashT, Eq >::FindConnectedComponents ( std::vector< Set > * components )

inline

Definition at line 286 of file connected_components.h.

GetNumberOfComponents()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

int ConnectedComponentsFinder< T, CompareOrHashT, Eq >::GetNumberOfComponents ( ) const

inline

Returns the current number of connected components. This number can change as the new nodes or edges are added.

Definition at line 297 of file connected_components.h.

GetNumberOfNodes()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

int ConnectedComponentsFinder< T, CompareOrHashT, Eq >::GetNumberOfNodes ( ) const

inline

Returns the current number of added distinct nodes. This includes nodes added explicitly via the calls to AddNode() method and implicitly via the calls to AddEdge() method. Nodes that were added several times only count once.

Definition at line 305 of file connected_components.h.

GetSize()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

int ConnectedComponentsFinder< T, CompareOrHashT, Eq >::GetSize ( T node )

inline

Finds the connected component containing a node, and returns the total number of nodes in that component. Returns zero iff the node has not been already added with AddNode.

Definition at line 265 of file connected_components.h.

operator=()

template<typename T , typename CompareOrHashT = std::less<T>, typename Eq = void>

ConnectedComponentsFinder & ConnectedComponentsFinder< T, CompareOrHashT, Eq >::operator= ( const ConnectedComponentsFinder< T, CompareOrHashT, Eq > & )

delete

---

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

• ortools/graph/connected_components.h