incremental.components {RBGL} | R Documentation |
Compute connected components for an undirected graph
init.incremental.components(g) incremental.components(g) same.component(g, node1, node2)
g |
an instance of the graph class |
node1 |
one vertex of the given graph |
node2 |
another vertex of the given graph |
This is a family of functions that work together to calculate the connected components of an undirected graph. The algorithm used here is based on the disjoint-sets (fast union-find) data structure which is a good method to use for situations where the graph is growing (edges are being added) and the connected components information needs to be updated repeatedly. This method does not cover the situation where edges are both added and removed from the graph, hence it is called incremental (and not fully dynamic). 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 disjoint-sets info on the previous graph is lost.
|
|
|
{connected components in the current graph }
Li Long <li.long@isb-sib.ch>
Boost Graph Library by Siek et al.
coex <- fromGXL(file(system.file("XML/conn2.gxl",package="RBGL"))) init.incremental.components(coex) incremental.components(coex) v1 <- 1 v2 <- 5 same.component(coex, v1, v2)