|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
#include <connectivity.h>
Public Member Functions | |
| ConnectedComponents () | |
| ~ConnectedComponents () | |
| void | Init (NodeIndex num_nodes) |
| Reserves memory for num_nodes and resets the data structures. | |
| void | AddArc (NodeIndex tail, NodeIndex head) |
| Adds the information that NodeIndex tail and NodeIndex head are connected. | |
| void | AddGraph (const StarGraph &graph) |
| Adds a complete StarGraph to the object. | |
| NodeIndex | CompressPath (NodeIndex node) |
| Compresses the path for node. | |
| NodeIndex | GetClassRepresentative (NodeIndex node) |
| Returns the equivalence class representative for node. | |
| NodeIndex | GetNumberOfConnectedComponents () |
| Returns the number of connected components. | |
| void | MergeClasses (NodeIndex node1, NodeIndex node2) |
| Merges the equivalence classes of node1 and node2. | |
See Cormen et al. 2nd Edition. MIT Press, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524. and Tarjan (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM 22(2):215–225 It is implemented as a template so that the size of NodeIndex can be chosen depending on the size of the graphs considered. The main interest is that arcs do not need to be kept. Thus the memory complexity is O(n) where n is the number of nodes in the graph. The complexity of this algorithm is O(n . alpha(n)) where alpha(n) is the inverse Ackermann function. alpha(n) <= log(log(log(..log(log(n))..) In practice alpha(n) <= 5. See Tarjan and van Leeuwen (1984). Worst-case analysis of set union algorithms. Journal of the ACM 31(2):245–281.
Usage example: ConnectedComponents components; components.Init(num_nodes); for (ArcIndex arc = 0; arc < num_arcs; ++arc) { components.AddArc(tail[arc], head[arc]); } int num_connected_components = components.GetNumberOfConnectedComponents(); if (num_connected_components == 1) { Graph is completely connected. } Group the nodes in the same connected component together. group[class_number][i] contains the i-th node in group class_number. hash_map<NodeIndex, std::vector<NodeIndex> > group(num_connected_components); for (NodeIndex node = 0; node < num_nodes; ++node) { group[components.GetClassRepresentative(node)].push_back(node); }
NodeIndex is used to denote both a node index and a number of nodes, as passed as parameter to Init.
Keywords: graph, connected components.
Definition at line 68 of file connectivity.h.
| operations_research::ConnectedComponents::ConnectedComponents | ( | ) | [inline] |
Definition at line 70 of file connectivity.h.
| operations_research::ConnectedComponents::~ConnectedComponents | ( | ) | [inline] |
Definition at line 76 of file connectivity.h.
| void operations_research::ConnectedComponents::Init | ( | NodeIndex | num_nodes | ) | [inline] |
Reserves memory for num_nodes and resets the data structures.
Definition at line 79 of file connectivity.h.
Adds the information that NodeIndex tail and NodeIndex head are connected.
Definition at line 36 of file connectivity.cc.
| void operations_research::ConnectedComponents::AddGraph | ( | const StarGraph & | graph | ) |
Adds a complete StarGraph to the object.
Note that Depth-First Search is a better algorithm for finding connected components on graphs.
Definition at line 46 of file connectivity.cc.
Returns the equivalence class representative for node.
Definition at line 69 of file connectivity.cc.
| NodeIndex operations_research::ConnectedComponents::GetNumberOfConnectedComponents | ( | ) |
Returns the number of connected components.
Allocates num_nodes_ bits for the computation.
Definition at line 83 of file connectivity.cc.