giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Eli Reisman <apache.mail...@gmail.com>
Subject Re: Network flow problems in Giraph
Date Sat, 20 Apr 2013 14:26:50 GMT
I would point this question at Sebastian or Claudio, but my instict is yes
this is a good fit for Giraph.


On Thu, Apr 18, 2013 at 10:41 AM, Jay Hutfles <jayhutfles@gmail.com> wrote:

> Actually, I think a max flow problem fits exactly with the batch
> processing model you describe.  You are given a massive graph (with
> predefined maximum flows along the edges between vertices), you run a
> program, it produces an output (i.e. the flow along each edge) and it
> terminates.  It's not necessarily adapting to any new inputs as it runs.
>  But it is an iterative process.  Or, at least, many algorithms are.
>
> I don't see it as being that different from Djikstra's Method for finding
> the shortest distance between two nodes on a graph.  Each super step is
> updating the labels along the graph, and when all notes are labelled as
> done, the algorithm finishes.  A max flow problem could be implemented
> likewise, since there are labeling algorithms for determining the max flow
> along a graph.
>
> See http://en.wikipedia.org/wiki/Maximum_flow_problem, specifically the
> Solutions section.  I think it should help clarify.
>
>
>
> On Thu, Apr 18, 2013 at 9:16 AM, André Kelpe <
> efeshundertelf@googlemail.com> wrote:
>
>> 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