graph scratching

scratched_graph.jl

using LightGraphs, SparseArrays, GraphPlot


get_adj(g, v) = first(findnz(adjacency_matrix(g)[v, :]))

function dfs(g::AbstractGraph{T}, s::T,
             visited = Set{T}(),
             ret = T[]) where T
    push!.((visited, ret), s)

    for v in get_adj(g, s)
        v in visited || dfs(g, v, visited, ret)
    end

    return ret
end

function bfs_iterative(g::AbstractGraph{T}, s::T) where T
    fringe = T[s]
    visited = Set{T}(s)
    ret = T[s]

    while !isempty(fringe)
        v = popfirst!(fringe)
        for nv in filter(!in(visited), get_adj(g, v))
            push!.((fringe, visited, ret), nv)
        end
    end

    return ret
end

function bfs_recursive(g::AbstractGraph{T}, s::T) where T
    fringe = T[s]
    visited = Set{T}(s)
    ret = T[s]

    _bfs_recursive(g, fringe, visited, ret)
    return ret
end

function _bfs_recursive(g, fringe, visited, ret)
    isempty(fringe) && return

    v = popfirst!(fringe)
    for nv in filter(!in(visited), get_adj(g, v))
        push!.((fringe, visited, ret), nv)
    end

    _bfs_recursive(g, fringe, visited, ret)
end

function make_graph()
    g = SimpleDiGraph(8)
    add_edge!(g, 1, 4)
    add_edge!(g, 2, 1)
    add_edge!(g, 3, 4)
    add_edge!(g, 3, 6)
    add_edge!(g, 4, 5)
    add_edge!(g, 5, 2)
    add_edge!(g, 5, 8)
    add_edge!(g, 6, 4)
    add_edge!(g, 6, 7)
    return g
end

let g = make_graph()
    @show dfs(g, 3)
    @show bfs_iterative(g, 3)
    @show bfs_recursive(g, 3)
    gplot(g; nodelabel = 1:nv(g))
end

# dfs(g, 3) = [3, 4, 5, 2, 1, 8, 6, 7]
# bfs_iterative(g, 3) = [3, 4, 6, 5, 7, 2, 8, 1]
# bfs_recursive(g, 3) = [3, 4, 6, 5, 7, 2, 8, 1]