incubator-hama-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Edward J. Yoon (JIRA)" <>
Subject [jira] Commented: (HAMA-162) Graph package with AdjacencyMatrix/List
Date Thu, 26 Feb 2009 10:15:01 GMT


Edward J. Yoon commented on HAMA-162:

To implement distributed BFS:

The Breadth-First Search & MapReduce was roughly introduced from
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:
>             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.

View raw message