# 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 Tue, 03 Mar 2009 01:27:56 GMT
```
[ 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) {
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;
} else {
list = new ArrayList<String>();
}

}
}

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)

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.

```
Mime
View raw message