Discussion : API for Graphs.jl 2.0

This is for discussing the future API of Graphs.jl

Here is a first shot to open the discussions:
In the light of Why I no longer recommend Julia, I tried to make the API as complete as possible, and to detail all the assumptions that go with it.
I took a lot of inspiration from boost graph, and try to make it the less breaking possible, there may be many breaking changes in my proposition that can be avoided simply.
I also left many question marks and void in it.

Vertices

Vertex (Trait)

required :

• isless(v1::Vertex , v2::Vertex)::Bool
  assumptions:
  • isless forms a total order
• hash(v::Vertex)::UInt

IntegerVertex < : Vertex

IntegerVertex will be associated with containers indexed by a UnitRange
required :

• getindex(V::IntegerVertex)::Uint (or vindex?)

Edges

AbstractEdge{T<:Vertex} (Trait ? See #132)

required :

• src(e::AbstractEdge)::T
• dst(e::AbstractEdge)::T
  assumptions:
  • no guarantee that src(e) <= dst(e) ?
• isless(e1::AbstractEdge, e2::AbstractEdge)::Bool
  assumptions:
  • isless forms a total order
• hash(e::AbstractEdge)::UInt

WeightedEdge{T} < : AbstractEdge{T}

• weight(e::WeightedEdge)::Float

DataEdge

todo

Graphs

AbstractGraph{V<:Vertex, E<:AbstractEdge}:

required:

• vertices(g::AbstractGraph)::{Iterator over Vertex}
• get_edges(g::AbstractGraph, u::Vertex, v::Vertex)::{Iterator over AbstractEdge}
• edges(g::AbstractGraph)::{Iterator over AbstractEdge} must be coherent with get_edges
• outedges(g::AbstractGraph, v::Vertex)::{Iterator over AbstractEdge}
  assumptions for each iterator output:
  • no repetition (of vertices or edges)
  • no need to be sorted
• get_weight(g::AbstractGraph, v::Vertex) default to 1 ? Or only for WeightedGraphs ?
• get_weight(g::AbstractGraph, e::AbstractEdge) default to 1 if edge is resent else 0 ? or only for WeightedGraphs ?

not required:

• nv(g) = length(vertices(g))

• ne(g) = length(edges(g))

• outneighbors(g::AbstractGraph, v::Vertex) = union([src(e) == v ? dst(e) : src(e) for e in outedges(g, v)])

• edges(g, v) = outedges(g, v)

• outdegree(g, v) = length(outneighbors(g, v))

• outdegree(g, u) = length(outedges(g, u))

• has_edge(g, e)::Bool

• has_vertex(g, v)::Bool

• has_self_loops(g::AbstractGraph) = any(src(e) == dst(e) for e in edges(g))

• get_vertex_container(g::AbstractGraph{V, E}, K::Type)::{Vertex container over type} = Dict{V, K}()
  The container is indexed by vertices of g

• get_edge_container(g::AbstractGraph{V, E}, K::Type)::{Vertex container} = Dict{E, K}()
  The container is indexed by edges of g

BidirectionalGraph <: Graph

required:

• inneighbors, inedges
  assumptions:
• no repetition of vertices
• no need to be sorted

not required:

• all_neighbors = union(inneigbors, outneighbors)
• neighbors = all_neighbors
• indegree = length(inneighbors)
• degree = length(all_neighbors)

IsSimple <: AbstractGraph

If true, additional requirement that no two edges can have same src and dst
Self-loops allowed because of implementation details and history of Graphs.jl (but at most one self-loop per vertex)

• weights(g:AbstractGraph)::AbstractMatrix ?
  not required:
• get_edge(g, u, v) = get_edges(g, u, v)

IsDirected <: AbstractGraph

(must be implemented ? allow mixed graphs ?)
If false:

• it is assumed that an each edge is an out_edge of both dest and src. edges output edges only for one direction. (so length(edges) = ne(g))
• it must be a subtype of Bidirectional graph ?
• it is assumed inedges = outedges

RangeBasedGraph <: AbstractGraph

it is assumed vertices(g::RangeBasedGraph) = 1:nv(g)

• adjacency_matrix(g::AbstractGraph)::AbstractMatrix ?
  A[i,j] should have positive value (or true value?) only if there is an edge between i and j
• weights(g::AbstractGraph) ?

Mutability

(distinguish vertex and edge mutability ?)

IsSimplyMutable

graph structure able to represent the structure of any unweighted simple graph
required:

• GraphType()::{GraphType<:IsSimplyMutable} returns an empty graph.
• add_vertex!(g::AbstractGraph)::Vertex
  return created vertex
  should generally succede (graph is sufficiently general to handle any number of vertices), can fail only due to overflow. (or allow more general failure, with clean exception thrown ?)
• add_edge!(g::AbstractGraph, e::AbstractEdge)::Bool
  allowed to return false if an edge with same extremities already exist
  If the edge does not already exist, it should generally succede.
• rem_vertex!(g, v)
  should always succede
  adjacent edges are deleted ? (or undefined behavior as in boost, use in cojonction with clear vertex?)
  vertex and edge identifiers can no longer be valid
• rem_edge!(g, e)
  should always succede
  edge identifiers can no longer be valid, but vertices will be

not required:
- add_vertices!(g, l) = add_vertex!(g, e) for e in edges(g)
- add_edges!, rem_vertices!, rem_edges!
- GraphType(g::AbstractGraph)::{GraphType<:IsSimplyMutable} cast a graph g to an instance of GraphType
- zero(GraphType<:IsSimplyMutable) = GraphType() ?
- GraphType(n::Integer)::{GraphType<:IsSimplyMutable} returns a graph with n vertices and no edges.

IsMutable <: IsSimplyMutable

graph structure able to represent the structure of any unweighted multigraph

• add_edge should generally succede

IsWeightMutable

graph structure able to modify all it's weight (but not necessarily able to change its structure)

• set_weight!(g::AbstractGraph, e::WeightedEdge{T, U}, w::U)

IsVertexStable

If mutated, vertex identifiers are guaranteed to still be valid (we can compare vertices gathered before and after a mutation, a vertex container gathered before a mutation will still be valid after)

IsEdgeStable

If mutated, edge identifiers are guaranteed to still be valid (we can compare edges gathered before and after a mutation, an edge container gathered before a mutation will still be valid after)