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 <[email protected]> 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 < > [email protected]> 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 <[email protected]>: >> > 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! >> > >
