Looped graphs Generated with NoLoops flag.

[sjorn3]

Hi there, I seem to be getting loops in graphs when I use the NoLoops newtype.

for example:

someTest :: NoLoops Gr () () -> Bool
someTest (NL g) = ...

yields:

*** Failed! Exception: 'Prelude.head: empty list' (after 7 tests):       
NL {looplessGraph = mkGraph [(-3,()),(1,())] [(-3,1,()),(1,-3,()),(1,-3,())]}

I don't have a cycle finder to hand so I can't test it properly, but this particular graph does seem to contain a cycle to me.

[ivan-m]

That graph has cycles, but not loops.

If you have a need for cycle-less graphs then I could look at adding such a wrapper to fgl-arbitrary but there isn't one at this stage (my thinking is that it would create a DAG by default, and then the Undirected wrapper would convert it to a tree).

[sjorn3]

Ah, my mistake then apologies.

Certainly, such a wrapper would be very helpful to me if it were to make its way in.

Thanks :)

[ivan-m]

I've been thinking about how to do this; the biggest problem I can think of is that there seems to be no logical way for a DAG wrapper and Undirected to play nicely together to be able to generate undirected cycle-free graphs (unless we do really boring DAGs that are just trees as well).

If we layer Undirected on top of DAG, then as soon as we have A -> {B, C} -> D, the undirected version will have the cycle A - B - D - C - A.

I think this is more a limitation of the ArbGraph class; either it can't work for this type (and it needs its own Arbitrary instances) or else more layering functions are needed.