# Connected components

*Graphs.jl* includes several functions dealing with connected components.

## Index

`Graphs.attracting_components`

`Graphs.components`

`Graphs.components_dict`

`Graphs.condensation`

`Graphs.connected_components`

`Graphs.connected_components!`

`Graphs.is_connected`

`Graphs.is_strongly_connected`

`Graphs.is_weakly_connected`

`Graphs.isdigraphical`

`Graphs.isgraphical`

`Graphs.neighborhood`

`Graphs.neighborhood_dists`

`Graphs.period`

`Graphs.strongly_connected_components`

`Graphs.strongly_connected_components_kosaraju`

`Graphs.weakly_connected_components`

## Full docs

`Graphs.attracting_components`

— Function`attracting_components(g)`

Return a vector of vectors of integers representing lists of attracting components in the directed graph `g`

.

The attracting components are a subset of the strongly connected components in which the components do not have any leaving edges.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
{5, 6} directed simple Int64 graph
julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
[4, 5]
[1, 2, 3]
julia> attracting_components(g)
1-element Array{Array{Int64,1},1}:
[4, 5]
```

`Graphs.components`

— Method`components(labels)`

Given a vector of component labels, return a vector of vectors representing the vertices associated with a given component id.

`Graphs.components_dict`

— Method`components_dict(labels)`

Convert an array of labels to a map of component id to vertices, and return a map with each key corresponding to a given component id and each value containing the vertices associated with that component.

`Graphs.condensation`

— Function`condensation(g[, scc])`

Return the condensation graph of the strongly connected components `scc`

in the directed graph `g`

. If `scc`

is missing, generate the strongly connected components first.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
{5, 6} directed simple Int64 graph
julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
[4, 5]
[1, 2, 3]
julia> foreach(println, edges(condensation(g)))
Edge 2 => 1
```

`Graphs.connected_components!`

— Method`connected_components!(label, g)`

Fill `label`

with the `id`

of the connected component in the undirected graph `g`

to which it belongs. Return a vector representing the component assigned to each vertex. The component value is the smallest vertex ID in the component.

**Performance**

This algorithm is linear in the number of edges of the graph.

`Graphs.connected_components`

— Method`connected_components(g)`

Return the connected components of an undirected graph `g`

as a vector of components, with each element a vector of vertices belonging to the component.

For directed graphs, see `strongly_connected_components`

and `weakly_connected_components`

.

**Examples**

```
julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);
julia> connected_components(g)
1-element Array{Array{Int64,1},1}:
[1, 2, 3]
julia> g = SimpleGraph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> connected_components(g)
2-element Array{Array{Int64,1},1}:
[1, 2, 3]
[4, 5]
```

`Graphs.is_connected`

— Method`is_connected(g)`

Return `true`

if graph `g`

is connected. For directed graphs, return `true`

if graph `g`

is weakly connected.

**Examples**

```
julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);
julia> is_connected(g)
true
julia> g = SimpleGraph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> is_connected(g)
false
julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_connected(g)
true
```

`Graphs.is_strongly_connected`

— Function`is_strongly_connected(g)`

Return `true`

if directed graph `g`

is strongly connected.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_strongly_connected(g)
true
```

`Graphs.is_weakly_connected`

— Method`is_weakly_connected(g)`

Return `true`

if the graph `g`

is weakly connected. If `g`

is undirected, this function is equivalent to `is_connected(g)`

.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_weakly_connected(g)
true
julia> g = SimpleDiGraph([0 1 0; 1 0 1; 0 0 0]);
julia> is_connected(g)
true
julia> is_strongly_connected(g)
false
julia> is_weakly_connected(g)
true
```

`Graphs.isdigraphical`

— Method`isdigraphical(indegree_sequence, outdegree_sequence)`

Check whether the given indegree sequence and outdegree sequence are digraphical, that is whether they can be the indegree and outdegree sequence of a simple digraph (i.e. a directed graph with no loops). This implies that `indegree_sequence`

and `outdegree_sequence`

are not independent, as their elements respectively represent the indegrees and outdegrees that the vertices shall have.

**Implementation Notes**

According to Fulkerson-Chen-Anstee theorem, a sequence $\{(a_1, b_1), ...,(a_n, b_n)\}$ (sorted in descending order of a) is graphic iff $\sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i\}$ and the sequence obeys the property -

\[\sum_{i=1}^{r} a_i \leq \sum_{i=1}^n min(r-1,b_i) + \sum_{i=r+1}^n min(r,b_i)\]

for each integer 1 <= r <= n-1.

See also: `isgraphical`

`Graphs.isgraphical`

— Method`isgraphical(degs)`

Return true if the degree sequence `degs`

is graphical. A sequence of integers is called graphical, if there exists a graph where the degrees of its vertices form that same sequence.

**Performance**

Time complexity: $\mathcal{O}(|degs|*\log(|degs|))$.

**Implementation Notes**

According to Erdös-Gallai theorem, a degree sequence $\{d_1, ...,d_n\}$ (sorted in descending order) is graphic iff the sum of vertex degrees is even and the sequence obeys the property -

\[\sum_{i=1}^{r} d_i \leq r(r-1) + \sum_{i=r+1}^n min(r,d_i)\]

for each integer r <= n-1.

See also: `isdigraphical`

`Graphs.neighborhood`

— Method`neighborhood(g, v, d, distmx=weights(g))`

