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