incubator-hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From edwardy...@apache.org
Subject svn commit: r750303 - in /incubator/hama/trunk: ./ src/java/org/apache/hama/ src/java/org/apache/hama/graph/ src/test/org/apache/hama/graph/
Date Thu, 05 Mar 2009 03:01:30 GMT
Author: edwardyoon
Date: Thu Mar  5 03:01:30 2009
New Revision: 750303

URL: http://svn.apache.org/viewvc?rev=750303&view=rev
Log:
Add graph package

Added:
    incubator/hama/trunk/src/java/org/apache/hama/graph/
    incubator/hama/trunk/src/java/org/apache/hama/graph/Graph.java
    incubator/hama/trunk/src/java/org/apache/hama/graph/SparseGraph.java
    incubator/hama/trunk/src/test/org/apache/hama/graph/
    incubator/hama/trunk/src/test/org/apache/hama/graph/TestGraph.java
Modified:
    incubator/hama/trunk/CHANGES.txt
    incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java
    incubator/hama/trunk/src/java/org/apache/hama/DenseMatrix.java
    incubator/hama/trunk/src/java/org/apache/hama/SparseMatrix.java

Modified: incubator/hama/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/CHANGES.txt?rev=750303&r1=750302&r2=750303&view=diff
==============================================================================
--- incubator/hama/trunk/CHANGES.txt (original)
+++ incubator/hama/trunk/CHANGES.txt Thu Mar  5 03:01:30 2009
@@ -4,6 +4,7 @@
 
   NEW FEATURES
 
+    HAMA-162: Add Graph using Sparse Matrix (edwardyoon)
     HAMA-151: Add multiplication example of file matrices (edwardyoon)
     HAMA-145: Add privacy policy page (edwardyoon)
     HAMA-83: 2D sqaure blocking for dense matrix multiplication (edwardyoon)

