haskell / haskell/fgl

Data.Graph.Inductive.Basic.undir appears to handle self-edges wrongly

Open
#85 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
200
Forks
58
PR merge metrics
No merged PRs in 30d

Description

According to the [documentation](http://hackage.haskell.org/package/fgl-5.7.0.1/docs/Data-Graph-Inductive-Basic.html#v:undir) of `undir`, we get:

"Make the graph undirected, i.e. for every edge from A to B, there exists an edge from B to A."

My expectation would be that if a graph has an edge from C to C, then well, in undirected form it will still have an edge from C to C, and that's it (concerning that self-edge). Except, I noticed something different. Here is a piece of code I had, with printing added for debugging:
```haskell
print theNodes
print theEdges
let numberedNodes = zip [0..] theNodes
let graph = undir (mkGraph numberedNodes theEdges) :: Gr String String
print graph
```
And here is the printed output:
```
["D$0","D$1","B$0","A$0"]
[(3,3,"y"),(3,0,"z"),(3,1,"z")]
mkGraph [(0,"D$0"),(1,"D$1"),(2,"B$0"),(3,"A$0")] [(0,3,"z"),(1,3,"z"),(3,0,"z"),(3,1,"z"),(3,3,"y"),(3,3,"y")]
```
Note the double occurrence of `(3,3,"y")` in there.

I get how the edges `(3,0,"z"),(3,1,"z")` before `undir` turn into `(0,3,"z"),(1,3,"z"),(3,0,"z"),(3,1,"z")` after it.

But why was the original edge `(3,3,"y")` duplicated into `(3,3,"y"),(3,3,"y")`? That seems uncalled for (and led to a wrong picture when feeding this graph into `GraphViz`).

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.