igraph (version 0.7.1)

clusters: Connected components of a graph

Description

Calculate the maximal (weakly or strongly) connected components of a graph

Usage

is.connected(graph, mode=c("weak", "strong"))
clusters(graph, mode=c("weak", "strong"))
no.clusters(graph, mode=c("weak", "strong"))
cluster.distribution(graph, cumulative = FALSE, mul.size = FALSE, ...)

Arguments

graph

The graph to analyze.

mode

Character string, either weak or strong. For directed graphs weak implies weakly, strong strongly connected components to search. It is ignored for undirected graphs.

cumulative

Logical, if TRUE the cumulative distirubution (relative frequency) is calculated.

mul.size

Logical. If TRUE the relative frequencies will be multiplied by the cluster sizes.

...

Additional attributes to pass to cluster, right now only mode makes sense.

Value

• For is.connected a logical constant.

  For clusters a named list with three components:

• membership
  numeric vector giving the cluster id to which each vertex belongs.
• csize
  numeric vector giving the sizes of the clusters.
• no
  numeric constant, the number of clusters.
• For no.clusters an integer constant is returned. For cluster.distribution a numeric vector with the relative frequencies. The length of the vector is the size of the largest component plus one. Note that (for currently unknown reasons) the first element of the vector is the number of clusters of size zero, so this is always zero.

concept

• Connectedness
• Graph component

Details

is.connected decides whether the graph is weakly or strongly connected.

clusters finds the maximal (weakly or strongly) connected components of a graph.

no.clusters does almost the same as clusters but returns only the number of clusters found instead of returning the actual clusters.

cluster.distribution creates a histogram for the maximal connected component sizes.

The weakly connected components are found by a simple breadth-first search. The strongly connected components are implemented by two consecutive depth-first searches.

See Also

subcomponent

Examples

g <- erdos.renyi.game(20, 1/20)
clusters(g)