GraphTraits.jl

module GraphTraits

abstract type GraphStyle end

GraphStyle(x) = GraphStyle(typeof(x))
GraphStyle(::Type{T}) where {T} = throw(MethodError(GraphStyle, T))

vertex_type(x) = vertex_type(typeof(x))
vertex_type(::Type{T}) where {T} = throw(MethodError(vertex_type, T))

edge_type(x) = edge_type(typeof(x))
edge_type(::Type{T}) where {T} = throw(MethodError(edge_type, T))

"""
    nvertices(g) -> Int

Return the number of vertices in `g`.
"""
nvertices(g) = nvertices(GraphStyle(g), g)
nvertices(s::GraphStyle, g) = throw(MethodError(nvertices, (s, g)))

"""
    nedges(g) -> Int

Return the number of edges in `g`.
"""
nedges(g) = nedges(GraphStyle(g), g)
nedges(s::GraphStyle, g) = throw(MethodError(nedges, (s, g)))

"""
    inneighbors(g, v)

Return a list of all neighbors connected to vertex `v` by an incoming edge.
"""
inneighbors(g, v) = inneighbors(GraphStyle(g), g, v)
inneighbors(s::GraphStyle, g, v) = throw(MethodError(inneighbors, (s, g, v)))

"""
    outneighbors(g, v)

Return a list of all neighbors connected to vertex `v` by an outgoing edge.
"""
outneighbors(g, v) = outneighbors(GraphStyle(g), g, v)
outneighbors(s::GraphStyle, g, v) = throw(MethodError(outneighbors, (s, g, v)))

"""
    neighbors(g, v)

Return a list of all neighbors reachable from vertex `v` in `g`.
For directed graphs, the default is equivalent to [`outneighbors`](@ref);
use [`all_neighbors`](@ref) to list inbound and outbound neighbors.
"""
neighbors(g, v) = neighbors(GraphStyle(g), g, v)
neighbors(s::GraphStyle, g, v) = throw(MethodError(neighbors, (s, g, v)))

"""
    indegree(g, v) -> Int
    indegree(g, v::AbstractVector) -> Vector{Int}

Return a vector corresponding to the number of edges which end at each vertex in graph `g`.
If `v` is specified, only return degrees for vertices in `v`.
"""
indegree(g, v=vertex_indicess(g)) = indegree(GraphStyle(g), g, v)
indegree(s::GraphStyle, g, v) = throw(MethodError(indegree, (s, g, v)))
function indegree(s::GraphStyle, g::AbstractGraph, v::AbstractVector)
    out = Vector{Int}(undef, length(v))
    @inbounds for (i, v_i) in enumerate(v)
        out[i] = indegree(s, g, v_i)
    end
    return out
end

"""
    outdegree(g, v) -> Int
    outdegree(g, v::AbstractVector) -> Vector{Int}

Return a vector corresponding to the number of edges which start at each vertex in
graph `g`. If `v` is specified, only return degrees for vertices in `v`.
"""
outdegree(g, v=vertex_indices(g)) = outdegree(GraphStyle(g), g, v)
outdegree(s::GraphStyle, g, v::Integer) = throw(MethodError(outdegree, (s, g, v)))
function outdegree(s::GraphStyle, g, v::AbstractVector)
    out = Vector{Int}(undef, length(v))
    @inbounds for (i, v_i) in enumerate(v)
        out[i] = outdegree(s, g, v_i)
    end
    return out
end

"""
    degree(g, v) -> Int
    degree(g, v::AbstractVector) -> Vector{Int}

Return a vector corresponding to the number of edges which start or end at each
vertex in graph `g`. If `v` is specified, only return degrees for vertices in `v`.
For directed graphs, this value equals the incoming plus outgoing edges.
For undirected graphs, it equals the connected edges.
"""
degree(g, v = vertex_indices(g)) = degree(GraphStyle(g), g, v)
degree(s::GraphStyle, g, v::Integer) = throw(MethodError(degree, (s, g, v)))
function degree(s::GraphStyle, g, v::AbstractVector)
    out = Vector{Int}(undef, length(v))
    @inbounds for (i, v_i) in enumerate(v)
        out[i] = degree(s, g, v_i)
    end
    return out
end

