Calculate the maximal (weakly or strongly) connected components of a graph
Arguments
- graph
The graph to analyze.
- 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 onlymode
makes sense.- 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.
Value
For is_connected()
a logical constant.
For components()
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 count_components()
an integer constant is returned.
For component_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.
For largest_component()
the largest connected component of the graph.
Details
is_connected()
decides whether the graph is weakly or strongly
connected. The null graph is considered disconnected.
components()
finds the maximal (weakly or strongly) connected components
of a graph.
count_components()
does almost the same as components()
but returns only
the number of clusters found instead of returning the actual clusters.
component_distribution()
creates a histogram for the maximal connected
component sizes.
largest_component()
returns the largest connected component of a graph. For
directed graphs, optionally the largest weakly or strongly connected component.
In case of a tie, the first component by vertex ID order is returned. Vertex
IDs from the original graph are not retained in the returned graph.
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
decompose()
, subcomponent()
, groups()
Connected components
articulation_points()
,
biconnected_components()
,
decompose()
Other structural.properties:
bfs()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
dfs()
,
distance_table()
,
edge_density()
,
feedback_arc_set()
,
girth()
,
is_acyclic()
,
is_dag()
,
is_matching()
,
k_shortest_paths()
,
knn()
,
laplacian_matrix()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()
Author
Gabor Csardi csardi.gabor@gmail.com
Examples
g <- sample_gnp(20, 1 / 20)
clu <- components(g)
groups(clu)
#> $`1`
#> [1] 1 2 5 7 9 11 17 19
#>
#> $`2`
#> [1] 3 14
#>
#> $`3`
#> [1] 4 8 10
#>
#> $`4`
#> [1] 6
#>
#> $`5`
#> [1] 12
#>
#> $`6`
#> [1] 13
#>
#> $`7`
#> [1] 15
#>
#> $`8`
#> [1] 16
#>
#> $`9`
#> [1] 18
#>
#> $`10`
#> [1] 20
#>
largest_component(g)
#> IGRAPH 7857f16 U--- 8 8 -- Erdos-Renyi (gnp) graph
#> + attr: name (g/c), type (g/c), loops (g/l), p (g/n)
#> + edges from 7857f16:
#> [1] 1--3 2--3 2--5 3--6 3--7 4--7 3--8 5--8