[Haskell-cafe] Re: Bug in Data.Graph

[Christophe Poucet]

I just realized that I was looking at dependencies the wrong way (which 
is where I'm using this).  So please ignore, the implementation is 
correct, I just made a mental typo :/

Christophe Poucet wrote:

> Dear,
>
> 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)
> 1
> / \
> | 3
> |/
> 2
> |
> 4
>
> Therefore one would expect [4,2,3,1].
>
> Is this a bug in the documentation or the implementation?
>
> With regards,
> Christophe
>


-- 
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
*****DISCLAIMER*****
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.
**********