Zulip Chat Archive

Stream: graph theory

Topic: darts

Kyle Miller (Feb 21 2022 at 23:22):

#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 (Feb 21 2022 at 23:36):

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

Kyle Miller (Feb 21 2022 at 23:41):

Indeed, I got the prod idea from having reviewed two_pointing

Kyle Miller (Feb 28 2022 at 19:50):

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

Mauricio Collares (Feb 28 2022 at 20:39):

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 (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: Dec 20 2023 at 11:08 UTC