Modified: incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java?rev=750303&r1=750302&r2=750303&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java Thu Mar  5 03:01:30
2009
@@ -55,7 +55,6 @@
  */
 public abstract class AbstractMatrix implements Matrix {
   static int tryPathLength = Constants.DEFAULT_PATH_LENGTH;
-  static final String TABLE_PREFIX = DenseMatrix.class.getSimpleName() + "_";
   static final Logger LOG = Logger.getLogger(AbstractMatrix.class);
 
   protected HamaConfiguration config;
@@ -89,10 +88,10 @@
    * 
    * @throws IOException
    */
-  protected void tryToCreateTable() throws IOException {
+  protected void tryToCreateTable(String table_prefix) throws IOException {
     int tryTimes = Constants.DEFAULT_TRY_TIMES;
     do {
-      matrixPath = TABLE_PREFIX + RandomVariable.randMatrixPath(tryPathLength);
+      matrixPath = table_prefix + "_" + RandomVariable.randMatrixPath(tryPathLength);
 
       if (!admin.tableExists(matrixPath)) { // no table 'matrixPath' in hbase.
         tableDesc = new HTableDescriptor(matrixPath);

Modified: incubator/hama/trunk/src/java/org/apache/hama/DenseMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/DenseMatrix.java?rev=750303&r1=750302&r2=750303&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/DenseMatrix.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/DenseMatrix.java Thu Mar  5 03:01:30 2009
@@ -59,6 +59,7 @@
  * This class represents a dense matrix.
  */
 public class DenseMatrix extends AbstractMatrix implements Matrix {
+  static private final String TABLE_PREFIX = DenseMatrix.class.getSimpleName();
   static private final Path TMP_DIR = new Path(DenseMatrix.class
       .getSimpleName()
       + "_TMP_dir");
@@ -74,7 +75,7 @@
   public DenseMatrix(HamaConfiguration conf) throws IOException {
     setConfiguration(conf);
 
-    tryToCreateTable();
+    tryToCreateTable(TABLE_PREFIX);
 
     closed = false;
   }
@@ -110,7 +111,7 @@
         hamaAdmin.delete(matrixName);
       }
       // create a new matrix table.
-      tryToCreateTable();
+      tryToCreateTable(TABLE_PREFIX);
       // save the new aliase relationship
       save(matrixName);
     } else {
@@ -166,7 +167,7 @@
       throws IOException {
     setConfiguration(conf);
 
-    tryToCreateTable();
+    tryToCreateTable(TABLE_PREFIX);
 
     closed = false;
 

Modified: incubator/hama/trunk/src/java/org/apache/hama/SparseMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/SparseMatrix.java?rev=750303&r1=750302&r2=750303&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/SparseMatrix.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/SparseMatrix.java Thu Mar  5 03:01:30 2009
@@ -35,11 +35,11 @@
 import org.apache.hama.util.RandomVariable;
 
 public class SparseMatrix extends AbstractMatrix implements Matrix {
-
+  static private final String TABLE_PREFIX = SparseMatrix.class.getSimpleName();
   public SparseMatrix(HamaConfiguration conf) throws IOException {
     setConfiguration(conf);
 
-    tryToCreateTable();
+    tryToCreateTable(TABLE_PREFIX);
 
     closed = false;
   }
@@ -65,7 +65,7 @@
     // we don't know where to call Matrix.close in Add & Mul map/reduce
     // process to decrement the reference. It seems difficulty.
   }
-
+  
   /**
    * Generate matrix with random elements
    * 
@@ -85,8 +85,8 @@
     for (int i = 0; i < m; i++) {
       vector.clear();
       for (int j = 0; j < n; j++) {
-        Random r = new Random();
-        if (r.nextInt(2) != 0)
+        Random r = new Random(); 
+        if(r.nextInt(2) != 0)
           vector.set(j, RandomVariable.rand());
       }
       rand.setRow(i, vector);
@@ -95,7 +95,7 @@
     rand.setDimension(m, n);
     return rand;
   }
-
+  
   @Override
   public Matrix add(Matrix B) throws IOException {
     // TODO Auto-generated method stub
@@ -110,9 +110,9 @@
 
   @Override
   public double get(int i, int j) throws IOException {
-    if (this.getRows() < i || this.getColumns() < j)
-      throw new ArrayIndexOutOfBoundsException(i + ", " + j);
-
+    if(this.getRows() < i || this.getColumns() < j)
+      throw new ArrayIndexOutOfBoundsException(i +", "+ j);
+    
     Cell c = table.get(BytesUtil.getRowIndex(i), BytesUtil.getColumnIndex(j));
     return (c != null) ? BytesUtil.bytesToDouble(c.getValue()) : 0.0;
   }
@@ -137,13 +137,13 @@
 
   /** {@inheritDoc} */
   public void set(int i, int j, double value) throws IOException {
-    if (value != 0) {
+    if(value != 0) {
       VectorUpdate update = new VectorUpdate(i);
       update.put(j, value);
       table.commit(update.getBatchUpdate());
     }
   }
-
+  
   /**
    * Returns type of matrix
    */
@@ -161,8 +161,8 @@
     jobConf.setNumMapTasks(config.getNumMapTasks());
     jobConf.setNumReduceTasks(config.getNumReduceTasks());
 
-    SIMDMultiplyMap.initJob(this.getPath(), B.getPath(), this.getType(),
-        SIMDMultiplyMap.class, IntWritable.class, MapWritable.class, jobConf);
+    SIMDMultiplyMap.initJob(this.getPath(), B.getPath(), this.getType(), SIMDMultiplyMap.class,
+        IntWritable.class, MapWritable.class, jobConf);
     SIMDMultiplyReduce.initJob(result.getPath(), SIMDMultiplyReduce.class,
         jobConf);
     JobManager.execute(jobConf);
@@ -185,15 +185,15 @@
   @Override
   public void setColumn(int column, Vector vector) throws IOException {
     // TODO Auto-generated method stub
-
+    
   }
 
   @Override
   public void setRow(int row, Vector vector) throws IOException {
-    if (this.getRows() < row)
+    if(this.getRows() < row)
       increaseRows();
-
-    if (vector.size() > 0) { // stores if size > 0
+    
+    if(vector.size() > 0) {  // stores if size > 0
       VectorUpdate update = new VectorUpdate(row);
       update.putAll(((SparseVector) vector).getEntries());
       table.commit(update.getBatchUpdate());
@@ -206,4 +206,4 @@
     return null;
   }
 
-}
+}
\ No newline at end of file

Added: incubator/hama/trunk/src/java/org/apache/hama/graph/Graph.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/graph/Graph.java?rev=750303&view=auto
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/graph/Graph.java (added)
+++ incubator/hama/trunk/src/java/org/apache/hama/graph/Graph.java Thu Mar  5 03:01:30 2009
@@ -0,0 +1,56 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hama.graph;
+
+import java.io.IOException;
+
+/**
+ * Basic graph interface.
+ */
+public interface Graph {
+
+  /**
+   * Adds an edge from v to w
+   * 
+   * @param v
+   * @param w
+   * @throws IOException
+   */
+  public void addEdge(int v, int w) throws IOException;
+
+  /**
+   * Return the degree of vertex v
+   * 
+   * @param v
+   * @return the degree of vertex v
+   * @throws IOException
+   */
+  public int getDegree(int v) throws IOException;
+
+  /**
+   * Return the array of vertices incident to v
+   * 
+   * @param v
+   * @return the array of vertices incident to v
+   * @throws IOException
+   */
+  public int[] neighborsOf(int v) throws IOException;
+
+}

Added: incubator/hama/trunk/src/java/org/apache/hama/graph/SparseGraph.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/graph/SparseGraph.java?rev=750303&view=auto
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/graph/SparseGraph.java (added)
+++ incubator/hama/trunk/src/java/org/apache/hama/graph/SparseGraph.java Thu Mar  5 03:01:30
2009
@@ -0,0 +1,144 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hama.graph;
+
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.hadoop.hbase.client.HTable;
+import org.apache.hadoop.hbase.client.Scanner;
+import org.apache.hadoop.hbase.io.Cell;
+import org.apache.hadoop.hbase.io.RowResult;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.Text;
+import org.apache.hadoop.io.Writable;
+import org.apache.hama.Constants;
+import org.apache.hama.HamaConfiguration;
+import org.apache.hama.SparseMatrix;
+import org.apache.hama.SparseVector;
+
+/**
+ * A implementation of a graph that is optimized to store edge sparse graphs
+ */
+public class SparseGraph implements Graph {
+  protected HTable table;
+  protected SparseMatrix adjMatrix;
+  protected String name;
+
+  /**
+   * Construct the graph
+   * 
+   * @param conf
+   * @throws IOException
+   */
+  public SparseGraph(HamaConfiguration conf) throws IOException {
+    this.adjMatrix = new SparseMatrix(conf);
+    this.name = adjMatrix.getPath();
+    this.table = adjMatrix.getHTable();
+  }
+
+  /**
+   * Initializes the graph from the given sparse matrix.
+   * 
+   * @param matrix
+   * @throws IOException
+   */
+  public SparseGraph(SparseMatrix matrix) throws IOException {
+    this.adjMatrix = matrix;
+    this.name = matrix.getPath();
+    this.table = matrix.getHTable();
+  }
+
+  /**
+   * add v to w's list of neighbors and w to v's list of neighbors parallel
+   * edges allowed
+   */
+  public void addEdge(int v, int w) throws IOException {
+    adjMatrix.set(v, w, 1.0);
+    adjMatrix.set(w, v, 1.0);
+  }
+
+  /**
+   * Returns the degree of vertex v
+   * 
+   * @param v
+   * @return the degree of vertex v
+   * @throws IOException
+   */
+  public int getDegree(int v) throws IOException {
+    SparseVector adjlist = this.adjMatrix.getRow(v);
+    if (adjlist == null)
+      return 0;
+    else
+      return adjlist.size();
+  }
+
+  /**
+   * Returns the array of vertices incident to v
+   * 
+   * @param v
+   * @return the array of vertices incident to v
+   * @throws IOException
+   */
+  public int[] neighborsOf(int v) throws IOException {
+    SparseVector adjlist = this.adjMatrix.getRow(v);
+    Set<Writable> set = adjlist.getEntries().keySet();
+    int[] arr = new int[set.size()];
+    Iterator<Writable> it = set.iterator();
+    int i = 0;
+    while (it.hasNext()) {
+      arr[i] = ((IntWritable) it.next()).get();
+      i++;
+    }
+
+    return arr;
+  }
+
+  /**
+   * for debugging only
+   */
+  public String toString() {
+    Scanner scan;
+    StringBuilder result = new StringBuilder();
+
+    try {
+      scan = table.getScanner(new String[] { Constants.COLUMN }, "");
+      Iterator<RowResult> it = scan.iterator();
+      while (it.hasNext()) {
+        RowResult rs = it.next();
+        result.append(new Text(rs.getRow()) + ": ");
+        for (Map.Entry<byte[], Cell> e : rs.entrySet()) {
+          result.append(new String(e.getKey()) + " ");
+        }
+        result.append("\n");
+      }
+    } catch (IOException e) {
+      e.printStackTrace();
+    }
+
+    return result.toString();
+  }
+
+  public String getName() {
+    return this.name;
+  }
+}

Added: incubator/hama/trunk/src/test/org/apache/hama/graph/TestGraph.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/test/org/apache/hama/graph/TestGraph.java?rev=750303&view=auto
==============================================================================
--- incubator/hama/trunk/src/test/org/apache/hama/graph/TestGraph.java (added)
+++ incubator/hama/trunk/src/test/org/apache/hama/graph/TestGraph.java Thu Mar  5 03:01:30
2009
@@ -0,0 +1,144 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hama.graph;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Map;
+
+import junit.extensions.TestSetup;
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+import org.apache.hama.HCluster;
+import org.apache.hama.HamaConfiguration;
+import org.apache.log4j.Logger;
+
+public class TestGraph extends TestCase {
+  static final Logger LOG = Logger.getLogger(TestGraph.class);
+  private static HamaConfiguration conf;
+  private static Graph adj;
+  private static int[] result = new int[] { 4, 3, 2, 0, 1 };
+
+  public static Test suite() {
+    TestSetup setup = new TestSetup(new TestSuite(TestGraph.class)) {
+      protected void setUp() throws Exception {
+        HCluster hCluster = new HCluster();
+        hCluster.setUp();
+
+        conf = hCluster.getConf();
+        adj = new SparseGraph(conf);
+      }
+
+      protected void tearDown() {
+      }
+    };
+    return setup;
+  }
+
+  public void testAddEdge() throws IOException {
+    adj.addEdge(0, 1);
+    adj.addEdge(0, 2);
+    adj.addEdge(2, 3);
+    adj.addEdge(3, 4);
+    adj.addEdge(3, 6);
+    adj.addEdge(4, 6);
+
+    LocalBFSearcher bfs = new LocalBFSearcher(adj, 1);
+    int[] path = bfs.path(4);
+
+    for (int i = 0; i < path.length; i++) {
+      assertEquals(result[i], path[i]);
+    }
+  }
+
+  static class LocalBFSearcher {
+    private Map<Integer, Integer> visited = new HashMap<Integer, Integer>();
+
+    public LocalBFSearcher(Graph G, int s) throws IOException {
+      Queue q = new Queue();
+      q.enqueue(s);
+
+      while (!q.isEmpty()) {
+        int v = (Integer) q.dequeue();
+        int[] neighbors = G.neighborsOf(v);
+        for (int i = 0; i < neighbors.length; i++) {
+          int w = neighbors[i];
+          if (visited.get(w) == null) {
+            q.enqueue(w);
+            if (s != w)
+              visited.put(w, v);
+          }
+        }
+      }
+    }
+
+    public int pathLength(int v) {
+      int len = -1;
+      while (visited.get(v) != null) {
+        v = (Integer) visited.get(v);
+        len++;
+      }
+      return len;
+    }
+
+    public int[] path(int v) {
+      int N = pathLength(v);
+      int[] p = new int[N + 1];
+      for (int i = 0; i <= N; i++) {
+        p[i] = v;
+        v = (Integer) visited.get(v);
+      }
+      return p;
+    }
+  }
+
+  static class Queue {
+    private Node first;
+    private Node last;
+
+    public boolean isEmpty() {
+      return (first == null);
+    }
+
+    public void enqueue(Object anItem) {
+      Node x = new Node();
+      x.item = anItem;
+      x.next = null;
+      if (isEmpty())
+        first = x;
+      else
+        last.next = x;
+      last = x;
+    }
+
+    public Object dequeue() {
+      Object val = first.item;
+      first = first.next;
+      return val;
+    }
+  }
+
+  static class Node {
+    Object item;
+    Node next;
+  }
+}



Mime
View raw message