edgeConn: computed edge connectivity and min disconnecting set for an...

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

Description

computed edge connectivity and min disconnecting set for an undirected graph

Usage

1

Arguments

g

an instance of the graph class with edgemode “undirected”

Details

Consider a graph G consisting of a single connected component. The edge connectivity of G is the minimum number of edges in G that can be cut to produce a graph with two (disconnected) components. The set of edges in this cut is called the minimum disconnecting set.

Value

A list:

connectivity

the integer describing the number of edges that must be severed to obtain two components

minDisconSet

a list (of length connectivity) of pairs of node names describing the edges that need to be cut to obtain two components

Author(s)

Vince Carey <stvjc@channing.harvard.edu>

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

minCut, edmonds.karp.max.flow, push.relabel.max.flow

Examples

1
2
3
4
5
con <- file(system.file("XML/conn.gxl",package="RBGL"), open="r")
coex <- fromGXL(con)
close(con)

edgeConnectivity(coex)

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