giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From André Kelpe <efeshundert...@googlemail.com>
Subject Re: Network flow problems in Giraph
Date Thu, 18 Apr 2013 14:16:51 GMT
Hi Jay,

this sounds like a continuous operation to me. Giraph is meant for
batch processing of massive graphs, which produces an output after a
successful run. You run a program, it produces an output, it
terminates. From what I understand, a stream processing framework like
storm (https://github.com/nathanmarz/storm/wiki/Rationale) could be a
better fit for this. Please let me know, if I am missing something.

André

2013/4/18 Jay Hutfles <jayhutfles@gmail.com>:
> 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