giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jay Hutfles <jayhutf...@gmail.com>
Subject Network flow problems in Giraph
Date Thu, 18 Apr 2013 14:06:58 GMT
I'm new to Giraph, but am interested in its applications to classic network
flow problems, specifically max flow or min cost problems.  I've looked for
BSP implementations of algorithms for these problems, but I can't find any
discussion regarding this online.  Has anyone had luck implementing such
problems?


The max flow problem seems like it should be adaptable to the BSP model.
 The flow augmenting algorithm developed by Ford and Fulkerson is
essentially:

while the graph contains a path over which flow could be increased,
   increase flow for arcs on the path

Identifying the flow augmenting paths is a simple labeling algorithm, but
I'm not sure how I'd implement the "while the graph contains ..."
condition.  Is that a super step *above* the labeling algorithm's super
steps?


And I have no idea how to start the min cost algorithm.  Anyone have ideas
for how to formulate this?

Thanks for your time, and for the great work on Giraph!

Mime
View raw message