[jira] Commented: (HAMA-162) Graph package with AdjacencyMatrix/List

["Edward J. Yoon (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12676953#action_12676953 ] 

Edward J. Yoon commented on HAMA-162:
-------------------------------------

To implement distributed BFS:

The Breadth-First Search & MapReduce was roughly introduced from http://code.google.com/edu/submissions/mapreduce-minilecture/lec5-pagerank.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, points-to) as its value
 - D is the distance to the node from the start
 - points-to is a list of nodes reachable from n
    ∀p ∈ points-to, emit (p, D+1)
- Reduce task gathers possible distances to a given p 
  and selects the minimum one


According to above-mentioned idea, A map task receives a node n as a key, and (D, points-to) 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, Depth-first search (DFS) will be needed first and is more important. 

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>            Reporter: Edward J. Yoon
>         Attachments: HAMA-162.patch
>
>
> I made a graph package with AdjacencyMatrix/List, and breadth-first 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.