Thanks for the reply, Sebastian. The problem I'm working on is a routing algorithm for a country wide railway network. I was thinking about two ways to approach it.
1. Pre calculate the routes. I understand that this is quadratic, but I was thinking of using some optimizations to limit the calculations. Like restrict the number of hops from the source node, only calculate the route to the nearest hub and not every other node, etc. 2. Use Giraph as a real time query engine - The graph is loaded into the memory of a cluster of nodes, and given the source and destination nodes of a query, a single source shortest path algorithm is run. For both these cases, I thought it would be useful have the vertices always in memory, and only repeat the process from superstep 0 as needed. For example, every time we have a new query, or every time we need to calculate a route from a source to a new destination. On Tue, Sep 25, 2012 at 1:25 AM, Sebastian Schelter <s...@apache.org> wrote: > Hi Venkata, > > The result of All-Pairs-Shortest-Paths is quadratic in the number of > vertices which makes it infeasible for sufficiently large graphs. > > Best, > Sebastian > > > On 24.09.2012 20:24, Venkata Sastry Malladi wrote: > > I'm thinking of modifying the simple shortest paths algorithm so that it > > calculates the shortest paths between all pairs of nodes (not just from a > > single source node). I wanted to get some general advice on whether these > > are feasible in Giraph: > > > > 1. Without quitting the job after all vertices voteToHalt(), is it > possible > > to just restart from superstep 0, but with a different source node? In > > other words, when we want to do simultaneous runs of the simple shortest > > paths algorithm, how can we avoid the overhead of re-reading the graph > into > > memory between the runs? > > > > 2. Is it possible to run some kind of reducer before the vertices are > > written to the output? Let's say the VertexWriter outputs something like > > (Source, Destination) -> Route for each node. Is it possible to combine > > many such outputs to produce a single output? Like (Source, Destination) > - > >> (Route1, Route2, Route3). > > > > Thanks, > > Venkat. > > > >
