darts

Stream: graph theory

[Kyle Miller]

#12195 moves darts from degree_sum to basic. It's nice to see that they've been finding more uses. (Ping: @Vincent Beffara.)

A breaking change: dart now extends prod so that they're more directly ordered pairs of vertices. I was thinking this made it so that it can interface easier with edges of a simple graph (no need to break apart the underlying pair of an edge to form a dart), but I haven't really tested anything. Thoughts?

[Yaël Dillies]

I myself wanted this change. Extending prod is nifty :smile:
cf docs#two_pointing

[Kyle Miller]

Indeed, I got the prod idea from having reviewed two_pointing

[Kyle Miller]

Following up with this, #12360 adds walk.darts and defines walk.edges in terms of it.

[Mauricio Collares]

Bikeshed: arc is another term for a directed edge, perhaps more common in graph theory (https://en.m.wikipedia.org/wiki/Directed_graph)

[Mauricio Collares]

Unless the point is to explicitly say "this is an orientation of an undirected edge" (say, if you want to recover the underlying undirected edge in case of multigraphs)

[Kyle Miller]

Yes, that's the point -- I think arc should be reserved for graphs with directed edges. The dart terminology comes from combinatorial maps, which are unoriented graphs with an additional "rotation structure" (a cyclic ordering of incident darts at each vertex).

[Mauricio Collares]

That's fair, thanks for the explanation!

[Vincent Beffara]

Cool! Also bikeshed: sometimes "half-edge" is used as well to mean something similar (I saw it in models of random graphs using the configuration model, where one first samples vertices with random degrees and the corresponding half-edges, and then pairs the half-edges into the edges of a graph). But dart sounds better in the general context.

[Vincent Beffara]

How about hypermaps / constellations / rotation systems next?

[Kyle Miller]

@Vincent Beffara Just remembered your suggestion about half-edges, so here's a PR to mention this synonym in the documentation: #13312

One reason I didn't go with half-edges originally is that it wasn't obvious to me which end of the ordered pair was the half-edge. (I think I've used both possibilities before in non-formalized math!)