Connected components of a graph
Calculate the maximal (weakly or strongly) connected components of a graph
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, ...)
- The graph to analyze.
- Character string, either
weakor strong. For directed graphs weakimplies weakly, strongstrongly connected components to search. It is ignored for undirected graphs.
- Logical, if TRUE the cumulative distirubution (relative frequency) is calculated.
- Logical. If TRUE the relative frequencies will be multiplied by the cluster sizes.
- Additional attributes to pass to
cluster, right now only
is.connected decides whether the graph is weakly or strongly
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
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.
is.connecteda logical constant.
clustersa 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.
no.clustersan integer constant is returned. For
cluster.distributiona 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.
- Graph component
g <- erdos.renyi.game(20, 1/20) clusters(g)