Seg fault for `DigraphReflexiveTransitiveReduction` of large graph

[james-d-mitchell]

I get the following:

gap> D := DigraphMutableCopy(D);
<mutable multidigraph with 335497 vertices, 364349742 edges>
gap> DigraphRemoveAllMultipleEdges(D);
<mutable digraph with 335497 vertices, 36895220 edges>
gap> DigraphReflexiveTransitiveReduction(D);
Stack trace (most recent call last):
#31   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d6521, in
#30   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d539f, in
#29   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d51b9, in
#28   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d604a, in
#27   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x463aa4, in IntrFuncCallEnd
#26   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x45656d, in
#25   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e530c, in EXEC_CURR_FUNC
#24   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e2e57, in
#23   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4545a1, in
#22   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x45a1dd, in
#21   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d7b2d, in ReadEvalCommand
#20   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d1e69, in
#19   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d1cb9, in
#18   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d19d8, in
#17   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d180b, in
#16   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d169a, in
#15   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d13f1, in
#14   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d117f, in
#13   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4d5c91, in
#12   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4cf492, in
#11   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x463ae8, in IntrFuncCallEnd
#10   Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4a1b1f, in DoOperation1Args
#9    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x45676e, in
#8    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e530c, in EXEC_CURR_FUNC
#7    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e2eb7, in
#6    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4533ef, in
#5    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4a1b1f, in DoOperation1Args
#4    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x45676e, in
#3    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e530c, in EXEC_CURR_FUNC
#2    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4e2d97, in
#1    Object "/homer1/jdm3/gap-4.13.0/gap", at 0x4533ef, in
#0    Object "/homer1/jdm3/gap-4.13.0/pkg/Digraphs//bin/x86_64-pc-linux-gnu-default64-kv9/digraphs.so", at 0x7f8d32d99381, in
Segmentation fault (Address not mapped to object [0x1])
Segmentation fault (core dumped)

will investigate further when I am able.

[ChrisJefferson]

Do you have a full program (not sure how to make D?) If so, I could try running it through GAP with valgrind, and see if it more accurately points out the problem.

[james-d-mitchell]

Thanks @ChrisJefferson ! Sorry I didn't reply earlier, somehow overlooked this.

Here's some more info, I can reproduce this using the following:

gap> D := ChainDigraph(3 * 10 ^ 6);
gap> DigraphReflexiveTransitiveReduction(D);
[1]    62771 killed     /Users/jdm/gap/gap -m 1g

It seems that what causes this is the line:

https://github.com/digraphs/Digraphs/blob/b28e374151e3bedbf7d29d1be6391445eef4c1a4/src/digraphs.c#L1148

or possibly:

https://github.com/digraphs/Digraphs/blob/b28e374151e3bedbf7d29d1be6391445eef4c1a4/src/digraphs.c#L1171

When n is large enough this is clearly a terrible idea. I think there are a number of things that could/should be done to fix this issue:

1. Add a check that n isn't too big into the C code, and if it is, then given an error (not completely sure what "too big" means here, or how to estimate it);

2. IsTransitiveDigraph has a backtrack version that is used when the digraph is "sparse" (the definition is in the code):

   https://github.com/digraphs/Digraphs/blob/b28e374151e3bedbf7d29d1be6391445eef4c1a4/gap/prop.gi#L392

   where n is the number of vertices and m the number of edges in the input digraph. We should implement a version of DigraphTransitiveReduction that uses the same technique (backtrack search) if the input digraph is sparse, or has too many vertices for the existing method (see 1);

3. We should implement IsTransitivelyReducedDigraph too, this is only tangentially related to this issue, so I'll open a new issue for it. But if IsTransitivelyReducedDigraph is implemented, the we could also start a DigraphTransitiveReduction by checking if it is already transitively reduced, and if so, then doing nothing.