Return a vector of each vertex in `g`

at a geodesic distance less than or equal to `d`

, where distances may be specified by `distmx`

.

**Optional Arguments**

`dir=:out`

: If`g`

is directed, this argument specifies the edge direction

with respect to `v`

of the edges to be considered. Possible values: `:in`

or `:out`

.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> neighborhood(g, 1, 2)
3-element Array{Int64,1}:
1
2
3
julia> neighborhood(g, 1, 3)
4-element Array{Int64,1}:
1
2
3
4
julia> neighborhood(g, 1, 3, [0 1 0 0 0; 0 0 1 0 0; 1 0 0 0.25 0; 0 0 0 0 0.25; 0 0 0 0.25 0])
5-element Array{Int64,1}:
1
2
3
4
5
```

`Graphs.neighborhood_dists`

— Method`neighborhood_dists(g, v, d, distmx=weights(g))`

Return a a vector of tuples representing each vertex which is at a geodesic distance less than or equal to `d`

, along with its distance from `v`

. Non-negative distances may be specified by `distmx`

.

**Optional Arguments**

`dir=:out`

: If`g`

is directed, this argument specifies the edge direction

with respect to `v`

of the edges to be considered. Possible values: `:in`

or `:out`

.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);
julia> neighborhood_dists(g, 1, 3)
4-element Array{Tuple{Int64,Int64},1}:
(1, 0)
(2, 1)
(3, 2)
(4, 3)
julia> neighborhood_dists(g, 1, 3, [0 1 0 0 0; 0 0 1 0 0; 1 0 0 0.25 0; 0 0 0 0 0.25; 0 0 0 0.25 0])
5-element Array{Tuple{Int64,Float64},1}:
(1, 0.0)
(2, 1.0)
(3, 2.0)
(4, 2.25)
(5, 2.5)
julia> neighborhood_dists(g, 4, 3)
2-element Array{Tuple{Int64,Int64},1}:
(4, 0)
(5, 1)
julia> neighborhood_dists(g, 4, 3, dir=:in)
5-element Array{Tuple{Int64,Int64},1}:
(4, 0)
(3, 1)
(5, 1)
(2, 2)
(1, 3)
```

`Graphs.period`

— Function`period(g)`

Return the (common) period for all vertices in a strongly connected directed graph. Will throw an error if the graph is not strongly connected.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> period(g)
3
```

`Graphs.strongly_connected_components`

— Function`strongly_connected_components(g)`

Compute the strongly connected components of a directed graph `g`

.

Return an array of arrays, each of which is the entire connected component.

**Implementation Notes**

The order of the components is not part of the API contract.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0; 1 0 1; 0 0 0]);
julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
[3]
[1, 2]
julia> g=SimpleDiGraph(11)
{11, 0} directed simple Int64 graph
julia> edge_list=[(1,2),(2,3),(3,4),(4,1),(3,5),(5,6),(6,7),(7,5),(5,8),(8,9),(9,8),(10,11),(11,10)];
julia> g = SimpleDiGraph(Edge.(edge_list))
{11, 13} directed simple Int64 graph
julia> strongly_connected_components(g)
4-element Array{Array{Int64,1},1}:
[8, 9]
[5, 6, 7]
[1, 2, 3, 4]
[10, 11]
```

`Graphs.strongly_connected_components_kosaraju`

— Function`strongly_connected_components_kosaraju(g)`

Compute the strongly connected components of a directed graph `g`

using Kosaraju's Algorithm. (https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm).

Return an array of arrays, each of which is the entire connected component.

**Performance**

Time Complexity : O(|E|+|V|) Space Complexity : O(|V|) {Excluding the memory required for storing graph}

|V| = Number of vertices |E| = Number of edges

**Examples**

```
julia> g=SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> g = SimpleDiGraph([0 1 0 ; 0 0 1; 0 0 0])
{3, 2} directed simple Int64 graph
julia> strongly_connected_components_kosaraju(g)
3-element Array{Array{Int64,1},1}:
[1]
[2]
[3]
julia> g=SimpleDiGraph(11)
{11, 0} directed simple Int64 graph
julia> edge_list=[(1,2),(2,3),(3,4),(4,1),(3,5),(5,6),(6,7),(7,5),(5,8),(8,9),(9,8),(10,11),(11,10)]
13-element Array{Tuple{Int64,Int64},1}:
(1, 2)
(2, 3)
(3, 4)
(4, 1)
(3, 5)
(5, 6)
(6, 7)
(7, 5)
(5, 8)
(8, 9)
(9, 8)
(10, 11)
(11, 10)
julia> g = SimpleDiGraph(Edge.(edge_list))
{11, 13} directed simple Int64 graph
julia> strongly_connected_components_kosaraju(g)
4-element Array{Array{Int64,1},1}:
[11, 10]
[2, 3, 4, 1]
[6, 7, 5]
[9, 8]
```

`Graphs.weakly_connected_components`

— Method`weakly_connected_components(g)`

Return the weakly connected components of the graph `g`

. This is equivalent to the connected components of the undirected equivalent of `g`

. For undirected graphs this is equivalent to the `connected_components`

of `g`

.

**Examples**

```
julia> g = SimpleDiGraph([0 1 0; 1 0 1; 0 0 0]);
julia> weakly_connected_components(g)
1-element Array{Array{Int64,1},1}:
[1, 2, 3]
```