"""
    vertex_indices(g)

Return the indices to the vertices of graph `g`.
"""
vertex_indices(g) = vertex_indices(GraphStyle(g), g)
vertex_indices(s::GraphStyle, g) = throw(MethodError(vertex_indices, (s, g))

"""
    vertices(g)

Return an iterable of to vertices of graph `g`.
"""
vertices(g) = vertices(GraphStyle(g), g)
vertices(s::GraphStyle, g) = throw(MethodError(vertices, (s, g))

"""
    edges(g)

Return (an iterator to or collection of) the edges of a graph.
For `AbstractSimpleGraph`s it returns a `SimpleEdgeIter`.
The expressions `e in edges(g)` and `e ∈ edges(ga)` evaluate as
calls to [`has_edge`](@ref).
"""
edges(g) = edges(GraphStyle(g), g)
edges(s::GraphStyle, g) = throw(MethodError(edges, (s, g)))


"""
    add_vertex!(g)

Add a new vertex to the graph `g`. Return true if addition was successful.
"""
add_vertex!(g) = add_vertex!(GraphStyle(g), g)
add_vertex!(g::GraphStyle, g) = throw(MethodError(add_vertex!, (s, g)))

"""
    add_vertices!(g, n)

Add `n` new vertices to the graph `g`.
Return the number of vertices that were added successfully.
"""
add_vertices!(g, n::Integer) = sum([add_vertex!(g) for i = 1:n])

"""
    insert_vertex!(g, index)

Insert a new vertex at `index` into the graph `g`.
"""
insert_vertex!(g, i) = insert_vertex!(GraphStyle(g), g, i)
insert_vertex!(g::GraphStyle, g, i) = throw(MethodError(insert_vertex!, (s, g, i)))

"""
    insert_vertex!(g, index, v)

Insert a vertex `v` into the graph `g` at `index`.
"""
insert_vertex!(g, i, v) = insert_vertex!(GraphStyle(g), g, i, v)
insert_vertex!(g::GraphStyle, g, i, v) = throw(MethodError(insert_vertex!, (s, g, i, v)))

"""
    children(g)

Get the immediate children of vertex `g`.
"""
function children(g)
    if has_children(g)
        return g
    else
        return ()
    end
end

has_children(x) = has_children(typeof(x))
has_children(::Typee{T}) where {T} = Base.isiterable(T)

"""
    is_directed(g) = is_directed(GraphStyle(g))
    is_directed(s::GraphStyle)

Return `true` if the graph type `G` is a directed graph; `false` otherwise.
New graph types must implement `is_directed(::Type{<:G})`.
The method can also be called with `is_directed(g::G)`
"""
is_directed(g) = is_directed(GraphStyle(g))
is_directed(s::GraphStyle) = throw(MethodError(is_directed, s))

"""
    has_vertex(g, v)

Return true if `v` is a vertex of `g`.
"""
has_vertex(g, v) = has_vertex(GraphStyle(g), g, v)
has_vertex(s::GraphStyle, g, v) = throw(MethodError(has_vertex, (s, g, v)))

"""
    has_edge(g, s, d)

Return true if the graph `g` has an edge from node `s` to node `d`.
An optional `has_edge(g, e)` can be implemented to check if an edge belongs
to a graph, including any data other than source and destination node.
`e ∈ edges(g)` or `e ∈ edges(g)` evaluate as
calls to `has_edge`, c.f. [`edges`](@ref).
"""
has_edge(g, v) = has_edge(GraphStyle(g), g, v)
has_edge(s::GraphStyle, g, v) = throw(MethodError(has_edge, (s, g, v)))

"""
    all_neighbors(g, v)

Return a list of all inbound and outbound neighbors of `v` in `g`.
For undirected graphs, this is equivalent to both [`outneighbors`](@ref)
and [`inneighbors`](@ref).

### Implementation Notes
Returns a reference to the current graph's internal structures, not a copy. 
Do not modify result. If the graph is modified, the behavior is undefined: 
the array behind this reference may be modified too, but this is not guaranteed. 
"""
all_neighbors(g, v) = all_neighbors(GraphStyle(g), g, v)
all_neighbors(s::GraphStyle, g, v) = throw(MethodError(all_neighbors, (s, g, v)))

end