"""
    Path
A path is a sequence of node traversals that exist in a graph.
A path in a graph usually have flows.
"""
mutable struct Path
    nodelist::Vector
    keylist::Vector
end

Path() = Path([], [])

nodelist(p::Path) = p.nodelist
keylist(p::Path) = p.keylist

isempty(p::Path) = isempty(p.nodelist) && isempty(p.keylist)
==(p1::Path,p2::Path) = p1.nodelist == p2.nodelist && p1.keylist == p2.keylist

# deconstruct a path
"""
    ArcIter(p)
breaks down the arcs in a path.
"""
function ArcIter(p::Path)
    len = length(p.keylist)
    ulist = []; sizehint!(ulist, len)
    vlist = []; sizehint!(vlist, len)
    keylist = []; sizehint!(keylist, len)
    for i in eachindex(p.keylist)
        u = p.nodelist[i]; push!(ulist, u)
        v = p.nodelist[i + 1]; push!(vlist, v)
        key = p.keylist[i]; push!(keylist, key)
    end
    return ArcIter(len, ulist, vlist, keylist)
end

arcs(p::Path) = ArcIter(p)

"""
    Graph(p, flow, attrib)
creates a graph from the path with a fixed flow from beginning to end.
"""
function Graph(p::Path, flow=1, attrib=:flow)
    G = Graph()
    add_arcs_from!(G, collect(arcs(p)))
    for a in arcs(G)
        G[a, attrib] = flow
    end
    return Graph(G.nn, G.na, G.fadj, G.badj)
end

"""
    depth_first_search(g, u, v)
finds the shortest path (complete with keys) by first traversing and then assigning key.
"""
function depth_first_search(g::Graph, u, v, p=Path(), shortest=Path(), method=rand)
    P = Path(deepcopy(p.nodelist), deepcopy(p.keylist))
    push!(P.nodelist, u)
    if length(P.nodelist) > 1
        key = keys(g.fadj[last(p.nodelist)][u])
        push!(P.keylist, method(key))
    end
    # println("current path: $(P)")
    if u == v
        return P
    end
    for n in out_neighbor(g, u)
        if !(n in P.nodelist)
            if shortest.nodelist == [] || length(P.nodelist) < length(shortest.nodelist)
                new_p = depth_first_search(g, n, v, P, shortest)
                if new_p.nodelist != []
                    shortest = new_p
                end
            end
        end
    end
    return shortest
end

"""
    dijkstra_shortest_path(g, u, v)
finds the shortest path from u to v in g using the dijkstra algorithm.
"""
function dijkstra_shortest_path(g::Graph, u, v=nothing, w=:flow)
    pred = dictionary(k => [] for k in keys(g.fadj))
    dist = dictionary(k => Inf for k in keys(g.fadj)); H = PriorityQueue()
    dist[u] = 0; H[u] = 0
    while !isempty(H)
        u = dequeue!(H)
        d = dist[u]
        for v in out_neighbor(g, u)
            val, ind = findmin(map(p -> getindex(p, w), g.fadj[u][v]))
            alt = d + val
            if alt < dist[v]
                push!(pred[v], (node = u, key = ind))
                dist[v] = alt
                H[v] = alt
            end
        end
    end

    if isnothing(v)
        return dist, pred
    else
        S = Path()
        complete = false
        while !isempty(pred[v])
            push!(S.nodelist, v)
            push!(S.keylist, last(pred[v]).key)
            v = last(pred[v]).node
        end
        if !isempty(S)
            push!(S.nodelist, v)
            reverse!(S.nodelist)
            reverse!(S.keylist)
        end
        return S
    end
end