Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[8055] branches/RDR
|
From: <mrp...@us...> - 2014-04-04 19:56:45
|
Revision: 8055
http://sourceforge.net/p/bigdata/code/8055
Author: mrpersonick
Date: 2014-04-04 19:56:42 +0000 (Fri, 04 Apr 2014)
Log Message:
-----------
added support for multiple bindings to an output variable on a gas program service call
Modified Paths:
--------------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IBinder.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/BFS.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/CC.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PATHS.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PR.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/BaseGASProgram.java
branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java
branches/RDR/bigdata-sails/src/test/com/bigdata/rdf/sail/graph/paths4.rq
Added Paths:
-----------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/BinderBase.java
Added: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/BinderBase.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/BinderBase.java (rev 0)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/BinderBase.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -0,0 +1,70 @@
+/**
+ Copyright (C) SYSTAP, LLC 2006-2012. All rights reserved.
+
+ Licensed 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 com.bigdata.rdf.graph;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.openrdf.model.Value;
+import org.openrdf.model.ValueFactory;
+
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IVariable;
+
+/**
+ * A base class for IBinders.
+ */
+public abstract class BinderBase<VS, ES, ST> implements IBinder<VS, ES, ST> {
+
+ /**
+ * The ordinal index of the variable that is bound by this
+ * {@link BinderBase}. By convention, index ZERO is the vertex. Indices
+ * greater than ZERO are typically aspects of the state of the vertex.
+ */
+ @Override
+ public abstract int getIndex();
+
+ /**
+ * Subclasses can implement this method if they follow the old single
+ * bind paradigm.
+ */
+ public abstract Value bind(ValueFactory vf, final IGASState<VS, ES, ST> state, Value v);
+
+ /**
+ * Call {@link #bind(ValueFactory, IGASState, Value)}.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public List<Value> bind(final ValueFactory vf, final IGASState<VS, ES, ST> state,
+ final Value u, final IVariable<?>[] outVars, final IBindingSet bs) {
+
+ final Value val = bind(vf, state, u);
+
+ if (val == null) {
+
+ return Collections.EMPTY_LIST;
+
+ } else {
+
+ return Arrays.asList(new Value[] { val });
+
+ }
+
+ }
+
+}
+
Property changes on: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/BinderBase.java
___________________________________________________________________
Added: svn:mime-type
## -0,0 +1 ##
+text/plain
\ No newline at end of property
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IBinder.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IBinder.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IBinder.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -15,9 +15,14 @@
*/
package com.bigdata.rdf.graph;
+import java.util.List;
+
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IVariable;
+
/**
* An interface that may be used to extract variable bindings for the
* vertices visited by the algorithm.
@@ -35,17 +40,35 @@
int getIndex();
/**
+ * New multi-binding strategy allows binders to bind multiple values to
+ * a given output variable (multiplying the number of solutions by the
+ * number of bindings).
+ *
* @param vf
* The {@link ValueFactory} used to create the return
* {@link Value}.
+ *
+ * @param state
+ * The {@link IGASState}.
+ *
* @param u
- * The vertex.
+ * The vertex.
*
+ * @param outVars
+ * The array of output variables.
+ *
+ * @param bs
+ * The current binding set. Can be used to conditionally bind
+ * values based on the current solution.
+ *
* @return The {@link Value} for that ordinal variable or
* <code>null</code> if there is no binding for that ordinal
* variable.
*/
- Value bind(ValueFactory vf, final IGASState<VS, ES, ST> state, Value u);
+ List<Value> bind(ValueFactory vf, IGASState<VS, ES, ST> state,
+ Value u, IVariable<?>[] outVars, IBindingSet bs);
+// Value bind(ValueFactory vf, final IGASState<VS, ES, ST> state, Value u);
+
}
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/BFS.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/BFS.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/BFS.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -25,6 +25,7 @@
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -282,7 +283,7 @@
final List<IBinder<BFS.VS, BFS.ES, Void>> tmp = super.getBinderList();
- tmp.add(new IBinder<BFS.VS, BFS.ES, Void>() {
+ tmp.add(new BinderBase<BFS.VS, BFS.ES, Void>() {
@Override
public int getIndex() {
@@ -296,9 +297,10 @@
return vf.createLiteral(state.getState(u).depth.get());
}
+
});
- tmp.add(new IBinder<BFS.VS, BFS.ES, Void>() {
+ tmp.add(new BinderBase<BFS.VS, BFS.ES, Void>() {
@Override
public int getIndex() {
@@ -312,6 +314,7 @@
return state.getState(u).predecessor.get();
}
+
});
return tmp;
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/CC.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/CC.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/CC.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -27,6 +27,7 @@
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -319,7 +320,7 @@
final List<IBinder<CC.VS, CC.ES, Value>> tmp = super.getBinderList();
- tmp.add(new IBinder<CC.VS, CC.ES, Value>() {
+ tmp.add(new BinderBase<CC.VS, CC.ES, Value>() {
@Override
public int getIndex() {
@@ -333,6 +334,7 @@
return state.getState(u).label.get();
}
+
});
return tmp;
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PATHS.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PATHS.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PATHS.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -15,20 +15,25 @@
*/
package com.bigdata.rdf.graph.analytics;
-import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
-import java.util.Iterator;
+import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
+import java.util.LinkedList;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import org.apache.log4j.Logger;
import org.openrdf.model.Statement;
+import org.openrdf.model.URI;
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IVariable;
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -39,14 +44,15 @@
import com.bigdata.rdf.graph.IGASState;
import com.bigdata.rdf.graph.IPredecessor;
import com.bigdata.rdf.graph.impl.BaseGASProgram;
+import com.bigdata.rdf.internal.IV;
/**
- * Breadth First Search (BFS) is an iterative graph traversal primitive. The
- * frontier is expanded iteratively until no new vertices are discovered. Each
- * visited vertex is marked with the round (origin ZERO) in which it was
- * visited. This is its distance from the initial frontier.
- *
- * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ * PATHS is an iterative graph traversal operation. The frontier is expanded
+ * iteratively until no new vertices are discovered, or until the target
+ * vertices have all been reached. Each vertex is marked with its depth and with
+ * a list of all predecessors and their edges to the vertex. This algorithm is
+ * useful for creating a complete connected subgraph between a source and a set
+ * of targets.
*/
public class PATHS extends BaseGASProgram<PATHS.VS, PATHS.ES, Void> implements
IPredecessor<PATHS.VS, PATHS.ES, Void> {
@@ -70,11 +76,12 @@
private final AtomicInteger depth = new AtomicInteger(-1);
/**
- * The predecessors are the first source vertex to visit a given target
- * vertex.
+ * The predecessors are the source vertices to visit a given target
+ * vertex. Each one has a list of edges along which they were able to
+ * reach this vertex.
*/
- private final Set<Value> predecessors =
- Collections.synchronizedSet(new LinkedHashSet<Value>());
+ private final Map<Value, Set<URI>> predecessors =
+ Collections.synchronizedMap(new LinkedHashMap<Value, Set<URI>>());
/**
* The depth at which this vertex was first visited (origin ZERO) and
@@ -87,13 +94,33 @@
}
/**
- * Return the first vertex to discover this vertex during BFS traversal.
+ * Return the vertices that discovered this vertex during BFS traversal.
*/
- public Set<Value> predecessors() {
+ public Map<Value, Set<URI>> predecessors() {
return predecessors;
}
+
+ /**
+ * Add a predecessor (might have already been added) and the edge
+ * along which the predecessor discovered this vertex.
+ */
+ public synchronized void addPredecessor(final Value pred, final URI edge) {
+
+ Set<URI> edges = predecessors.get(pred);
+
+ if (edges == null) {
+
+ edges = new LinkedHashSet<URI>();
+
+ predecessors.put(pred, edges);
+
+ }
+
+ edges.add(edge);
+
+ }
/**
* Note: This marks the vertex at the current traversal depth.
@@ -103,21 +130,20 @@
* first visited the vertex (this helps to avoid multiple
* scheduling of a vertex).
*/
- public boolean visit(final int depth, final Value predecessor) {
- if (predecessor != null)
- this.predecessors.add(predecessor);
+ public boolean visit(final int depth, final Value pred, final URI edge) {
+
+ if (pred != null) {
+// this.predecessors.add(pred);
+ addPredecessor(pred, edge);
+ }
+
if (this.depth.compareAndSet(-1/* expect */, depth/* newValue */)) {
// Scheduled by this thread.
return true;
}
+
return false;
-// synchronized (this) {
-// if (this.depth == -1) {
-// this.depth = depth;
-// return true;
-// }
-// return false;
-// }
+
}
@Override
@@ -187,7 +213,7 @@
public void initVertex(final IGASContext<PATHS.VS, PATHS.ES, Void> ctx,
final IGASState<PATHS.VS, PATHS.ES, Void> state, final Value u) {
- state.getState(u).visit(0, null/* predecessor */);
+ state.getState(u).visit(0, null/* predecessor */, null/* edge */);
}
@@ -245,11 +271,6 @@
public void scatter(final IGASState<PATHS.VS, PATHS.ES, Void> state,
final IGASScheduler sch, final Value u, final Statement e) {
-// if (state.getTargetVertices().contains(u)) {
-// // don't schedule any more vertices, we've hit a target
-// return;
-// }
-
// remote vertex state.
final Value v = state.getOtherVertex(u, e);
@@ -257,7 +278,7 @@
// final VS otherState = state.getState(e.getObject()/* v */);
// visit.
- if (otherState.visit(state.round() + 1, u/* predecessor */)) {
+ if (otherState.visit(state.round() + 1, u/* predecessor */, e.getPredicate())) {
/*
* This is the first visit for the remote vertex. Add it to the
@@ -284,9 +305,12 @@
* <dt>{@value Bindings#DEPTH}</dt>
* <dd>The depth at which the vertex was first encountered during traversal.
* </dd>
- * <dt>{@value Bindings#PREDECESSOR}</dt>
- * <dd>The predecessor is the first vertex that discovers a given vertex
+ * <dt>{@value Bindings#PREDECESSORS}</dt>
+ * <dd>The predecessors are all the vertices that discovers a given vertex
* during traversal.</dd>
+ * <dt>{@value Bindings#EDGES}</dt>
+ * <dd>These are the edges along which each predecessor discovered a given
+ * vertex during traversal.</dd>
* </dl>
*/
@Override
@@ -294,7 +318,7 @@
final List<IBinder<PATHS.VS, PATHS.ES, Void>> tmp = super.getBinderList();
- tmp.add(new IBinder<PATHS.VS, PATHS.ES, Void>() {
+ tmp.add(new BinderBase<PATHS.VS, PATHS.ES, Void>() {
@Override
public int getIndex() {
@@ -308,28 +332,89 @@
return vf.createLiteral(state.getState(u).depth.get());
}
+
});
tmp.add(new IBinder<PATHS.VS, PATHS.ES, Void>() {
@Override
public int getIndex() {
- return Bindings.PREDECESSOR;
+ return Bindings.PREDECESSORS;
}
@Override
- public Value bind(final ValueFactory vf,
- final IGASState<PATHS.VS, PATHS.ES, Void> state, final Value u) {
+ public List<Value> bind(final ValueFactory vf,
+ final IGASState<PATHS.VS, PATHS.ES, Void> state,
+ final Value u, final IVariable<?>[] outVars,
+ final IBindingSet bs) {
- final String s = Arrays.toString(state.getState(u).predecessors.toArray());
+ final VS vs = state.getState(u);
- if (log.isTraceEnabled()) {
- log.trace(s);
+ return new LinkedList<Value>(vs.predecessors().keySet());
+
+ }
+
+ });
+
+ tmp.add(new IBinder<PATHS.VS, PATHS.ES, Void>() {
+
+ @Override
+ public int getIndex() {
+ return Bindings.EDGES;
+ }
+
+ @Override
+ @SuppressWarnings({ "rawtypes", "unchecked" })
+ public List<Value> bind(final ValueFactory vf,
+ final IGASState<PATHS.VS, PATHS.ES, Void> state,
+ final Value u, final IVariable<?>[] outVars,
+ final IBindingSet bs) {
+
+ /*
+ * We want to return a different set of edges depending on
+ * which predecessor the caller is asking about. We can
+ * find that information in the binding set.
+ */
+
+ final IVariable<?> var = outVars[Bindings.PREDECESSORS];
+
+ if (!bs.isBound(var)) {
+
+ if (log.isTraceEnabled()) {
+ log.trace("no predecessors");
+ }
+
+ return Collections.EMPTY_LIST;
+
}
- return vf.createLiteral(s);
+ final IV predIV = (IV) bs.get(var).get();
+
+ final Value predVal;
+
+ if (predIV instanceof Value) {
+
+ predVal = (Value) predIV;
+
+ } else if (predIV.hasValue()) {
+
+ predVal = predIV.getValue();
+
+ } else {
+
+ throw new RuntimeException("FIXME");
+
+ }
+
+ final VS vs = state.getState(u);
+
+ /*
+ * Return the edges for this predecessor.
+ */
+ return new LinkedList<Value>(vs.predecessors().get(predVal));
}
+
});
return tmp;
@@ -349,70 +434,18 @@
int DEPTH = 1;
/**
- * The BFS predecessor is the first vertex to discover a given vertex.
+ * The predecessors are all vertices to discover a given vertex.
*
*/
- int PREDECESSOR = 2;
+ int PREDECESSORS = 2;
+ /**
+ * The edges along which each predecessor discovered a given vertex.
+ */
+ int EDGES = 3;
+
}
-// /**
-// * Reduce the active vertex state, returning a histogram reporting the #of
-// * vertices at each distance from the starting vertex. There will always be
-// * one vertex at depth zero - this is the starting vertex. For each
-// * successive depth, the #of vertices that were labeled at that depth is
-// * reported. This is essentially the same as reporting the size of the
-// * frontier in each round of the traversal, but the histograph is reported
-// * based on the vertex state.
-// *
-// * @author <a href="mailto:tho...@us...">Bryan
-// * Thompson</a>
-// */
-// protected static class HistogramReducer implements
-// IReducer<VS, ES, Void, Map<Integer, AtomicLong>> {
-//
-// private final ConcurrentHashMap<Integer, AtomicLong> values = new ConcurrentHashMap<Integer, AtomicLong>();
-//
-// @Override
-// public void visit(final IGASState<VS, ES, Void> state, final Value u) {
-//
-// final VS us = state.getState(u);
-//
-// if (us != null) {
-//
-// final Integer depth = Integer.valueOf(us.depth());
-//
-// AtomicLong newval = values.get(depth);
-//
-// if (newval == null) {
-//
-// final AtomicLong oldval = values.putIfAbsent(depth,
-// newval = new AtomicLong());
-//
-// if (oldval != null) {
-//
-// // lost data race.
-// newval = oldval;
-//
-// }
-//
-// }
-//
-// newval.incrementAndGet();
-//
-// }
-//
-// }
-//
-// @Override
-// public Map<Integer, AtomicLong> get() {
-//
-// return Collections.unmodifiableMap(values);
-//
-// }
-//
-// }
-
/*
* TODO Do this in parallel for each specified target vertex.
*/
@@ -428,10 +461,6 @@
final IGASState<PATHS.VS, PATHS.ES, Void> gasState = ctx.getGASState();
-// for (Value v : gasState.values()) {
-// log.trace(v);
-// }
-
final Set<Value> retainSet = new HashSet<Value>();
for (Value v : targetVertices) {
@@ -450,20 +479,6 @@
visitPredecessors(gasState, v, retainSet);
-// Value current = v;
-//
-// while (current != null) {
-//
-// retainSet.add(current);
-//
-// final PATHS.VS currentState = gasState.getState(current);
-//
-// final Value predecessor = currentState.predecessor();
-//
-// current = predecessor;
-//
-// }
-
} // next target vertex.
gasState.retainAll(retainSet);
@@ -476,7 +491,7 @@
final PATHS.VS currentState = gasState.getState(v);
- for (Value pred : currentState.predecessors()) {
+ for (Value pred : currentState.predecessors().keySet()) {
if (pred == null) {
@@ -498,71 +513,4 @@
}
-// @Override
-// public <T> IReducer<VS, ES, Void, T> getDefaultAfterOp() {
-//
-// class NV implements Comparable<NV> {
-// public final int n;
-// public final long v;
-// public NV(final int n, final long v) {
-// this.n = n;
-// this.v = v;
-// }
-// @Override
-// public int compareTo(final NV o) {
-// if (o.n > this.n)
-// return -1;
-// if (o.n < this.n)
-// return 1;
-// return 0;
-// }
-// }
-//
-// final IReducer<VS, ES, Void, T> outerReducer = new IReducer<VS, ES, Void, T>() {
-//
-// final HistogramReducer innerReducer = new HistogramReducer();
-//
-// @Override
-// public void visit(IGASState<VS, ES, Void> state, Value u) {
-//
-// innerReducer.visit(state, u);
-//
-// }
-//
-// @Override
-// public T get() {
-//
-// final Map<Integer, AtomicLong> h = innerReducer.get();
-//
-// final NV[] a = new NV[h.size()];
-//
-// int i = 0;
-//
-// for (Map.Entry<Integer, AtomicLong> e : h.entrySet()) {
-//
-// a[i++] = new NV(e.getKey().intValue(), e.getValue().get());
-//
-// }
-//
-// Arrays.sort(a);
-//
-// System.out.println("distance, frontierSize, sumFrontierSize");
-// long sum = 0L;
-// for (NV t : a) {
-//
-// System.out.println(t.n + ", " + t.v + ", " + sum);
-//
-// sum += t.v;
-//
-// }
-//
-// return null;
-// }
-//
-// };
-//
-// return outerReducer;
-//
-// }
-
}
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PR.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PR.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/PR.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -25,6 +25,7 @@
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -352,7 +353,7 @@
final List<IBinder<PR.VS, PR.ES, Double>> tmp = super.getBinderList();
- tmp.add(new IBinder<PR.VS, PR.ES, Double>() {
+ tmp.add(new BinderBase<PR.VS, PR.ES, Double>() {
@Override
public int getIndex() {
@@ -366,6 +367,7 @@
return vf.createLiteral(state.getState(u).getValue());
}
+
});
return tmp;
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-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/analytics/SSSP.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -25,6 +25,11 @@
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+import sun.reflect.generics.reflectiveObjects.NotImplementedException;
+
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IVariable;
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -441,7 +446,7 @@
final List<IBinder<SSSP.VS, SSSP.ES, Integer>> tmp = super
.getBinderList();
- tmp.add(new IBinder<SSSP.VS, SSSP.ES, Integer>() {
+ tmp.add(new BinderBase<SSSP.VS, SSSP.ES, Integer>() {
@Override
public int getIndex() {
@@ -456,9 +461,10 @@
return vf.createLiteral(state.getState(u).dist());
}
+
});
- tmp.add(new IBinder<SSSP.VS, SSSP.ES, Integer>() {
+ tmp.add(new BinderBase<SSSP.VS, SSSP.ES, Integer>() {
@Override
public int getIndex() {
@@ -472,6 +478,7 @@
return state.getState(u).predecessor.get();
}
+
});
return tmp;
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/BaseGASProgram.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/BaseGASProgram.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/BaseGASProgram.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -26,6 +26,8 @@
import org.openrdf.model.Value;
import org.openrdf.model.ValueFactory;
+
+import com.bigdata.rdf.graph.BinderBase;
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.Factory;
import com.bigdata.rdf.graph.FrontierEnum;
@@ -237,7 +239,7 @@
final List<IBinder<VS, ES, ST>> tmp = new LinkedList<IBinder<VS, ES, ST>>();
- tmp.add(new IBinder<VS, ES, ST>() {
+ tmp.add(new BinderBase<VS, ES, ST>() {
@Override
public int getIndex() {
Modified: branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java
===================================================================
--- branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java 2014-04-04 19:56:42 UTC (rev 8055)
@@ -30,6 +30,7 @@
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
+import java.util.ListIterator;
import java.util.Set;
import org.apache.log4j.Logger;
@@ -995,8 +996,10 @@
@Override
public void visit(final IGASState<VS, ES, ST> state, final Value u) {
- final IBindingSet bs = new ListBindingSet();
+ final List<IBindingSet> bSets = new LinkedList<IBindingSet>();
+ bSets.add(new ListBindingSet());
+
for (IBinder<VS, ES, ST> b : binderList) {
// The variable for this binder.
@@ -1004,65 +1007,118 @@
if(var == null)
continue;
-
- /*
- * TODO This does too much work. The API is defined in terms
- * of openrdf Value objects rather than IVs because it is in
- * a different package (not bigdata specific). The
- * getBinderList() method should be moved to the code that
- * exposes the service (this class) so it can do bigdata
- * specific things and DO LESS WORK. This would be a good
- * thing to do at the time that we add support for FuzzySSSP
- * (which is not an IGASProgram and hence breaks the model
- * anyway).
- */
- final Value val = b.bind(vf, state, u);
- if (val == null)
- continue;
+ final Iterator<IBindingSet> it = bSets.iterator();
+
+ final List<IBindingSet> bSets2 = new LinkedList<IBindingSet>();
+
+ while (it.hasNext()) {
+
+ final IBindingSet parent = it.next();
+
+ if (log.isTraceEnabled())
+ log.trace("parent: " + parent);
+
+ final List<Value> vals =
+ b.bind(vf, state, u, outVars, parent);
+
+ if (vals.size() == 0) {
+
+ // do nothing, leave the parent in the bSets
+
+ } else if (vals.size() == 1) {
+
+ /*
+ * Bind the single value, leave the parent in the
+ * bSets.
+ */
+
+ final Value val = vals.get(0);
+
+ bind(var, val, parent);
+
+ if (log.isTraceEnabled())
+ log.trace("parent (after bind): " + parent);
+
+ } else {
+
+ /*
+ * Remove the parent from the bSets, for each new
+ * value, clone the parent, bind the value, and add
+ * the new solution to the bSets
+ */
+
+ for (Value val : vals) {
+
+ final IBindingSet child = parent.clone();
+
+ bind(var, val, child);
+
+ if (log.isTraceEnabled())
+ log.trace("child: " + child);
+
+ bSets2.add(child);
+
+ }
+
+ it.remove();
+
+ }
+
+ }
- if (val instanceof IV) {
+ bSets.addAll(bSets2);
+
+ }
- // The value is already an IV.
- bs.set(var, new Constant((IV) val));
+ // Add to the set of generated solutions.
+ tmp.addAll(bSets);
- } else {
+ }
- /*
- * The Value is a BigdataValueImpl (if the bind() method
- * used the supplied ValueFactory). We need to convert
- * it to an IV and this code ASSUMES that we can do this
- * using an inline IV with the as configured KB. (This
- * will work for anything numeric, but not for strings.)
- */
- final IV<BigdataValueImpl, ?> iv = lex
- .getLexiconConfiguration().createInlineIV(val);
+ @SuppressWarnings({ "unchecked", "rawtypes" })
+ protected void bind(final IVariable<?> var, final Value val, final IBindingSet bs) {
+
+ if (val == null)
+ return;
- if (iv != null) {
+ if (val instanceof IV) {
- iv.setValue((BigdataValueImpl) val);
+ // The value is already an IV.
+ bs.set(var, new Constant((IV) val));
- bs.set(var, new Constant(iv));
-
- } else if (val instanceof BigdataValue) {
-
- bs.set(var, new Constant(DummyConstantNode.toDummyIV((BigdataValue) val)));
-
- } else {
-
- throw new RuntimeException("FIXME");
-
- }
+ } else {
+ /*
+ * The Value is a BigdataValueImpl (if the bind() method
+ * used the supplied ValueFactory). We need to convert
+ * it to an IV and this code ASSUMES that we can do this
+ * using an inline IV with the as configured KB. (This
+ * will work for anything numeric, but not for strings.)
+ */
+ final IV<BigdataValueImpl, ?> iv = lex
+ .getLexiconConfiguration().createInlineIV(val);
+
+ if (iv != null) {
+
+ iv.setValue((BigdataValueImpl) val);
+
+ bs.set(var, new Constant(iv));
+
+ } else if (val instanceof BigdataValue) {
+
+ bs.set(var, new Constant(DummyConstantNode.toDummyIV((BigdataValue) val)));
+
+ } else {
+
+ throw new RuntimeException("FIXME");
+
}
}
- // Add to the set of generated solutions.
- tmp.add(bs);
-
}
-
+
@Override
public IBindingSet[] get() {
Modified: branches/RDR/bigdata-sails/src/test/com/bigdata/rdf/sail/graph/paths4.rq
===================================================================
--- branches/RDR/bigdata-sails/src/test/com/bigdata/rdf/sail/graph/paths4.rq 2014-04-04 17:15:05 UTC (rev 8054)
+++ branches/RDR/bigdata-sails/src/test/com/bigdata/rdf/sail/graph/paths4.rq 2014-04-04 19:56:42 UTC (rev 8055)
@@ -4,7 +4,7 @@
gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.PATHS" .
gas:program gas:in </:target> . # starting point
gas:program gas:target </:source1> . # target vertices
- gas:program gas:target </:source2> . # target vertices
+ # gas:program gas:target </:source2> . # target vertices
gas:program gas:traversalDirection "Reverse" .
# gas:program gas:maxIterations 2 .
gas:program gas:maxIterationsAfterTargets 0 .
@@ -12,7 +12,9 @@
gas:program gas:maxVisited 100000 .
gas:program gas:out ?s . # bound to the visited vertices.
gas:program gas:out1 ?depth . # bound to the depth
+ gas:program gas:out2 ?o . # bound to the pred
+ gas:program gas:out3 ?p . # bound to the edge
}
- ?s </:edge> ?o .
- filter(?s != </:target>) .
+ #?s </:edge> ?o .
+ #filter(?s != </:target>) .
} order by ?depth
\ No newline at end of file
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
