[dataflow]

In all of your earlier examples (and actually, including the current one too), you're treating vertices as first-class objects, but edges as second-class. There's no way to even identify an edge in your formulation -- only vertices.

This is a common oversight in graph structures that ends up being very annoying in many applications. You keep trying to work around it by associating the edge's properties with those of the vertex pairs and hoping that's sufficient for the application, but I'm trying to point out that the abstraction you're implicitly dancing around -- and the one that many practical uses need -- is actually one that treats edges as first-class. In fact, I would go further and say that if anything should be second-class, it ought to be the vertices, since they're already implied by the edges. (That is to say, for many practical applications of graphs, an edge determines its endpoints, but the endpoints don't determine the edge.)

[naasking]

I'm not clear what an abstraction that makes edges first class but vertices second class looks like. An edge connects two vertices, so if two edges connect to the same vertex, what does this look like?

[dataflow]

The most minimal example of it I can think of would be a little ridiculous, but it could look like this:

  interface Edge { }
  interface Graph {
    List<Edge> getRoots();  // Returns some ~minimal set of edges with connectivity to all the others
    List<Edge> getAdjacentEdges(Edge e, boolean tail);
  }

There's no way to directly refer to a vertex here at all (unlike with edges), and yet (since edges have identity) there's enough information to determine the graph structure!

[naasking]

What's an example of an algorithm that could use this sort of interface? All of the algorithms that immediately come to mind are more require more vertex information.