circuits.jl

import Base: start, next, done

using LightGraphs

## New implementation.
type Circuits
    dg::DiGraph
end

type CircuitsState
    sccs::Vector{Vector{Int}}
    scc::Vector{Int}
    subdg::DiGraph
    vmap::Vector{Int}  
    startnode::Int
    blockedmap::Vector{Set{Int}}
    blocked::Vector{Bool}
    stack::Vector{Int}
    currentnode::Int
    done::Bool
end

"""
```unblock!(v::T, blocked::Vector{Bool}, B::Vector{Set{Int}})```

Unblock the vertices recursively.

# Arguments
* `v`: the vertex to unblock
* `blocked`: tell whether a vertex is blocked or not
* `B`: the map that tells if the unblocking of one vertex should unblock other vertices
"""
function unblock!(v::Int, blocked::Vector{Bool}, B::Vector{Set{Int}})
    blocked[v] = false
    for w in B[v]
        delete!(B[v], w)
        if blocked[w]
            unblock!(w, blocked, B)
        end
    end
end

function start(cr::Circuits) ## Problem if acyclic digraph
    sccs = strongly_connected_components(cr.dg)
    scc = pop!(sccs)
    while !isempty(sccs) && (length(scc) < 2)
        scc = pop!(sccs)
    end
    wdg, vmap = induced_subgraph(cr.dg, scc)
    b = falses(vertices(wdg))
    bmap = [Set{Int}() for i in vertices(wdg)]
    neighbors = fadj(wdg, 1)
    state = CircuitsState(sccs, scc, wdg, vmap, 1, bmap, b, [1], 1, false)    
    state.blocked[1] = true
    return state
end

function done(cr::Circuits, state::CircuitsState)
    return isempty(state.sccs)
end

function next(cr::Circuits, state::CircuitsState)
    cycle = Vector{Int}()
    state.done = false
    push!(state.stack, state.currentnode)
    state.blocked[state.currentnode] = true
    for w in fadj(state.subdg, state.currentnode)
        if w == state.startnode
            state.done = true
            cycle = state.vmap[state.stack]
            unblock!(state.currentnode, state.blocked, state.blockedmap)
            pop!(state.stack)
        elseif !state.blocked[w]
            if !in(state.blockedmap[w], state.currentnode)
                push!(state.blockedmap[w], state.currentnode)
            end
            state.currentnode = w
            #next(cr, state)
        else
            if !in(state.blockedmap[w], state.currentnode)
                push!(state.blockedmap[w], state.currentnode)
            end
            pop!(state.stack)
            #next(cr, state)
        end
    end
    if state.done
        return cycle, state
        elseif (length(state.scc) > 1)
        state.currentnode = pop!(state.scc)
        #next(cr, state)
        elseif  !isempty(sccs)
        state.scc = pop!(state.sccs)
        while length(state.scc) == 1
            state.scc = pop!(state.sccs)
        end
        state.subdg, state.vmap = induced_subgraph(state.dg, scc)
        #next(cr, state)
    end
    return cycle, state
end

type SCCcircuits
    dg::DiGraph
end

type SCCcircuitState
    scc::Vector{Int}
    wdg::DiGraph
    vmap::Vector{Int}
    blocked::Vector{Bool}
    blockedmap::Vector{Set{Int}}
    startvertex::Int
    currentvertex::Int
    stack::Vector{Int}
    done::Bool
end

function done(cr::SCCcircuits, state::SCCcircuitState)
    # return length(state.scc) < 2
    return state.done
end

function start(cr::SCCcircuits)
    sccs = strongly_connected_components(cr.dg)
    scc = pop!(sccs)
    wdg, vmap = induced_subgraph(cr.dg, scc)
    b = falses(vertices(wdg))
    bmap = [Set{Int}() for i in vertices(wdg)]
    b[1] = true
    startvertex = 1
    currentvertex = 1
    stack = Int[]
    state = SCCcircuitState(scc, wdg, vmap, b, bmap, startvertex, currentvertex, stack, false)
    return state
end

function next(cr::SCCcircuits, state::SCCcircuitState)
    # cycle = Vector{Int}()
    state.done = false
    push!(state.stack, state.currentvertex)
    state.blocked[state.currentvertex] = true
    @show state.blocked, state.stack
    for neighbor in fadj(state.wdg, state.currentvertex)
        @show neighbor
        if neighbor == state.startvertex
            cycle = state.vmap[state.stack]
            @show cycle
            state.done = true
            return cycle, state
        elseif !state.blocked[neighbor]
            state.currentvertex = neighbor
            next(cr, state)
        end
    end
    if state.done
        return state.vmap[state.stack], state
        unblock!(state.currentvertex, state.blocked, state.blockedmap)
    else
        for neighbor in fadj(state.wdg, state.currentvertex)
            if !in(state.blockedmap[neighbor], state.currentvertex)
                push!(state.blockedmap[neighbor], state.currentvertex)
            end
        end
    end
    pop!(state.stack)
    @show cycle
    return cycle, state
