incremental.components
Compute connected components for an undirected graph
Compute connected components for an undirected graph
 Keywords
 models
Usage
init.incremental.components(g)
incremental.components(g)
same.component(g, node1, node2)
Arguments
 g
 an instance of the
graph
class  node1
 one vertex of the given graph
 node2
 another vertex of the given graph
Details
This family of functions work together to calculate the connected components of an undirected graph. The algorithm is based on the disjointsets. It works where the graph is growing by adding new edges. Call "init.incremental.components" to initialize the calculation on a new graph. Call "incremental.components" to recalculate connected components after growing the graph. Call "same.component" to learn if two given vertices are in the same connected components. Currently, the codes can only handle ONE incremental graph at a time. When you start working on another graph by calling "init.incremental.components", the disjointsets info on the previous graph is lost. See documentation on Incremental Connected Components in Boost Graph Library for more details.
Value

Output from
init.incremental.components
is a list of component numbers for each vertex in the graph.Output from incremental.components
is a list of component numbers for each vertex in the graph.Output from same.component
is true if both nodes are in the same connected component, otherwise it's false.
References
Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )
The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, LieQuan Lee, and Andrew Lumsdaine; (AddisonWesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0201729148
See Also
Examples
con < file(system.file("XML/conn2.gxl",package="RBGL"), open="r")
coex < fromGXL(con)
close(con)
init.incremental.components(coex)
incremental.components(coex)
v1 < 1
v2 < 5
same.component(coex, v1, v2)