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
— Functioncycle_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]
Graphs.circuit_recursive!
— Functioncircuit_recursive!(g, v1, v2, blocked, B, stack, cycles)
Find circuits in g
recursively starting from v1.
Graphs.resetB!
— MethodresetB!(B)
Reset B work structure.
Graphs.resetblocked!
— Methodresetblocked!(blocked)
Reset vector of blocked
vertices.
Graphs.simplecycles_hawick_james
— Functionsimplecycles_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!
— Methodunblock!(v, blocked, B)
Unblock the value v
from the blocked
list and remove from B
.
Graphs.DenseGraphICT_BFGT_N
— Typestruct 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
— Typeabstract 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
— Typestruct 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!
— Functionadd_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
Graphs.JohnsonVisitor
— Typetype 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
— Functioncircuit{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 DFSdg
: the digraph from which cycles are computedvisitor
: Informations needed for the cycle computation, contains:stack
: the stack of parent verticesblocked
: tells whether a vertex has already been explored or notblockedmap
: mapping of the blocking / unblocking consequences
allcycles
: output containing the cycles already detectedvmap
: vector map containing the link from the old to the new nodes of the directed graphstartnode = 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
— Functioncircuit_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 graphcycle
: 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
— Functionitercycles(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
— Functionmaxsimplecycles(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
— Methodmaxsimplecycles(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
— Methodncycles_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
— Functionsimplecycles(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> using Graphs
julia> simplecycles(complete_digraph(3))
5-element Vector{Vector{Int64}}:
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2, 3]
Graphs.simplecycles_iter
— Functionsimplecycles_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
— Functionsimplecyclescount(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> using Graphs
julia> simplecyclescount(complete_digraph(6))
409
Graphs.simplecycleslength
— Functionsimplecycleslength(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> 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)
Graphs.unblock!
— Methodunblock!{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
— Functionkarp_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
— Methodsimplecycles_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.