end

function printncycles(g, n::Int)
    ci = SCCcircuits(g)
    for i in take(ci, n)
        println("Cycle found: $i, $ci")
    end
end


com = CompleteDiGraph(4)
printncycles(com, 2)
printncycles(LightGraphs.CycleDiGraph(10), 2)
g = LightGraphs.CycleDiGraph(10)
add_edge!(g, 1,3)
printncycles(LightGraphs.CycleDiGraph(10), 5)

output.txt

❯ julia5                                                                                                                                                                                            [09:07:47]
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.5.0 (2016-09-19 18:14 UTC)
 _/ |\__'_|_|_|\__'_|  |  
|__/                   |  x86_64-apple-darwin15.5.0

julia> include("./cycles.jl")
(state.blocked,state.stack) = (Bool[true,false,false,false],[1])
neighbor = 2
(state.blocked,state.stack) = (Bool[true,true,false,false],[1,2])
neighbor = 1
cycle = [1,2]
neighbor = 3
(state.blocked,state.stack) = (Bool[true,true,true,false],[1,2,3])
neighbor = 1
cycle = [1,2,3]
neighbor = 4
(state.blocked,state.stack) = (Bool[true,true,true,true],[1,2,3,4])
neighbor = 1
cycle = [1,2,3,4]
Cycle found: [1,2,3,4], SCCcircuits({4, 12} directed graph)
(state.blocked,state.stack) = (Bool[true,false,false,false,false,false,false,false,false,false],[1])
neighbor = 2
(state.blocked,state.stack) = (Bool[true,true,false,false,false,false,false,false,false,false],[1,2])
neighbor = 3
(state.blocked,state.stack) = (Bool[true,true,true,false,false,false,false,false,false,false],[1,2,3])
neighbor = 4
(state.blocked,state.stack) = (Bool[true,true,true,true,false,false,false,false,false,false],[1,2,3,4])
neighbor = 5
(state.blocked,state.stack) = (Bool[true,true,true,true,true,false,false,false,false,false],[1,2,3,4,5])
neighbor = 6
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,false,false,false,false],[1,2,3,4,5,6])
neighbor = 7
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,false,false,false],[1,2,3,4,5,6,7])
neighbor = 8
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,false,false],[1,2,3,4,5,6,7,8])
neighbor = 9
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,true,false],[1,2,3,4,5,6,7,8,9])
neighbor = 10
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,true,true],[1,2,3,4,5,6,7,8,9,10])
neighbor = 1
cycle = [1,2,3,4,5,6,7,8,9,10]
Cycle found: [1,2,3,4,5,6,7,8,9,10], SCCcircuits({10, 10} directed graph)
(state.blocked,state.stack) = (Bool[true,false,false,false,false,false,false,false,false,false],[1])
neighbor = 2
(state.blocked,state.stack) = (Bool[true,true,false,false,false,false,false,false,false,false],[1,2])
neighbor = 3
(state.blocked,state.stack) = (Bool[true,true,true,false,false,false,false,false,false,false],[1,2,3])
neighbor = 4
(state.blocked,state.stack) = (Bool[true,true,true,true,false,false,false,false,false,false],[1,2,3,4])
neighbor = 5
(state.blocked,state.stack) = (Bool[true,true,true,true,true,false,false,false,false,false],[1,2,3,4,5])
neighbor = 6
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,false,false,false,false],[1,2,3,4,5,6])
neighbor = 7
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,false,false,false],[1,2,3,4,5,6,7])
neighbor = 8
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,false,false],[1,2,3,4,5,6,7,8])
neighbor = 9
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,true,false],[1,2,3,4,5,6,7,8,9])
neighbor = 10
(state.blocked,state.stack) = (Bool[true,true,true,true,true,true,true,true,true,true],[1,2,3,4,5,6,7,8,9,10])
neighbor = 1
cycle = [1,2,3,4,5,6,7,8,9,10]
Cycle found: [1,2,3,4,5,6,7,8,9,10], SCCcircuits({10, 10} directed graph)

I am afraid to say something stupid, but should not we have a print of the cycle found at line 16 soon after: [1,2] is a cycle.