You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@hama.apache.org by "Edward J. Yoon (JIRA)" <ji...@apache.org> on 2009/02/25 11:11:05 UTC

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

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


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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon reassigned HAMA-162:
-----------------------------------

    Assignee: Edward J. Yoon

> 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
>            Assignee: 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.


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

Posted by "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=12678204#action_12678204 ] 

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

So, graph just can be handled by sparse matrix/vector API.

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


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Attachment: HAMA-162_v02.patch

> 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
>            Assignee: Edward J. Yoon
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.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.


[jira] Issue Comment Edited: (HAMA-162) Graph package with AdjacencyMatrix/List

Posted by "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=12676954#action_12676954 ] 

udanax edited comment on HAMA-162 at 3/1/09 6:10 PM:
-------------------------------------------------------------

Current 'AdjacencyMatrix' should be named as 'Graph'.

      was (Author: udanax):
    Current AdjacencyMatrix seems better Graph. 
  
> 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.


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

Posted by "Hudson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12678654#action_12678654 ] 

Hudson commented on HAMA-162:
-----------------------------

-1 overall.  Here are the results of testing the latest attachment 
http://issues.apache.org/jira/secure/attachment/12401377/HAMA-162_v02.patch
against trunk revision 748370.

    @author +1.  The patch does not contain any @author tags.

    tests included +1.  The patch appears to include 3 new or modified tests.

    javadoc -1.  The javadoc tool appears to have generated 1 warning messages.

    javac +1.  The applied patch does not generate any new javac compiler warnings.

    release audit +1.  The applied patch does not generate any new release audit warnings.

    findbugs -1.  The patch appears to introduce 1 new Findbugs warnings.

    core tests +1.  The patch passed core unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hama-Patch/161/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hama-Patch/161/artifact/trunk/build/reports/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hama-Patch/161/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hama-Patch/161/console

This message is automatically generated.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Status: Patch Available  (was: Open)

Rescheduling.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "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=12678184#action_12678184 ] 

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

My mis-understand. It doesn't need a DFS. See page 9 - "Adjacency Matrices".

- Another classic graph representation. 
  M[i][j]= '1' implies a link from node i to j.
- Naturally encapsulates iteration over nodes

  | 1  2  3  4
--+----------
1 | 0  1  0  1
2 | 1  0  1  1
3 | 0  1  0  0
4 | 1  0  1  0

So, It can be represented as below:

1 (2, 4)
2 (1, 3, 4)
3 (2)
4 (1, 3)

Then, MR job will iterate until find the shortest path. Let's assume start node is "1".

First MR job:

  1  D=0, points-to=(2, 4)
  2  D=inf, points-to=(1, 3, 4)
  3  D=inf, points-to=(2)
  4  D=inf, points-to=(1, 3)

  Result: (2,1), (4,1)

Second MR job:

  1  D=0, points-to=(2, 4)
  2  D=1, points-to=(1, 3, 4)
  3  D=inf, points-to=(2)
  4  D=1, points-to=(1, 3)

  Result: (2,1), (3,2), (4,1)
----
Here's my test code:

public class BFS {
  static Map<String, ArrayList<String>> collect = new HashMap<String, ArrayList<String>>();
  
  public static void main(String[] args) {
    String[] value = { 
        // key | distance | points-to
        "1|0|2;4",
        "2|"+Integer.MAX_VALUE+"|1;3;4",
        "3|"+Integer.MAX_VALUE+"|2",
        "4|"+Integer.MAX_VALUE+"|1;3",
        };

    mapper(value);
    reducer(collect.entrySet());
  }

