search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
184 stars 54 forks source link

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

Open jvoigtlaender opened 5 years ago

jvoigtlaender commented 5 years ago

According to the documentation 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:

  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).