connectedComp: Identify Connected Components in an Undirected Graph

In RBGL: An interface to the BOOST graph library

Description

The connected components in an undirected graph are identified. If the graph is directed then the weakly connected components are identified.

Usage

connectedComp(g)

Arguments

g	graph with edgemode “undirected”

Details

Uses a depth first search approach to identifying all the connected components of an undirected graph. If the input, g, is a directed graph it is first transformed to an undirected graph (using ugraph).

Value

A list of length equal to the number of connected components in g. Each element of the list contains a vector of the node labels for the nodes that are connected.

Author(s)

Vince Carey <[e-mail]>

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,strongComp, ugraph, same.component

Examples

con <- file(system.file("GXL/kmstEx.gxl",package="graph"), open="r")
km <- fromGXL(con)
close(con)
km <- graph::addNode(c("F","G","H"), km)
km <- addEdge("G", "H", km, 1)
km <- addEdge("H", "G", km, 1)
ukm <- ugraph(km)
ukm
edges(ukm)
connectedComp(ukm)

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, cbind, colMeans, colSums, colnames, 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

A graphNEL graph with undirected edges
Number of Nodes = 8 
Number of Edges = 8 
$A
[1] "C" "E"

$B
[1] "D" "E" "C"

$C
[1] "B" "D" "A"

$D
[1] "E" "B" "C"

$E
[1] "A" "B" "D"

$F
character(0)

$G
[1] "H"

$H
[1] "G"

$`1`
[1] "A" "B" "C" "D" "E"

$`2`
[1] "F"

$`3`
[1] "G" "H"

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