[RFC] GraphInterface.jl: An interface proposal for Graphs.jl version 2.0

Specific Domains Graphs
,
14

Requiring a method from the user or requiring a trait doesn’t change much in the grand scheme of things.
But what changes a lot is what we index stuff with in the algorithms themselves:

  1. the vertex object
  2. an explicit vertex index
  3. an implicit vertex index given by the memory layout of vertices(g) or neighbors(g, u)

Another issue with 3 is consistency: the index of v in vertices(g) is not the same as its index in neighbors(g, u). I shudder to think of the headaches this would cause.

More generally, I’m also worried that we might make the interface way too complicated, especially by adding lots of traits (which also mess with the readability of stack traces).
If we disregard efficiency considerations, I think something like this could actually be the minimum required set of methods (names are provisional).
Nearly everything else can be defined based on those:

  • vertices(g)
  • edges(g)
  • edges(g, v): edges linked to a vertex v
  • neighbors(g, e, v): vertices reachable from v through the edge e
  • data(g, v) and data(g, e)

The more requirements we add, the harder we make it to understand the code or extend it.
That’s also why I like option 2 for vertex to integer translation: pay a cost once at the beginning of an algorithm and at the end, but in the middle it’s business as usual.

1 Like