Handle interaction between mutability and edge weights better

[reiniscirpons]

The way weighted digraphs are currently implemented causes the following rather confusing behavior:

gap> D := Digraph(IsImmutableDigraph, [[2], []]);
<immutable digraph with 2 vertices, 1 edge>
gap> De := EdgeWeightedDigraph(D, [[1], []]);    
<immutable digraph with 2 vertices, 1 edge>
gap> EdgeWeights(De);
[ [ 1 ], [  ] ]
gap> D := Digraph(IsMutableDigraph, [[2], []]);  
<mutable digraph with 2 vertices, 1 edge>
gap> De := EdgeWeightedDigraph(D, [[1], []]);  
<mutable digraph with 2 vertices, 1 edge>
gap> EdgeWeights(De);                          
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `EdgeWeights' on 1 arguments at /home/rc234/Desktop/Source/gap/lib/methsel2.g:250 called from
<function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
 called from read-eval loop at *stdin*:8
type 'quit;' to quit to outer loop

The issue arises because a digraph is made weighted by setting its EdgeWeights attribute in EdgeWeightedDigraph, so that a weighted digraph is one which satisfies the filter IsDigraph and HasEdgeWeights. This is reasonable enough, but a mutable digraph is not attribute storing (see https://docs.gap-system.org/doc/ref/chap13.html#X7A951C33839AF2C1), so the SetEdgeWeights call in EdgeWeightedDigraph is a no-op:

gap> D := Digraph(IsMutableDigraph, [[2], []]);
<mutable digraph with 2 vertices, 1 edge>
gap> SetEdgeWeights(D, [[1], []]);
gap> HasEdgeWeights(D);           
false

Here are some ideas on how we might fix this:

1. Change the filters for EdgeWeightedDigraph to only implement it for immutable digraphs. The error message here wont be particularly useful if someone does try to call the EdgeWeightedDigraph function with a mutable digraph - just a no-method found error which could be confusing if you are not already aware that edge weights dont work for mutable digraphs.
2. Make EdgeWeightedDigraph throw an error explaining that the method only works for immutable graphs if the digraph passed in is mutable. The only downside to this is that the user now needs to explicitly call EdgeWeightedDigraph(DigraphImmutableCopy(D), weights) if D happens to be a mutable digraph, which could be a bit tedious to work with.
3. Make EdgeWeightedDigraph display a warning when passed a mutable digraph, then convert the digraph into an immutable one and return the immutable copy instead. This seems the most reasonable and ergonomic to me, but it does mean we won't have proper support for mutable edge weighted digraphs. Another issue is that, if there is ever a chain of operations on an edge weighted digraph which at some point performs a mutable copy, then the final digraph loses all of its weights. This might not be too bad since its unclear what weights should be assigned to new edges when modifying a digraph, e.g. if we call DigraphAddAllLoops on a weighted graph, what should the weights of the newly added loops be? We should probably add a warning in the docs about this, however.
4. Set IsAttributeStoringRep on D (e.g. SetFilterObj(D, IsAttributeStoringRep);) before the SetEdgeWeights call in EdgeWeightedDigraph. This would solve the immediate issue but would cause many more issues down the line since we now have some mutable digraphs that store attributes and some that don't, and the underlying issue of what weights to assign to newly added edges remains.
5. Implement a proper mutable and edge weighted digraph class which allows the user to mutate both the graph and the edge weights. This would likely be quite time consuming, and involve implementing wrappers around all the operations on digraphs that modify the graph in order to support weights.

We should probably do 1., 2. or 3. and add a warning in the EdgeWeightedDigraph docs for now and maybe consider doing 5. at a later point? Not sure if we want to do 5. to avoid a similar issues as with multi digraphs, but would probably be good to discuss at the meeting tomorrow.

[james-d-mitchell]

Number 4 won’t work I think, it simply isn’t possible to store attributes in a mutable digraph. Good write up otherwise, thanks @reiniscirpons

[reiniscirpons]

Number 4 won’t work I think, it simply isn’t possible to store attributes in a mutable digraph. Good write up otherwise, thanks @reiniscirpons

Oh but it will and it is:

gap> D := Digraph(IsMutableDigraph, [[2], []]);
<mutable digraph with 2 vertices, 1 edge>
gap> SetFilterObj(D, IsAttributeStoringRep);   
gap> SetEdgeWeights(D, [[1], []]);
gap> D;
<mutable digraph with 2 vertices, 1 edge>
gap> HasEdgeWeights(D);
true
gap> EdgeWeights(D);
[ [ 1 ], [  ] ]

Per the docs (https://docs.gap-system.org/doc/ref/chap13.html#X7A951C33839AF2C1):

Mutable objects in IsAttributeStoringRep are allowed, but attribute values are not stored automatically in them.

Note that one can force an attribute value to be stored in a mutable object in IsAttributeStoringRep, by explicitly calling the attribute setter. This feature should be used with care. For example, think of a mutable matrix whose rank or trace gets stored, and the values later become wrong when somebody changes the matrix entries.

So we can't automatically store the attributes in an IsMutable object, but if it is in IsAttributeStoringRep, then it will store attributes that are set using the attr setters (such as SetEdgeWeights used in EdgeWeightedDigraph). This is probably a bad idea anyway though, for the other reasons stated :D

[james-d-mitchell]

Well you learn something new everyday, I don't think we should do this though, as you say.