IsDigraphHomomorphism is significantly slower for mutable graphs

[jjonusas]

gap> g := CompleteDigraph(100);;  
gap> g2 := DigraphMutableCopy(g);;
gap> IsDigraphHomomorphism(g, g, (1, 12));; time;
19
gap> IsDigraphHomomorphism(g2, g2, (1, 12));; time;
753

[james-d-mitchell]

Thanks @jjonusas, it seems that the issue here is with OutNeighbours the output of which, maybe because OutNeighbours is an attribute, is copied every time it is called (9900 times in the code above). This can be fixed by making OutNeighbours a function instead of an attribute, must think a bit more about whether or not that’s a good idea.

[james-d-mitchell]

If we do:

gap> for i in [1 .. 9900] do
> OutNeighbours(g);
> od;
gap> time;
2

but if we do:

gap> g := DigraphMutableCopy(g);
<mutable digraph with 100 vertices, 9900 edges>
gap> for i in [1 .. 9900] do
> OutNeighbours(g);
> od;
gap> time;
607

So, the only reason I can I think of not to make OutNeighbours a function, is that at present with OutNeighbours an attribute, the return value is immutable, and so too are each of the sublists it contains. If OutNeighbours becomes a function, then the return value is mutable, and so too are each of its sublists. Any thoughts @wilfwilson?

[james-d-mitchell]

I'm fairly sure that if the return value of OutNeighbours is mutable, and it is changed outside of the relevant Digraphs functions (DigraphAddVertex etc), then the digraph will be corrupted, but obviously what @jjonusas reports is also bad

[wilfwilson]

It’s bad, but imo it’s also not really how mutable digraphs are intended to be used. The point of mutability is to make it cheaper to modify/build digraphs. But once you want to do really any kind of computation, you should make it immutable. That’s my initial gut feeling - but perhaps I’m missing something.

[jjonusas]

The reason I've encountered this is that ChromaticNumber makes a mutable copy of the graph, which would appear to go against the intended use.

[wilfwilson]

Ah! Good to know.

[james-d-mitchell]

So, it looks to me that ChromaticNumber needs some work on this front. I could also "fix" IsDigraphHomomorphism for mutable digraphs, but I wonder if that's a good idea? Any thoughts?

[wilfwilson]

Sorry I didn't see this. I've not had any thoughts about this.

[wilfwilson]

Resolved in v1.4.1.