  private static void mapper(String[] value) {
    for (int i = 0; i < value.length; i++) {
      String line = value[i].toString();
      String[] keyVal = line.split("[|]");

      String Key = keyVal[0];
      String sDist = keyVal[1];
      String[] links = null;
      if (keyVal.length > 2) {
        links = keyVal[2].split(";");
        int Dist = Integer.parseInt(sDist);

        if (Dist != Integer.MAX_VALUE)
          Dist++;

        for (int x = 0; x < links.length; x++) {
          if (links[x] != "") {
            ArrayList<String> list;
            if (collect.containsKey(links[x])) {
              list = collect.get(links[x]);
            } else {
              list = new ArrayList<String>();
            }

            list.add(Dist + "|");
            collect.put(links[x], list);
          }
        }

        ArrayList<String> list;
        if (collect.containsKey(Key)) {
          list = collect.get(Key);
        } else {
          list = new ArrayList<String>();
        }
        list.add(sDist + "|" + keyVal[2]);
        collect.put(Key, list);
      }
    }
  }

  private static void reducer(Set<Entry<String, ArrayList<String>>> entrySet) {
    for (Map.Entry<String, ArrayList<String>> e : entrySet) {
      Iterator<String> values = e.getValue().iterator();
      int minDist = Integer.MAX_VALUE;
      String link_list = "";

      while (values.hasNext()) {
        String[] dist_links = values.next().toString().split("[|]");
        if (dist_links.length > 1)
          link_list = dist_links[1];

        int dist = Integer.parseInt(dist_links[0]);
        minDist = Math.min(minDist, dist);
      }

      System.out.println(e.getKey() + " - D " + (minDist + " | " + link_list));
    }
  }
}

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


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Attachment: HAMA-162_v01.patch

Replaced to sparse matrix.

> 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
>            Assignee: Edward J. Yoon
>         Attachments: HAMA-162.patch, HAMA-162_v01.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Attachment: HAMA-162.patch

Here's my patch.

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


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

Posted by "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=12676954#action_12676954 ] 

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

Current AdjacencyMatrix seems better Graph. 

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


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

Posted by "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=12679046#action_12679046 ] 

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

I just committed this. 

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Status: Open  (was: Patch Available)

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Attachment: HAMA-162_v03.patch

Removed findbugs and javadoc warnings.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

    Resolution: Won't Fix
        Status: Resolved  (was: Patch Available)

It'll handled later.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "Edward J. Yoon (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Edward J. Yoon updated HAMA-162:
--------------------------------

        Fix Version/s: 0.1.0
    Affects Version/s: 0.1.0
               Status: Patch Available  (was: Open)

Submit to hudson.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.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.


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

Posted by "Hudson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HAMA-162?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12678665#action_12678665 ] 

Hudson commented on HAMA-162:
-----------------------------

+1 overall.  Here are the results of testing the latest attachment 
http://issues.apache.org/jira/secure/attachment/12401387/HAMA-162_v03.patch
against trunk revision 748370.

    @author +1.  The patch does not contain any @author tags.

    tests included +1.  The patch appears to include 3 new or modified tests.

    javadoc +1.  The javadoc tool did not generate any warning messages.

    javac +1.  The applied patch does not generate any new javac compiler warnings.

    release audit +1.  The applied patch does not generate any new release audit warnings.

    findbugs +1.  The patch does not introduce any new Findbugs warnings.

    core tests +1.  The patch passed core unit tests.

Test results: http://hudson.zones.apache.org/hudson/job/Hama-Patch/162/testReport/
Findbugs warnings: http://hudson.zones.apache.org/hudson/job/Hama-Patch/162/artifact/trunk/build/reports/findbugs/newPatchFindbugsWarnings.html
Checkstyle results: http://hudson.zones.apache.org/hudson/job/Hama-Patch/162/artifact/trunk/build/test/checkstyle-errors.html
Console output: http://hudson.zones.apache.org/hudson/job/Hama-Patch/162/console

This message is automatically generated.

> Graph package with AdjacencyMatrix/List
> ---------------------------------------
>
>                 Key: HAMA-162
>                 URL: https://issues.apache.org/jira/browse/HAMA-162
>             Project: Hama
>          Issue Type: New Feature
>    Affects Versions: 0.1.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>             Fix For: 0.1.0
>
>         Attachments: HAMA-162.patch, HAMA-162_v01.patch, HAMA-162_v02.patch, HAMA-162_v03.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.


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

Posted by "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.