[graph] graph concepts in edmunds-karp algorithm are incomplete
Hello all, I believe the required graph concepts of the Edmunds-Karp algorithm are not complete. The online documentation says the given graph has to be a VertexListGraph. I believe it also has to be a IncidenceGraph, since the algorithm uses breadth-first search, which calls the out-edges of each node successively. Since the algorithm (and all flow algorithms) work on the edges of the graph, edges are needed somewhere, so VertexListGraph cannot be enough in my opinion. Is this correct? Thanks, -- Peter
On Apr 19, 2005, at 4:59 PM, Peter Billen wrote:
I believe the required graph concepts of the Edmunds-Karp algorithm are not complete. The online documentation says the given graph has to be a VertexListGraph. I believe it also has to be a IncidenceGraph, since the algorithm uses breadth-first search, which calls the out-edges of each node successively. Since the algorithm (and all flow algorithms) work on the edges of the graph, edges are needed somewhere, so VertexListGraph cannot be enough in my opinion.
Is this correct?
Yep, you're right. I've fixed the documentation in CVS. Thanks! Doug
participants (2)
-
Doug Gregor -
Peter Billen