Withdraw multidigraphs and implement edge-coloured digraphs instead

[james-d-mitchell]

We already stopped adding new methods for multidigraphs, the main issue is that there is no way to distinguish between the multiple edges. To address this I propose removing support for multidigraphs altogether, and instead implementing edge-coloured digraphs, so that it is not permitted to have more than one edge from a vertex to another vertex with the same colour.

[kiryph]

What is the status of this breaking change (Feb 2024)?

I am interested in multidigraphs with group elements as edge labels (gain graphs) which are currently not supported:

 ┌───────┐   GAP 4.12.2 of 2022-12-18
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin22-default64-kv8
 Configuration:  gmp 6.3.0, GASMAN, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.2.1, AtlasRep 2.1.6, AutPGrp 1.11, Browse 1.8.19, CaratInterface 2.3.6,
             CRISP 1.4.6, crypting 0.10.4, Cryst 4.1.27, CrystCat 1.1.10, CTblLib 1.3.4, curlInterface 2.3.1,
             datastructures 0.3.0, debugger 0.4, Digraphs 1.6.1, FactInt 1.6.3, FGA 1.4.0, float 1.0.3,
             Forms 1.2.9, GAPDoc 1.6.6, genss 1.6.8, GRAPE 4.9.0, IO 4.8.0, IRREDSOL 1.4.4, json 2.1.1,
             LAGUNA 3.9.5, Memoisation 1.0, orb 4.9.0, PackageManager 1.3.2, Polenta 1.3.10, Polycyclic 2.16,
             polymaking 0.8.6, PrimGrp 3.4.3, RadiRoot 2.9, recog 1.4.2, ResClasses 4.7.3, SmallGrp 1.5.1,
             Sophus 1.27, SpinSym 1.5.2, TomLib 1.2.9, TransGrp 3.6.3, typeset 1.1, utils 0.81
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> gr := Digraph(5, [1, 2, 2, 4, 1, 1], [2, 3, 5, 5, 1, 1]);
<immutable multidigraph with 5 vertices, 6 edges>
gap> SetDigraphEdgeLabel(gr, 1, 2, [42]);
Error, the 1st argument <D> must be a digraph with no multiple edges, edge labels are not supported on digraphs with multiple edges, at /usr/local/Cellar/gap/4.12.2/libexec/pkg/digraphs/gap/labels.gi:94 called from
<function "SetDigraphEdgeLabel for a digraph, a pos int, a pos int, and an object">( <arguments> )
 called from read-eval loop at *stdin*:2
type 'quit;' to quit to outer loop

CHANGELOG.md up to version 1.7.1 indicates no change.

Scientific Context

Ross, E., Schulze, B., & Whiteley, W. (2011). Finite motions from periodic frameworks with added symmetry. International Journal of Solids and Structures, 48(11–12), 1711–1729. https://doi.org/10.1016/j.ijsolstr.2011.02.018

uses for the occurring (gain) graphs the term periodic (symmetric) orbit graphs. Edge labels are elements of crystallographic groups (GAP package Cryst) (only a vector is shown for pure translations):

[james-d-mitchell]

We still aim to remove support for multidigraphs and to instead support what I'd call a word graph, i.e. support out-regular digraphs or equivalently deterministic finite state automata with no initial or terminal states instead. This case includes that of Cayley graphs for example.

The issue with the SetDigraphEdgeLabel(gr, 1, 2, [42]); is that in the current set up in Digraphs, it is not possible to distinguish the two edges from 1 to 2 (in your example). Which one of them are you trying to add the label to? It's not clear, and basically this is key reason we want to withdraw support for multidigraphs as currently implemented: it is not possible to distinguish between the multiple edges from one node to another.

With the aim above in mind (replacing multidigraphs by word graphs) we stopped implementing things for multidigraphs for new features whenever it wasn't immediately obvious how to do it (i.e. if an algorithm implementing a feature makes sense for multidigraphs, and requires no additional code to work on a multidigraph, then we will probably have implemented it in such a way that it works for multidigraphs, but otherwise we will not).

Having said all of that, I don't think anyone is actively working to remove multidigraphs just yet, it's just a longer term goal.

I hope this helps!

[kiryph]

@james-d-mitchell Thanks for your detailed answer and insights to the way multidigraphs are implemented in Digraphs. The issue with specifying multi edges is understandable. I checked for comparison quivers and the QPA package: apparently strings are used to denote edges/arrows in QPA (if not chosen, defaults are of the form "a1", "a2", ...).

gap> q2 := Quiver(2,[[1,1],[2,1],[1,2]]);
<quiver with 2 vertices and 3 arrows>
gap> ArrowsOfQuiver(q2);
[ a1, a2, a3 ]
gap> q2.a1;
a1

I noticed the recent addition of EdgeWeightedDigraph where the weights can be scalars (integers, rationals, floats) which I assume does not support Multidigraphs and not matrices or group elements as edge "weights".

For my problem at hand, I will use a custom record and store edges in a list [ [1, 2, g1], [1, 2, g2], ...] where the list index denotes each edge. An alternative could be to use a quiver and add a custom attribute to an arrow to store the group element.

Anyhow, I wanted to raise awareness for the broader use of multidigraphs.