Data.Graph.Inductive.Query.TransClos.rc is wrongly implemented

[LambdaP]

In the module Data.Graph.Inductive.Query.TransClos, the function rc has the following description:

Finds the reflexive closure of a directed graph.
Given a graph G=(V,E), its transitive closure is the graph:
G* = (V,Er union E) where Er = {(i,i): i in V}

However, its implementation of the function rc is:

rc :: (DynGraph gr) => gr a b -> gr a ()
rc g = newEdges `insEdges` insNodes ln empty
  where
    ln       = labNodes g
    newEdges = [ (u, u, ()) | (u, _) <- ln ]

This very obviously computes the graph (V, Er), using the previous notation.

Proposed solution: replace the code with:

rc :: (DynGraph gr) => gr a b -> gr a ()
rc g = (newEdges ++ oldEdges) `insEdges` insNodes ln empty
  where
    ln       = labNodes g
    newEdges = [ (u, u, ()) | (u, _) <- ln ]
    oldEdges = [ (u, v, ()) | (u, v, _) <- labEdges g ]

I am following this issue with the corresponding PR.

[LambdaP]

Note that the function rc as modified in #87 is not idempotent: rc (rc g) is not the same graph as rc g in general. This is because the behavior of rcis to add an extra self-loop everywhere regardless of whether a self-loop is already present at a node or not. This is probably connected in nature with #85.

That is not a bug per se, but I feel it is counterintuitive. Mostly, the function insEdges behaves as if it is working on multigraphs rather than on relational graphs where only one edge may exist between two nodes, but this is not made explicit anywhere. I would expect a Graph to correspond to a single-edged graph rather than a multigraph, but that may be only my intuition. The notion itself of a reflexive closure is murkier for multigraphs anyway, since there are infinitely many reflexive supergraphs of any graph.

[andreasabel]

@LambdaP: It is good practice to include a MWE that exposes the problem. From this MWE, you then directly get a test case.

[athas]

This was fixed in #87.

[LambdaP]

@andreasabel I don't think you mean to, but this feels condescending. Here is a 4 years old issue about an obviously extremely wrong piece of code, for which I carefully explained why it was wrong, offered a fix, and then added a conceptual discussion warning about the ambiguities of the API. You pop in out of nowhere 4 years later to educate me about good practice, in a case where I frankly doubt that it would have been worth anyone's time to read, let alone write, an MWE for this, given how transparent the mathematical expression of the code is.

Simultaneously, in the discussion about the related commit, you tell me about some entirely unrelated bug in a library, with vague instructions to check that my commit (which, again, was correcting a piece code that was hopelessly wrong and could not be relied on to do anything remotely sensible) didn't introduce bugs somewhere else, sending me down a trail to understand what's going on with code that has, in fact, nothing to do with something I did and last thought about four years ago.

Please don't treat other people's time as less valuable than yours.

[andreasabel]

@LambdaP: It is good practice to include a MWE that exposes the problem. From this MWE, you then directly get a test case.

Sorry, @LambdaP, didn't mean to be condescending, apologies if you got this wrong.

Yet I stand to my principles. The most helpful bug reports include a MWE. Any bug fix should include a regression test. I won't waiver on this.