[ https://issues.apache.org/jira/browse/HAMA162?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=12676953#action_12676953
]
Edward J. Yoon commented on HAMA162:

To implement distributed BFS:
The BreadthFirst Search & MapReduce was roughly introduced from http://code.google.com/edu/submissions/mapreduceminilecture/lec5pagerank.ppt.
The graph is stored as a sparse matrix, finds shortest path using Map/Reduce as describe below:
Finding the Shortest Path: Intuition
 We can define the solution to this problem inductively:
 DistanceTo(startNode) = 0
 For all nodes n directly reachable from startNode, DistanceTo(n) = 1
 For all nodes n reachable from some other set of nodes S,
 DistanceTo(n) = 1 + min(DistanceTo(m), m ∈ S)
>From Intuition to Algorithm
 A map task receives a node n as a key, and (D, pointsto) as its value
 D is the distance to the node from the start
 pointsto is a list of nodes reachable from n
∀p ∈ pointsto, emit (p, D+1)
 Reduce task gathers possible distances to a given p
and selects the minimum one
According to abovementioned idea, A map task receives a node n as a key, and (D, pointsto)
as its value. It means that an "input" is a set of all reachable path from 'start' to each
key. The graph consisting of a finite number of finite or infinite links. So, Depthfirst
search (DFS) will be needed first and is more important.
> Graph package with AdjacencyMatrix/List
> 
>
> Key: HAMA162
> URL: https://issues.apache.org/jira/browse/HAMA162
> Project: Hama
> Issue Type: New Feature
> Reporter: Edward J. Yoon
> Attachments: HAMA162.patch
>
>
> I made a graph package with AdjacencyMatrix/List, and breadthfirst search example.
> Any advices are welcome.

This message is automatically generated by JIRA.

You can reply to this email to add a comment to the issue online.
