Depth-first searcher: a simple graph type and an implementation of depth first search (DFS) in Julia

graphSearcher.jl

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