# Cycles

*Graphs.jl* contains numerous algorithms related to cycles.

## Index

`Graphs.DenseGraphICT_BFGT_N`

`Graphs.IncrementalCycleTracker`

`Graphs.JohnsonVisitor`

`Graphs.TransactionalVector`

`Graphs.add_edge_checked!`

`Graphs.circuit`

`Graphs.circuit_iter`

`Graphs.circuit_recursive!`

`Graphs.cycle_basis`

`Graphs.itercycles`

`Graphs.karp_minimum_cycle_mean`

`Graphs.maxsimplecycles`

`Graphs.maxsimplecycles`

`Graphs.ncycles_n_i`

`Graphs.resetB!`

`Graphs.resetblocked!`

`Graphs.simplecycles`

`Graphs.simplecycles_hawick_james`

`Graphs.simplecycles_iter`

`Graphs.simplecycles_limited_length`

`Graphs.simplecyclescount`

`Graphs.simplecycleslength`

`Graphs.unblock!`

`Graphs.unblock!`

## Full docs

`Graphs.cycle_basis`

— Function`cycle_basis(g, root=nothing)`

Return a list of cycles which form a basis for cycles of the undirected graph `g`

, optionally starting at node `root`

.

A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis. Here summation of cycles is defined as "exclusive or" of the edges. Cycle bases are useful, e.g. when deriving equations for electric circuits using Kirchhoff's Laws.

**Examples**

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

**References**

- Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518. [https://dl.acm.org/citation.cfm?id=363232]

`Graphs.circuit_recursive!`

— Function`circuit_recursive!(g, v1, v2, blocked, B, stack, cycles)`

Find circuits in `g`

recursively starting from v1.

`Graphs.resetB!`

— Method`resetB!(B)`

Reset B work structure.

`Graphs.resetblocked!`

— Method`resetblocked!(blocked)`

Reset vector of `blocked`

vertices.

`Graphs.simplecycles_hawick_james`

— Function`simplecycles_hawick_james(g)`

Find circuits (including self-loops) in `g`

using the algorithm of Hawick & James.

**References**

- Hawick & James, "Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs", 2008

`Graphs.unblock!`

— Method`unblock!(v, blocked, B)`

Unblock the value `v`

from the `blocked`

list and remove from `B`

.

`Graphs.DenseGraphICT_BFGT_N`

— Type`struct DenseGraphICT_BFGT_N`

Implements the "Naive" (Algorithm N) Bender-Fineman-Gilbert-Tarjan one-way line search incremental cycle detector for dense graphs from BFGT15 (Section 3).

**References**

BFGT15: Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. 2015 A New Approach to Incremental Cycle Detection and Related Problems. ACM Trans. Algorithms 12, 2, Article 14 (December 2015), 22 pages. DOI: http://dx.doi.org/10.1145/2756553

`Graphs.IncrementalCycleTracker`

— Type`abstract type IncrementalCycleTracker`

The supertype for incremental cycle detection problems. The abstract type constructor IncrementalCycleTracker(G) may be used to automatically select a specific incremental cycle detection algorithm. See `add_edge_checked!`

for a usage example.

`Graphs.TransactionalVector`

— Type`struct TransactionalVector`

A vector with one checkpoint that may be reverted to by calling `revert!`

. The setpoint itself is set by calling `commit!`

.

`Graphs.add_edge_checked!`

— Function`add_edge_checked!([f!,], ict::IncrementalCycleTracker, v, w)`

Using the incremental cycle tracker, ict, check whether adding the edge `v=>w`

would introduce a cycle in the underlying graph. If so, return false and leave the ict intact. If not, update the underlying graph and return true.

**Optional f! Argument**

By default the `add_edge!`

function is used to update the underlying graph. However, for more complicated graphs, users may wish to manually specify the graph update operation. This may be accomplished by passing the optional `f!`

callback argument. This callback is called on the underlying graph when no cycle is detected and is required to modify the underlying graph in order to effectuate the proposed edge addition.

**Batched edge additions**

Optionally, either `v`

or `w`

(depending on the `in_out_reverse`

flag) may be a collection of vertices representing a batched addition of vertices sharing a common source or target more efficiently than individual updates.

**Example**

```
julia> G = SimpleDiGraph(3)
julia> ict = IncrementalCycleTracker(G)
BFGT_N cycle tracker on {3, 0} directed simple Int64 graph
julia> add_edge_checked!(ict, 1, 2)
true
julia> collect(edges(G))
1-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
julia> add_edge_checked!(ict, 2, 3)
true
julia> collect(edges(G))
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
julia> add_edge_checked!(ict, 3, 1) # Would add a cycle
false
julia> collect(edges(G))
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 2 => 3
```

`Graphs.JohnsonVisitor`

— Type```
type JohnsonVisitor{T<:Integer} <: Visitor{T}
stack::Vector{T}
blocked::BitVector
blockedmap::Vector{Set{T}}
end
JohnsonVisitor(dg::::IsDirected)
```

Composite type that regroups the information needed for Johnson's algorithm.

`stack`

is the stack of visited vertices. `blocked`

is a boolean for each vertex that tells whether it is blocked or not. `blockedmap`

tells which vertices to unblock if the key vertex is unblocked.

`JohnsonVisitor`

may also be constructed directly from the directed graph.

`Graphs.circuit`

— Function```
circuit{T<:Integer}(v::T, dg::::IsDirected, vis::JohnsonVisitor{T},
allcycles::Vector{Vector{T}}, vmap::Vector{T}, startnode::T = v)
```

Return one step of the recursive version of simple cycle detection, using a DFS algorithm.

`v`

: the vertex considered in this iteration of the DFS`dg`

: the digraph from which cycles are computed`visitor`

: Informations needed for the cycle computation, contains:`stack`

: the stack of parent vertices`blocked`

: tells whether a vertex has already been explored or not`blockedmap`

: mapping of the blocking / unblocking consequences

`allcycles`

: output containing the cycles already detected`vmap`

: vector map containing the link from the old to the new nodes of the directed graph`startnode = v`

: optional argument giving the starting node. In the first iteration,

the same as v, otherwise it should be passed.

**Implementation Notes**

Implements Johnson's CIRCUIT function. This is a recursive version. Modifies the vector of cycles, when needed.

**References**

`Graphs.circuit_iter`

— Function```
circuit_iter{T<:Integer}(v::T, dg::::IsDirected, vis::JohnsonVisitor{T},
vmap::Vector{T}, cycle::Channel, startnode::T = v)
```

Execute one step of the recursive version of simple cycle detection, using a DFS algorithm. Return `true`

if a circuit has been found in the current exploration.

**Arguments**

- v: the vertex considered in this iteration of the DFS
- dg: the digraph from which cycles are computed
- visitor: information needed for the cycle computation, contains:
- stack: the stack of parent vertices
- blocked: tells whether a vertex has already been explored or not
- blockedmap: mapping of the blocking / unblocking consequences

`vmap`

: vector map containing the link from the old to the new nodes of the directed graph`cycle`

: storage of the channel- startnode = v: optional argument giving the starting node. In the first iteration,

the same as v, otherwise it should be passed.

**Implementation Notes**

Implements the CIRCUIT function from Johnson's algorithm, recursive and iterative version. Produces a cycle when needed. Can be used only inside a `Channel`

.

**References**

`Graphs.itercycles`

— Function`itercycles(dg::::IsDirected, cycle::Channel)`

Compute all cycles of the given directed graph, using Johnson's algorithm.

**Implementation Notes**

Iterative version of the algorithm, using `Channel`

s to stop the exploration after a given number of cycles.

**References**

`Graphs.maxsimplecycles`

— Function`maxsimplecycles(dg::::IsDirected, byscc::Bool = true)`

Compute the theoretical maximum number of cycles in the directed graph `dg`

.

The computation can be performed assuming the graph is complete or taking into account the decomposition in strongly connected components (`byscc`

parameter).

**Performance**

A more efficient version is possible.

**References**

`Graphs.maxsimplecycles`

— Method`maxsimplecycles(n::Integer)`

Compute the theoretical maximum number of cycles in a directed graph of `n`

vertices, assuming there are no self-loops.

**References**

`Graphs.ncycles_n_i`

— Method`ncycles_n_i(n::Integer, i::Integer)`

Compute the theoretical maximum number of cycles of size `i`

in a directed graph of `n`

vertices.

`Graphs.simplecycles`

— Function`simplecycles(dg::::IsDirected)`

Compute and return all cycles of the given directed graph using Johnson's algorithm.

**Performance**

The number of cycles grows more than exponentially with the number of vertices, you might want to use the algorithm with a ceiling – `simplecycles_iter`

– on large directed graphs (slightly slower). If you want to have an idea of the possible number of cycles, look at function `maxsimplecycles(dg::DiGraph, byscc::Bool = true)`

. If you only need short cycles of a limited length, `simplecycles_limited_length`

can be more efficient.

**References**

**Examples**

```
julia> simplecycles(complete_digraph(3))
5-element Array{Array{Int64,1},1}:
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2, 3]
```

`Graphs.simplecycles_iter`

— Function`simplecycles_iter(dg::DiGraph, ceiling = 10^6)`

Search all cycles of the given directed graph, using Johnson's algorithm, up to the ceiling (to avoid memory overload).

**Implementation Notes**

If the graph is small, the ceiling will not be reached and `simplecycles(dg::DiGraph)`

is more efficient. It avoids the overhead of the counting and testing if the ceiling is reached. It returns all the cycles of the directed graph if the `ceiling`

is not reached, a subset of them otherwise.

To get an idea of the possible number of cycles, use function `maxsimplecycles(dg::DiGraph, byscc::Bool = true) on the directed graph.

**References**

`Graphs.simplecyclescount`

— Function`simplecyclescount(dg::DiGraph, ceiling = 10^6)`

Count the number of cycles in a directed graph, using Johnson's algorithm. Return the minimum of the ceiling and the number of cycles.

**Implementation Notes**

The `ceiling`

is here to avoid memory overload if there are a lot of cycles in the graph. Default value is 10^6, but it can be higher or lower. You can use the function `maxsimplecycles(dg::DiGraph, byscc::Bool = true)`

to get an idea of the theoretical maximum number or cycles.

**References**

**Examples**

```
julia> simplecyclescount(complete_digraph(6))
409
```

`Graphs.simplecycleslength`

— Function`simplecycleslength(dg::DiGraph, ceiling = 10^6)`

Search all cycles of the given directed graph, using Johnson's algorithm, and return a tuple representing the cycle length and the number of cycles.

**Implementation Notes**

To get an idea of the possible number of cycles, using function `maxsimplecycles(dg::DiGraph, byscc::Bool = true)`

on the directed graph.

If the `ceiling`

is reached (`ncycles = ceiling`

), the output is only a subset of the cycles lengths.

**References**

**Examples**

```
julia> simplecycleslength(complete_digraph(16))
([0, 1, 1, 1, 1, 1, 2, 10, 73, 511, 3066, 15329, 61313, 183939, 367876, 367876], 1000000)
julia> simplecycleslength(wheel_digraph(16))
([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 1)
```

`Graphs.unblock!`

— Method`unblock!{T<:Integer}(v::T, blocked::BitVector, B::Vector{Set{T}})`

Unblock the vertices recursively.

`v`

is the vertex to unblock, `blocked`

tells whether a vertex is blocked or not and `B`

is the map that tells if the unblocking of one vertex should unblock other vertices.

`Graphs.karp_minimum_cycle_mean`

— Function`karp_minimum_cycle_mean(g[, distmx])`

Return minimum cycle mean of the directed graph `g`

with optional edge weights contained in `distmx`

.

**References**

- Karp.

`Graphs.simplecycles_limited_length`

— Method`simplecycles_limited_length(g, n, ceiling=10^6)`

Compute and return at most `ceiling`

cycles of length at most `n`

of the given graph. Both directed and undirected graphs are supported.

**Performance**

The number of cycles grows very fast with the number of vertices and the allowed length of the cycles. This function is intended for finding short cycles. If you want to find cycles of any length in a directed graph, `simplecycles`

or `simplecycles_iter`

may be more efficient.