Iterator for self-avoiding walks

[bramtayl]

I happened to need an iterator of all self-avoiding walks from a start to a destination. I didn't see something like this mentioned in the docs, although there was a random self-avoiding walks generator. Maybe I missed something or this is in another package. Anyway, I wrote up some code for it, and it's below in case that's something people are interested in.

struct PathIterator{Graph}
    graph::Graph
    origin::Int
    destination::Int
end

function eltype(::Type{<: PathIterator})
    Vector{Int}
end

function IteratorSize(::Type{<: PathIterator})
    SizeUnknown()
end

struct PathState
    path::Vector{Int}
    visited::Set{Int}
    decisions::Vector{Tuple{Vector{Int}, Int}}
end

function PathState(;
    path = Int[],
    visited = Set{Int}(),
    decisions = Tuple{Vector{Int}, Int}[]
)
    PathState(path, visited, decisions)
end

function add_path_vertex!(path_state, vertex)
    push!(path_state.path, vertex)
    push!(path_state.visited, vertex)
end

function choose!(path_state, choices, chosen)
    push!(path_state.decisions, (choices, chosen))
    vertex = choices[chosen]
    add_path_vertex!(path_state, vertex)
    vertex
end

function find_choices(path_iterator, path_state, cursor)
    setdiff(outneighbors(path_iterator.graph, cursor), path_state.visited)
end

function forwards!(path_iterator, path_state, cursor)
    path = path_state.path
    destination = path_iterator.destination
    while cursor !== nothing
        if cursor === destination
            return copy(path), path_state
        end
        choices = find_choices(path_iterator, path_state, cursor)
        while !(isempty(choices))
            cursor = choose!(path_state, choices, 1)
            if cursor === destination
                return copy(path), path_state
            end
            choices = find_choices(path_iterator, path_state, cursor)
        end
        cursor = backwards!(path_iterator, path_state)
    end
    return nothing
end

function backwards_one!(path_state)
    old_vertex = pop!(path_state.path)
    delete!(path_state.visited, old_vertex)
    pop!(path_state.decisions)
end

function backwards!(path_iterator, path_state)
    decisions = path_state.decisions

    if isempty(decisions)
        return nothing
    end
    (choices, old_chosen) = backwards_one!(path_state)

    while old_chosen == length(choices)
        if isempty(decisions)
            return nothing
        end
        (choices, old_chosen) = backwards_one!(path_state)
    end
    cursor = choose!(path_state, choices, old_chosen + 1)
end

function iterate(path_iterator::PathIterator)
    path_state = PathState()
    origin = path_iterator.origin
    add_path_vertex!(path_state, origin)
    forwards!(path_iterator, path_state, origin)
end

function iterate(path_iterator::PathIterator, path_state::PathState)
    cursor = backwards!(path_iterator, path_state)
    forwards!(path_iterator, path_state, cursor)
end

[gdalle]

Hey @bramtayl, thanks for the contribution! Did you check out #106 too? Is there a way to make both approaches compatible?