[
https://issues.apache.org/jira/browse/GIRAPH-1254?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17514165#comment-17514165
]
mohit commented on GIRAPH-1254:
-------------------------------
Here is the pseudo code for the Algorithm.
# Select an arbitrary vertex, call it vertex v.
# start a distributed algorithm from vertex v, to build a BFS T_v
# Send a pebble P on T_v
# Distributed protocol to be run on each vertex x
## while P reaches x
### if P visits x for the first time then
#### wait one time slot ('iterative step' in Giraph lingo)
#### start a BFS at T_x
Constructing a BFS tree: basically message propagation.
Note that in the above psudo code, I did not explicitly mention about computing
APSP, but when BFS trees are computing, it is implict on computation of BFS
tree, the level of a vertex in a BFS tree is equal to the length of APSP.
Run time guarantee: O(n) rounds (iterative steps), with low bandwidth messages
exchanged between only adjacent vertices.
// any feedback is welcome.
> A linear round complexity algorithm for unweighted, exact all pairs shortest
> path (APSP)
> ----------------------------------------------------------------------------------------
>
> Key: GIRAPH-1254
> URL: https://issues.apache.org/jira/browse/GIRAPH-1254
> Project: Giraph
> Issue Type: New Feature
> Components: examples
> Affects Versions: 1.3.0
> Reporter: mohit
> Priority: Minor
>
> In the theory community (mainly targeting PODC, SODA, FOCS, and STOC),
> several graph algorithms for APSP have been developed in the abstract model
> of vertex-centric computation. These distinguished themselves upon
> # weighted vs unweighted
> # randomized vs deterministic
> # exact vs approximation
> # permission for message passing, and message size
> ## between only adjacent vertices
> ## between any two vertices in the graph
> This Jira is to implement a simple linear-time algorithm for APSP (discussed
> on the dev list). An algorithm for a fundamental problem like APSP has
> several practical use cases, for example in developing large scale
> recommender systems. This implementation would also lead the way forward for
> some recent results claiming poly log round complexity for various graph
> algorithms in the aforementioned graph model.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
