DenseConnectedComponentsFinder Class Reference

A connected components finder that only works on dense ints. More...

#include <connected_components.h>

Public Member Functions
	DenseConnectedComponentsFinder ()
	DenseConnectedComponentsFinder (const DenseConnectedComponentsFinder &)=default
	We support copy and move construction.
DenseConnectedComponentsFinder &	operator= (const DenseConnectedComponentsFinder &)=default
	DenseConnectedComponentsFinder (DenseConnectedComponentsFinder &&)=default
DenseConnectedComponentsFinder &	operator= (DenseConnectedComponentsFinder &&)=default
bool	AddEdge (int node1, int node2)
bool	Connected (int node1, int node2)
int	GetSize (int node)
int	GetNumberOfComponents () const
int	GetNumberOfNodes () const
const std::vector< int > &	GetComponentRoots ()
void	SetNumberOfNodes (int num_nodes)
int	FindRoot (int node)
std::vector< int >	GetComponentIds ()
	Returns the same as GetConnectedComponents().

Detailed Description

A connected components finder that only works on dense ints.

NOTE(user): The rest of the functions below should also be in namespace util, but for historical reasons it hasn't been done yet.

Definition at line 88 of file connected_components.h.

Constructor & Destructor Documentation

DenseConnectedComponentsFinder() [1/3]

DenseConnectedComponentsFinder::DenseConnectedComponentsFinder ( )

inline

Definition at line 90 of file connected_components.h.

DenseConnectedComponentsFinder() [2/3]

DenseConnectedComponentsFinder::DenseConnectedComponentsFinder ( const DenseConnectedComponentsFinder & )

default

We support copy and move construction.

DenseConnectedComponentsFinder() [3/3]

DenseConnectedComponentsFinder::DenseConnectedComponentsFinder ( DenseConnectedComponentsFinder && )

default

Member Function Documentation

AddEdge()

bool DenseConnectedComponentsFinder::AddEdge	(	int	node1,
		int	node2 )

The main API is the same as ConnectedComponentsFinder (below): see the homonymous functions there.

Grow if needed.

Just union the sets for node1 and node2.

Already the same set.

Attach the shallowest tree to root of the deepest one. Note that this operation grows the rank of the new common root by at most one (if the two trees originally have the same rank).

If the ranks were the same then attaching just grew the rank by one.

Definition at line 98 of file connected_components.cc.

Connected()

bool DenseConnectedComponentsFinder::Connected	(	int	node1,
		int	node2 )

Definition at line 136 of file connected_components.cc.

FindRoot()

int DenseConnectedComponentsFinder::FindRoot

(

int

node

)

Returns the root of the set for the given node. node must be in [0;GetNumberOfNodes()-1]. Non-const because it does path compression internally.

Search the root.

Apply path compression.

Definition at line 56 of file connected_components.cc.

GetComponentIds()

std::vector< int > DenseConnectedComponentsFinder::GetComponentIds

(

)

Returns the same as GetConnectedComponents().

This is the first node in a yet unseen component.

Definition at line 151 of file connected_components.cc.

GetComponentRoots()

const std::vector< int > & DenseConnectedComponentsFinder::GetComponentRoots

(

)

Gets the current set of root nodes in sorted order. Runs in amortized O(#components) time.

Add potential roots for each new node that did not exist the last time GetComponentRoots() was called. The cost here is amortized against adding the nodes in the first place.

Remove the roots that have been merged with other components. Each node only gets removed once from the roots vector, so the cost of FindRoot() is amortized against adding the edge.

Definition at line 75 of file connected_components.cc.

GetNumberOfComponents()

int DenseConnectedComponentsFinder::GetNumberOfComponents ( ) const

inline

Definition at line 106 of file connected_components.h.

GetNumberOfNodes()

int DenseConnectedComponentsFinder::GetNumberOfNodes ( ) const

inline

Definition at line 107 of file connected_components.h.

GetSize()

int DenseConnectedComponentsFinder::GetSize

(

int

node

)

Definition at line 144 of file connected_components.cc.

operator=() [1/2]

DenseConnectedComponentsFinder & DenseConnectedComponentsFinder::operator= ( const DenseConnectedComponentsFinder & )

default

operator=() [2/2]

DenseConnectedComponentsFinder & DenseConnectedComponentsFinder::operator= ( DenseConnectedComponentsFinder && )

default

SetNumberOfNodes()

void DenseConnectedComponentsFinder::SetNumberOfNodes

(

int

num_nodes

)

Sets the number of nodes in the graph. The graph can only grow: this dies if "num_nodes" is lower or equal to any of the values ever given to AddEdge(), or lower than a previous value given to SetNumberOfNodes(). You need this if there are nodes that don't have any edges.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. The following uses disjoint-sets algorithms, see: https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests

Each new node starts as an isolated component: It has itself as root.

It's in an isolated component of size 1.

Its rank is 0.

This introduces one extra component per added node.

Definition at line 38 of file connected_components.cc.

---

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

• ortools/graph/connected_components.h
• ortools/graph/connected_components.cc