Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
graph scratching
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]
@aviatesk

This comment has been minimized.

Copy link
Owner Author

aviatesk commented Jul 5, 2020

Screen Shot 2020-07-05 at 16 39 12

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.