incrConnComp: Compute connected components for an undirected graph

Description Usage Arguments Details Value Author(s) References See Also Examples

Description

Compute connected components for an undirected graph

Usage

1
2
3

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 disjoint-sets. 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 re-calculate 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 disjoint-sets 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.

Author(s)

Li Long <li.long@isb-sib.ch>

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, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

See Also

connComp, connectedComp, strongComp

Examples

1
2
3
4
5
6
7
8
9
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)

Example output

Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, sd, var, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, basename, cbind, colMeans, colSums, colnames,
    dirname, do.call, duplicated, eval, evalq, get, grep, grepl,
    intersect, is.unsorted, lapply, lengths, mapply, match, mget,
    order, paste, pmax, pmax.int, pmin, pmin.int, rank, rbind,
    rowMeans, rowSums, rownames, sapply, setdiff, sort, table, tapply,
    union, unique, unsplit, which, which.max, which.min

[[1]]
no. of initial components 
                        8 

[[2]]
[1] "A"

[[3]]
[1] "B"

[[4]]
[1] "C"

[[5]]
[1] "D"

[[6]]
[1] "E"

[[7]]
[1] "G"

[[8]]
[1] "H"

[[9]]
[1] "F"

[[1]]
no. of connected components 
                          1 

[[2]]
[1] "B" "A" "C" "D" "E" "G" "H" "F"

[1] TRUE

RBGL documentation built on Nov. 8, 2020, 5 p.m.