Cycles

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> using Graphs

julia> elist = [(1,2),(2,3),(2,4),(3,4),(4,1),(1,5)];

julia> g = SimpleGraph(Graphs.SimpleEdge.(elist));

julia> cycle_basis(g)
2-element Vector{Vector{Int64}}:
 [2, 4, 1]
 [2, 3, 4]

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]

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

Find circuits in g recursively starting from v1.

resetB!(B)

Reset B work structure.

resetblocked!(blocked)

Reset vector of blocked vertices.

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

unblock!(v, blocked, B)

Unblock the value v from the blocked list and remove from B.

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

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.

struct TransactionalVector

A vector with one checkpoint that may be reverted to by calling revert!. The setpoint itself is set by calling commit!.

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> using Graphs

julia> G = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph

julia> ict = IncrementalCycleTracker(G)
BFGT_N cycle tracker on SimpleDiGraph{Int64}(0, [Int64[], Int64[], Int64[]], [Int64[], Int64[], Int64[]])

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

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.

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

• Johnson

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

• Johnson

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 Channels to stop the exploration after a given number of cycles.

References

• Johnson

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

• Johnson

maxsimplecycles(n::Integer)

Compute the theoretical maximum number of cycles in a directed graph of n vertices, assuming there are no self-loops.

References

• Johnson.

ncycles_n_i(n::Integer, i::Integer)

Compute the theoretical maximum number of cycles of size i in a directed graph of n vertices.

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

• Johnson

Examples

julia> using Graphs

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

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

• Johnson

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

• Johnson

Examples

julia> using Graphs

julia> simplecyclescount(complete_digraph(6))
409

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

• Johnson

Examples

julia> using Graphs

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)

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.

karp_minimum_cycle_mean(g[, distmx])

Return minimum cycle mean of the directed graph g with optional edge weights contained in distmx.

References

• Karp.

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.