[Bigdata-commit] SF.net SVN: bigdata:[8034] branches/RDR/bigdata-gas/src/java/com/bigdata/ rdf/graph/analytics/SSSP.java

[<mrp...@us...>]

Revision: 8034
          http://sourceforge.net/p/bigdata/code/8034
Author:   mrpersonick
Date:     2014-04-03 21:15:33 +0000 (Thu, 03 Apr 2014)
Log Message:
-----------
added a predecessor field and implemented the IPredecessor interface

Modified Paths:
--------------
    branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java

Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java	2014-04-03 13:23:17 UTC (rev 8033)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java	2014-04-03 21:15:33 UTC (rev 8034)
@@ -15,7 +15,9 @@
 */
 package com.bigdata.rdf.graph.analytics;
 
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 
 import org.apache.log4j.Logger;
@@ -31,6 +33,7 @@
 import com.bigdata.rdf.graph.IGASContext;
 import com.bigdata.rdf.graph.IGASScheduler;
 import com.bigdata.rdf.graph.IGASState;
+import com.bigdata.rdf.graph.IPredecessor;
 import com.bigdata.rdf.graph.impl.BaseGASProgram;
 
 /**
@@ -46,7 +49,8 @@
  *         so we need a different data structure to collect them (we need to
  *         store the predecesor when we run SSSP to do this).
  */
-public class SSSP extends BaseGASProgram<SSSP.VS, SSSP.ES, Integer/* dist */> {
+public class SSSP extends BaseGASProgram<SSSP.VS, SSSP.ES, Integer/* dist */> 
+		implements IPredecessor<SSSP.VS, SSSP.ES, Integer/* dist */> {
 
     private static final Logger log = Logger.getLogger(SSSP.class);
 
@@ -101,6 +105,15 @@
          */
         private final AtomicReference<Value> predecessor = new AtomicReference<Value>();
 
+        /**
+         * Return the vertex preceding this vertex on the shortest path.
+         */
+        public Value predecessor() {
+
+            return predecessor.get();
+            
+        }
+
 //        /**
 //         * Set the distance for the vertex to ZERO. This is done for the
 //         * starting vertex.
@@ -445,6 +458,22 @@
             }
         });
 
+        tmp.add(new IBinder<SSSP.VS, SSSP.ES, Integer>() {
+            
+            @Override
+            public int getIndex() {
+                return Bindings.PREDECESSOR;
+            }
+            
+            @Override
+            public Value bind(final ValueFactory vf,
+                    final IGASState<SSSP.VS, SSSP.ES, Integer> state, final Value u) {
+
+                return state.getState(u).predecessor.get();
+
+            }
+        });
+
         return tmp;
 
     }
@@ -461,6 +490,58 @@
          */
         int DISTANCE = 1;
         
+        /**
+         * The predecessor vertex on a shortest path.
+         * 
+         */
+        int PREDECESSOR = 2;
+        
     }
 
+	@Override
+	public void prunePaths(IGASContext<VS, ES, Integer> ctx,
+			Value[] targetVertices) {
+		
+        if (ctx == null)
+            throw new IllegalArgumentException();
+
+        if (targetVertices == null)
+            throw new IllegalArgumentException();
+        
+        final IGASState<SSSP.VS, SSSP.ES, Integer> gasState = ctx.getGASState();
+
+        final Set<Value> retainSet = new HashSet<Value>();
+
+        for (Value v : targetVertices) {
+
+            if (!gasState.isVisited(v)) {
+
+                // This target was not reachable.
+                continue;
+
+            }
+
+            /*
+             * Walk the precessors back to a starting vertex.
+             */
+            Value current = v;
+
+            while (current != null) {
+
+                retainSet.add(current);
+
+                final SSSP.VS currentState = gasState.getState(current);
+
+                final Value predecessor = currentState.predecessor();
+
+                current = predecessor;
+
+            }
+            
+        } // next target vertex.
+        
+        gasState.retainAll(retainSet);
+		
+	}
+
 }

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.