incubator-hama-dev mailing list archives

Site index · List index
Message view
Top
From "Edward J. Yoon (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HAMA-162) Graph package with AdjacencyMatrix/List
Date Thu, 26 Feb 2009 10:15:01 GMT
```
[ 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 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.

> ---------------------------------------
>
>                 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
>
>