Discussion : API for Graphs.jl 2.0

[etiennedeg]

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)

[gdalle]

Hi @etiennedeg, and thanks for this first draft!
Here are my thoughts:

• Why Vertex and not AbstractVertex?
• Why allow for DataEdge and not, say, DataVertex?
• What is the idea behind get_vertex/edge_container?
• I would keep a fallback get_weight for general graphs, and I think it should throw an error on non-existent edges instead of returning zero (because edges with zero weights can exist too)
• I'm not sure I understand the difference between BidirectionalGraph and graphs with the IsDirected trait
• Should adjacency_matrix only be defined for RangeBasedGraph? Or should there be a natural enumeration of vertices for other types of graphs?
• I don't get the nuance between IsSimplyMutable and IsMutable

Also, what should we use to implement traits? SimpleTraits.jl?

[etiennedeg]

* Why `Vertex` and not `AbstractVertex`?

I don't remember, AbstractVertex is probably better.

* Why allow for `DataEdge` and not, say, `DataVertex`?

Of course, I just put some examples, but if DataEdge is part of the API, DataVertex should also be

* What is the idea behind `get_vertex/edge_container`?

For some algorithm, like astar, we need to have a list indexed by vertices (here to store the heuristic distance at each vertex). If the vertices does not form a UnitRange, we can't use a list and we can require a Dict. get_vertex_contrainer should return the best suited container depending on the vertex type and the assumptions on the graph. For example, a grid graph could have vertices reprsented by CartesianCoordinates, and the container could be a matrix.

* I'm not sure I understand the difference between `BidirectionalGraph` and graphs with the `IsDirected` trait

BiDirectional comes from the boost graph library. For some graph implementations it is much more costly to call inneighbors than outneighbors, so it is good to have implementations that avoid inneighbors. Bidirectional guarantee that we call inneighbors (and probably assumes it is a bit efficient). Bidirectional is trivial for undirected graphs, so that why I wondered if we can force undirected graphs to be subtype of Bidirectional

* Should `adjacency_matrix` only be defined for `RangeBasedGraph`? Or should there be a natural enumeration of vertices for other types of graphs?

The point of allowing more general vertex type is to avoid maintaining a range based enumeration of vertices. If a graph is implemented in a way that it can provide a natural enumeration of vertices, then he should probably subtype RangeBasedGraph.

* I don't get the nuance between `IsSimplyMutable` and `IsMutable`

IsSimplyMutable is a type of graph that can represent the structure of any simple graph. For example, SimpleGraph is a simply mutable graph.
IsMutable is a type of graph that can represent the structure of any graph (including multigraphs). SimpleGraph is not a mutable graph because it can't be used to represent a graph with multiple edges.

Also, what should we use to implement traits? SimpleTraits.jl?

This is what is used for the moment, are there better alternatives?

[etiennedeg]

Makes me remember we should also define the API for the vertex / edge containers

[jirka-fink]

Thanks for considering another API. Especially for weighted graphs need them.
Here are my thoughts:

Should functions vertices and edges be required?
There are algorithms like DFS, Dijkstra, A* and various state exploration methods (e.g. alpha-beta pruning) for which relevant parts of a graph are generated on fly. These algorithms can be used on infinite graphs, like various lattices, or huge graphs, like state space of chess.

weight(e::WeightedEdge)::Float
Does it mean that a weight of an edge must be a float? I would prefer to have the option to have graphs with integer weights.

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) ?

Having vertices identified by the range 1:nv(g) simplifies a lot of algorithms. But why providing an adjacency_matrix should necessary? Why weight of an edge cannot be zero? What the function weight should be doing? I would suggest RangeBasedGraph be a trait which only imposes vertices to be 1:nv(g).

I am not sure if
IsDirected <: AbstractGraph
means abstract type and their inheritance or traits.

[etiennedeg]

Thank you for your feedback on the API.

Should functions vertices and edges be required?
There are algorithms like DFS, Dijkstra, A* and various state exploration methods (e.g. alpha-beta pruning) for which relevant parts of a graph are generated on fly. These algorithms can be used on infinite graphs, like various lattices, or huge graphs, like state space of chess.

edges and vertices are allowed to return iterator so this is not much a problem. Another point where we need to be careful is the container, but we can use a dictionary to this effect. But it makes me realize that in this case, its dangerous to collect the output of vertices or edges. So maybe it is worth creating a Trait for infinite graphs.

weight(e::WeightedEdge)::Float
Does it mean that a weight of an edge must be a float? I would prefer to have the option to have graphs with integer weights.

I don't know why I didn't used the current SimpleWeightEdge{T<:Integer, U<:Real}, which would become
SimpleWeightEdge{T<:Vertex, U<:Real}, and weight(e) would return U.

Having vertices identified by the range 1:nv(g) simplifies a lot of algorithms. But why providing an adjacency_matrix should necessary?

The adjacency matrix can be easily built by querying the neighbors for every vertices of the graph, so we can make a default implementation. Graph types that want a customized implementation for better performance can do so, but it having it add API does not add more burden on implementation, it just guarantees that such a function can be called.

Why weight of an edge cannot be zero? What the function weight should be doing?

I don't see where I said this. Currently, SimpleWeightedGraph does not support zero weights, but this is due to the implementation, and that could eventually be lifted by this PR. In the API, I was wondering if get_edge must be implemented only for weighted graphs, or if we could define default weights for generic graphs (In which case we probably not need an abstract type or trait for weighted graphs)
In the API I gave, weight(e) is only defined for AbstractWeightedEdge (but if we go the way of defauting weight for generic graphs, we must define it for AbstractEdge too. There is also weights(g) that return the weight matrix, get_weight(g, v) and get_weight(g, v). weight and weights are already part of the API, but we can still find a better name instead of get_weight if needed. For weights, there is still the question of which type must implement it (This is why I put question marks). As for the adjacency matrix, we probably need a RangeBasedGraph, but I think we also need the graph to be simple. Maybe we should not have this function in the API.

I am not sure if
IsDirected <: AbstractGraph
means abstract type and their inheritance or traits.

Here, IsDirected is a trait (as it already is), but you are right that I didn't precised what is a type and what is a trait. I think only AbstractGraph and BidirectionalGraph should be types.

[jlapeyre]

Also, what should we use to implement traits? SimpleTraits.jl?

SimpleTraits can seriously degrade the usefulness of stack traces, and @which. Maybe there is a way around this that I don't know about. I don't have another solution to offer except to use by-hand, non-macro traits.