[Haskell-cafe] Bug in Data.Graph

Christophe Poucet christophe.poucet at gmail.com
Sat Jun 3 21:17:15 EDT 2006


I think I have discovered a bug in Data.Graph. If one looks at the 
documentation it states:

Vertex = (Node, Node)
An edge from the first vertex to the second.
Ergo (i,j) => j is reachable from i

Then continuing, one reads that:
topSort :: Graph -> [Vertex]
A topological sort of the graph. The order is partially specified by the 
condition that a vertex /i/ precedes /j/ whenever /j/ is reachable from 
/i/ but not vice versa.

However if one tries to evaluate it, one gets:
 > print . G.components $ G.buildG (1,4) [(1,2), (1,3), (2,4), (2,3)]
 > [1,3,2,4]

According to specification we have the graph (with arrows pointing down)
/ \
| 3

Therefore one would expect [4,2,3,1].

Is this a bug in the documentation or the implementation?

With regards,

Christophe Poucet
Ph.D. Student
Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
Website: http://notvincenz.com/  
IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be
This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s).
Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments.

More information about the Haskell-Cafe mailing list