Stream: graph theory
Kyle Miller (Feb 21 2022 at 23:22):
#12195 moves darts from
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 (Feb 21 2022 at 23:36):
I myself wanted this change. Extending
prod is nifty :smile:
Kyle Miller (Feb 21 2022 at 23:41):
Indeed, I got the prod idea from having reviewed
Kyle Miller (Feb 28 2022 at 19:50):
Mauricio Collares (Feb 28 2022 at 20:39):
arc is another term for a directed edge, perhaps more common in graph theory (https://en.m.wikipedia.org/wiki/Directed_graph)
Mauricio Collares (Feb 28 2022 at 20:40):
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 (Feb 28 2022 at 21:18):
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 (Feb 28 2022 at 21:26):
That's fair, thanks for the explanation!
Vincent Beffara (Feb 28 2022 at 22:24):
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 (Feb 28 2022 at 22:35):
How about hypermaps / constellations / rotation systems next?
Kyle Miller (Apr 10 2022 at 18:59):
@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!)
Last updated: Aug 03 2023 at 10:10 UTC