Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Depth-first searcher: a simple graph type and an implementation of depth first search (DFS) in Julia
import Base: ==, show
#####################
# root
#####################
abstract AbstractGraph
#####################
# node
#####################
immutable Node{T}
key::T
end
key(v::Node) = v.key
==(v1::Node, v2::Node) = (v1.key == v2.key)
function show(io::IO, v::Node)
print(io, "Node $(v.key)")
end
######################
# edge
######################
immutable Edge
src::Node
dest::Node
end
Edge(src::Char, dest::Char) = Edge(Node(src), Node(dest))
source(e::Edge) = e.src
destination(e::Edge) = e.dest
==(e1::Edge, e2::Edge) = (e1.src == e2.src && e1.dest == e2.dest)
rev(e::Edge) = Edge(e.dest, e.src)
function show(io::IO, e::Edge)
print(io, "Edge $(e.src) -> $(e.dest)")
end
#########################
# graph
#########################
type AdjacencyList <: AbstractGraph
is_directed::Bool
nodes::Vector{Node}
adjlist::Dict{Node,Vector{Node}}
function AdjacencyList(;is_directed::Bool = true,
nodes::Vector{Node} = Node[],
adjlist = Dict{Node, Vector{Node}}() )
new(is_directed, nodes, adjlist)
end
end
is_directed(g::AdjacencyList) = g.is_directed
num_nodes(g::AdjacencyList) = length(g.nodes)
vertices(g::AdjacencyList) = g.nodes
num_edges(g::AdjacencyList) = g.nedges
function show(io::IO, a::AdjacencyList)
print(io, "AdjacencyList: \n")
for k in keys(a.adjlist)
for d in a.adjlist[k]
print(io, "Edge $(k) -> $(d) \n")
end
end
end
function add_node!(g::AdjacencyList, v::Node)
if v in g.nodes
error("Duplicate node")
else
push!(g.nodes, v)
g.adjlist[v] = Node[]
end
return v
end
function add_edge!(g::AdjacencyList, e::Edge)
src = e.src
dest = e.dest
if !(src in g.nodes && dest in g.nodes)
error("Node not in graph")
end
push!(g.adjlist[src], dest)
if !g.is_directed
push!(g.adjlist[dest], src)
end
end
out_neighbors(g::AdjacencyList, v::Node) = g.adjlist[v]
has_node(g::AdjacencyList, v::Node) = (v in g.nodes)
############################
# Build tree
############################
function build_tree(;is_directed = true)
g = AdjacencyList(is_directed = is_directed)
for element in ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
add_node!(g, Node(element))
end
add_edge!(g, Edge('a', 'b'))
add_edge!(g, Edge('b', 'd'))
add_edge!(g, Edge('b', 'e'))
add_edge!(g, Edge('b', 'f'))
add_edge!(g, Edge('a', 'c'))
add_edge!(g, Edge('c', 'g'))
add_edge!(g, Edge('g', 'h'))
return g
end
#################################
# Depth-first-search
#################################
function print_path(path)
print("path: ")
for i in 1 : length(path)-1
print(path[i], " -> ")
end
print(path[end])
print("\n")
end
function DFS_visit(g::AdjacencyList, start_node::Node, end_node::Node,
path = Node[], finder = None)
if start_node == end_node
return start_node
end
path = cat(1, path, [start_node])
print_path(path)
for node in out_neighbors(g, start_node)
if !(node in path) # avoid cycles
if finder == None || finder != end_node
new_node = DFS_visit(g, node, end_node, path, finder)
if new_node != None
finder = new_node
end
end
end
end
return finder
end
function DFS(g::AdjacencyList, v::Node)
start_node = Node('a')
path = Node[]
return DFS_visit(g, start_node, v, path)
end
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.