# Directed graphs

*Graphs.jl* includes some algorithms that are specific to directed graphs.

## Index

## Full docs

`Graphs.transitiveclosure`

— Function`transitiveclosure(g, selflooped=false)`

Compute the transitive closure of a directed graph, using DFS. Return a graph representing the transitive closure. If `selflooped`

is `true`

, add self loops to the graph.

**Performance**

Time complexity is $\mathcal{O}(|E||V|)$.

**Examples**

```
julia> using Graphs
julia> barbell = blockdiag(complete_digraph(3), complete_digraph(3));
julia> add_edge!(barbell, 1, 4);
julia> ne(barbell)
13
julia> ne(transitiveclosure(barbell))
21
```

`Graphs.transitiveclosure!`

— Function`transitiveclosure!(g, selflooped=false)`

Compute the transitive closure of a directed graph, using DFS. If `selflooped`

is true, add self loops to the graph.

**Performance**

Time complexity is $\mathcal{O}(|E||V|)$.

**Implementation Notes**

This version of the function modifies the original graph.

`Graphs.transitivereduction`

— Function`transitivereduction(g; selflooped=false)`

Compute the transitive reduction of a directed graph. If the graph contains cycles, each strongly connected component is replaced by a directed cycle and the transitive reduction is calculated on the condensation graph connecting the components. If `selflooped`

is true, self loops on strongly connected components of size one will be preserved.

**Performance**

Time complexity is $\mathcal{O}(|V||E|)$.

**Examples**

```
julia> using Graphs
julia> barbell = blockdiag(complete_digraph(3), complete_digraph(3));
julia> add_edge!(barbell, 1, 4);
julia> collect(edges(barbell))
13-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 2 => 1
Edge 2 => 3
Edge 3 => 1
Edge 3 => 2
Edge 4 => 5
Edge 4 => 6
Edge 5 => 4
Edge 5 => 6
Edge 6 => 4
Edge 6 => 5
julia> collect(edges(transitivereduction(barbell)))
7-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 4
Edge 2 => 3
Edge 3 => 1
Edge 4 => 5
Edge 5 => 6
Edge 6 => 4
```