Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[7982] branches/RDR
|
From: <tho...@us...> - 2014-03-15 14:00:41
|
Revision: 7982
http://sourceforge.net/p/bigdata/code/7982
Author: thompsonbry
Date: 2014-03-15 14:00:37 +0000 (Sat, 15 Mar 2014)
Log Message:
-----------
Replaced the concept of directedTraversal:boolean with the more general concept of TraversalDirection. The TraversalDirection is a type safe enum with three possible values Forward, Reverse, and Undirected. This generalizes the concept of directed versus undirected traversal and adds support for reverse traversal.
Added a unit test for this.
Updated the wiki page to reflect the changed API.
Modified Paths:
--------------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java
branches/RDR/bigdata-gas/src/test/com/bigdata/rdf/graph/analytics/TestBFS.java
branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java
Added Paths:
-----------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/TraversalDirectionEnum.java
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java 2014-03-15 13:31:34 UTC (rev 7981)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java 2014-03-15 14:00:37 UTC (rev 7982)
@@ -67,20 +67,22 @@
IGraphAccessor getGraphAccessor();
/**
- * Specify whether the visited edges of the graph are to be interpreted as
- * directed or undirected (default <code>directed</code>).
+ * Specify the traversal direction for the {@link IGASProgram}.
* <p>
* The value specified here is used to determine how the {@link EdgesEnum}
- * will be interpreted for the GATHER and SCATTER phases. See
- * {@link EdgesEnum#asUndirectedTraversal()}.
+ * will be interpreted for the GATHER and SCATTER phases. The default is
+ * {@link TraversalDirectionEnum#Forward}.
+ *
+ * @see TraversalDirectionEnum#asTraversed(EdgesEnum)
+ * @see EdgesEnum#asUndirectedTraversal()
*/
- void setDirectedTraversal(boolean newVal);
+ void setTraversalDirection(TraversalDirectionEnum newVal);
/**
- * Return <code>true</code> if the graph should be interpreted as a directed
- * graph.
+ * Return a type safe value indicating the traversal direction for the
+ * {@link IGASProgram}.
*/
- boolean isDirectedTraversal();
+ TraversalDirectionEnum getTraversalDirection();
/**
* Specify the maximum number of iterations for the algorithm. A value of
Added: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/TraversalDirectionEnum.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/TraversalDirectionEnum.java (rev 0)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/TraversalDirectionEnum.java 2014-03-15 14:00:37 UTC (rev 7982)
@@ -0,0 +1,76 @@
+/**
+ 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;
+
+/**
+ * Typesafe enumeration of manner in which an RDF graph will be traversed by an
+ * {@link IGASProgram} based on its {@link EdgesEnum}.
+ *
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
+ */
+public enum TraversalDirectionEnum {
+
+ /**
+ * Directed traversal along the natural direction of the RDF statements
+ * (from Subject to Object).
+ */
+ Forward,
+ /**
+ * Directed traversal along the reverse direction of the RDF statements
+ * (from Object to Subject).
+ */
+ Reverse,
+ /**
+ * Undirected traversal - edges are explored in both the {@link #Forward}
+ * and the {@link #Reverse} direction.
+ */
+ Undirected;
+
+ /**
+ * Interpret the given {@link EdgesEnum}, returning the effective value
+ * required to impose the semantics of this {@link TraversalDirectionEnum}.
+ *
+ * @param edges
+ * The {@link EdgesEnum}.
+ *
+ * @return The effective {@link EdgesEnum} value that will impose the
+ * traversal semantics of this {@link TraversalDirectionEnum}.
+ *
+ * @see EdgesEnum#asUndirectedTraversal()
+ */
+ public EdgesEnum asTraversed(final EdgesEnum edges) {
+
+ switch (this) {
+ case Forward:
+ return edges;
+ case Reverse:
+ switch (edges) {
+ case InEdges:
+ return EdgesEnum.OutEdges;
+ case OutEdges:
+ return EdgesEnum.InEdges;
+ default:
+ return edges;
+ }
+ case Undirected:
+ return edges.asUndirectedTraversal();
+ default:
+ throw new AssertionError();
+ }
+
+ }
+
+}
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java 2014-03-15 13:31:34 UTC (rev 7981)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java 2014-03-15 14:00:37 UTC (rev 7982)
@@ -19,7 +19,6 @@
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeUnit;
-import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
@@ -37,6 +36,7 @@
import com.bigdata.rdf.graph.IGraphAccessor;
import com.bigdata.rdf.graph.IReducer;
import com.bigdata.rdf.graph.IStaticFrontier;
+import com.bigdata.rdf.graph.TraversalDirectionEnum;
import com.bigdata.rdf.graph.util.GASUtil;
import cutthecrap.utils.striterators.Filter;
@@ -65,9 +65,10 @@
/**
* Whether or not the edges of the graph will be traversed with directed
- * graph semantics (default is TRUE).
+ * graph semantics (default is {@link TraversalDirectionEnum#Forward}).
*/
- private final AtomicBoolean directedGraph = new AtomicBoolean(true);
+ private final AtomicReference<TraversalDirectionEnum> traversalDirection = new AtomicReference<TraversalDirectionEnum>(
+ TraversalDirectionEnum.Forward);
/**
* The maximum number of iterations (defaults to {@link Integer#MAX_VALUE}).
@@ -258,12 +259,10 @@
* APPLY is done before the SCATTER - this would not work if we pushed
* down the APPLY into the SCATTER).
*/
- final EdgesEnum gatherEdges = isDirectedTraversal() ? program
- .getGatherEdges() : program.getGatherEdges()
- .asUndirectedTraversal();
- final EdgesEnum scatterEdges = isDirectedTraversal() ? program
- .getScatterEdges() : program.getScatterEdges()
- .asUndirectedTraversal();
+ final EdgesEnum gatherEdges = getTraversalDirection().asTraversed(
+ program.getGatherEdges());
+ final EdgesEnum scatterEdges = getTraversalDirection().asTraversed(
+ program.getScatterEdges());
final boolean pushDownApplyInGather;
final boolean pushDownApplyInScatter;
final boolean runApplyStage;
@@ -816,17 +815,20 @@
}
@Override
- public boolean isDirectedTraversal() {
-
- return directedGraph.get();
-
+ public TraversalDirectionEnum getTraversalDirection() {
+
+ return traversalDirection.get();
+
}
-
+
@Override
- public void setDirectedTraversal(final boolean newVal) {
+ public void setTraversalDirection(final TraversalDirectionEnum newVal) {
- directedGraph.set(newVal);
-
+ if (newVal == null)
+ throw new IllegalArgumentException();
+
+ traversalDirection.set(newVal);
+
}
@Override
Modified: branches/RDR/bigdata-gas/src/test/com/bigdata/rdf/graph/analytics/TestBFS.java
===================================================================
--- branches/RDR/bigdata-gas/src/test/com/bigdata/rdf/graph/analytics/TestBFS.java 2014-03-15 13:31:34 UTC (rev 7981)
+++ branches/RDR/bigdata-gas/src/test/com/bigdata/rdf/graph/analytics/TestBFS.java 2014-03-15 14:00:37 UTC (rev 7982)
@@ -21,6 +21,7 @@
import com.bigdata.rdf.graph.IGASEngine;
import com.bigdata.rdf.graph.IGASState;
import com.bigdata.rdf.graph.IGraphAccessor;
+import com.bigdata.rdf.graph.TraversalDirectionEnum;
import com.bigdata.rdf.graph.impl.sail.AbstractSailGraphTestCase;
/**
@@ -104,11 +105,11 @@
/**
* Variant test in which we choose a vertex (<code>foaf:person</code>) in
- * the middle of the graph and insist on directed edges. Since the edges
- * point from the person to the <code>foaf:person</code> vertex, this BSF
- * traversal does not discover any connected vertices.
+ * the middle of the graph and insist on forward directed edges. Since the
+ * edges point from the person to the <code>foaf:person</code> vertex, this
+ * BSF traversal does not discover any connected vertices.
*/
- public void testBFS_directed() throws Exception {
+ public void testBFS_directed_forward() throws Exception {
final SmallGraphProblem p = setupSmallGraphProblem();
@@ -135,7 +136,8 @@
gasState.setFrontier(gasContext, p.getFoafPerson());
// directed traversal.
- gasContext.setDirectedTraversal(true);
+ gasContext
+ .setTraversalDirection(TraversalDirectionEnum.Forward);
// Converge.
gasContext.call();
@@ -177,6 +179,83 @@
/**
* Variant test in which we choose a vertex (<code>foaf:person</code>) in
+ * the middle of the graph and insist on reverse directed edges. Since the
+ * edges point from the person to the <code>foaf:person</code> vertex,
+ * forward BSF traversal does not discover any connected vertices. However,
+ * since the traversal direction is reversed, the vertices are all one hop
+ * away.
+ */
+ public void testBFS_directed_reverse() throws Exception {
+
+ final SmallGraphProblem p = setupSmallGraphProblem();
+
+ final IGASEngine gasEngine = getGraphFixture()
+ .newGASEngine(1/* nthreads */);
+
+ try {
+
+ final SailConnection cxn = getGraphFixture().getSail()
+ .getConnection();
+
+ try {
+
+ final IGraphAccessor graphAccessor = getGraphFixture()
+ .newGraphAccessor(cxn);
+
+ final IGASContext<BFS.VS, BFS.ES, Void> gasContext = gasEngine
+ .newGASContext(graphAccessor, new BFS());
+
+ final IGASState<BFS.VS, BFS.ES, Void> gasState = gasContext
+ .getGASState();
+
+ // Initialize the froniter.
+ gasState.setFrontier(gasContext, p.getFoafPerson());
+
+ // directed traversal.
+ gasContext
+ .setTraversalDirection(TraversalDirectionEnum.Reverse);
+
+ // Converge.
+ gasContext.call();
+
+ // starting vertex at (0,null).
+ assertEquals(0, gasState.getState(p.getFoafPerson()).depth());
+ assertEquals(null, gasState.getState(p.getFoafPerson())
+ .predecessor());
+
+ // All other vertices are 1-hop.
+ assertEquals(1, gasState.getState(p.getMike()).depth());
+ assertEquals(p.getFoafPerson(), gasState.getState(p.getMike())
+ .predecessor());
+
+ assertEquals(1, gasState.getState(p.getBryan()).depth());
+ assertEquals(p.getFoafPerson(), gasState.getState(p.getBryan())
+ .predecessor());
+
+ assertEquals(1, gasState.getState(p.getMartyn()).depth());
+ assertEquals(p.getFoafPerson(), gasState
+ .getState(p.getMartyn()).predecessor());
+
+ } finally {
+
+ try {
+ cxn.rollback();
+ } finally {
+ cxn.close();
+ }
+
+ }
+
+ } finally {
+
+ gasEngine.shutdownNow();
+
+ }
+
+ }
+
+ /**
+ * Variant test in which we choose a vertex (<code>foaf:person</code>) in
* the middle of the graph and insist on directed edges. Since the edges
* point from the person to the <code>foaf:person</code> vertex, this BSF
* traversal does not discover any connected vertices.
@@ -208,8 +287,9 @@
gasState.setFrontier(gasContext, p.getFoafPerson());
// undirected traversal.
- gasContext.setDirectedTraversal(false);
-
+ gasContext
+ .setTraversalDirection(TraversalDirectionEnum.Undirected);
+
// Converge.
gasContext.call();
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-03-15 13:31:34 UTC (rev 7981)
+++ branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java 2014-03-15 14:00:37 UTC (rev 7982)
@@ -55,6 +55,7 @@
import com.bigdata.rdf.graph.IGraphAccessor;
import com.bigdata.rdf.graph.IPredecessor;
import com.bigdata.rdf.graph.IReducer;
+import com.bigdata.rdf.graph.TraversalDirectionEnum;
import com.bigdata.rdf.graph.analytics.CC;
import com.bigdata.rdf.graph.analytics.PR;
import com.bigdata.rdf.graph.impl.GASEngine;
@@ -167,14 +168,19 @@
int DEFAULT_NTHREADS = 4;
/**
- * This option determines whether the traversal of the graph will
- * interpret the edges as directed or undirected.
+ * This option determines the traversal direction semantics for the
+ * {@link IGASProgram} against the graph, including whether the the
+ * edges of the graph will be interpreted as directed (
+ * {@link TraversalDirectionEnum#Forward} (which is the default),
+ * {@link TraversalDirectionEnum#Reverse}), or
+ * {@link TraversalDirectionEnum#Undirected}.
*
- * @see IGASContext#setDirectedTraversal(boolean)
+ * @see TraversalDirectionEnum
+ * @see IGASContext#setTraversalDirection(TraversalDirectionEnum)
*/
- URI DIRECTED_TRAVERSAL = new URIImpl(NAMESPACE + "directedTraversal");
+ URI TRAVERSAL_DIRECTION = new URIImpl(NAMESPACE + "traversalDirection");
- boolean DEFAULT_DIRECTED_TRAVERSAL = true;
+ TraversalDirectionEnum DEFAULT_DIRECTED_TRAVERSAL = TraversalDirectionEnum.Forward;
/**
* The maximum #of iterations for the GAS program (optional, default
@@ -398,7 +404,7 @@
// options extracted from the SERVICE's graph pattern.
private final int nthreads;
- private final boolean directedTraversal;
+ private final TraversalDirectionEnum traversalDirection;
private final int maxIterations;
private final int maxVisited;
private final URI linkType, linkAttrType;
@@ -433,10 +439,13 @@
store.getValueFactory().createLiteral(
Options.DEFAULT_NTHREADS))).intValue();
- this.directedTraversal = ((Literal) getOnlyArg(Options.PROGRAM,
- Options.DIRECTED_TRAVERSAL, store.getValueFactory()
- .createLiteral(Options.DEFAULT_DIRECTED_TRAVERSAL)))
- .booleanValue();
+ this.traversalDirection = TraversalDirectionEnum
+ .valueOf(((Literal) getOnlyArg(
+ Options.PROGRAM,
+ Options.TRAVERSAL_DIRECTION,
+ store.getValueFactory().createLiteral(
+ Options.DEFAULT_DIRECTED_TRAVERSAL.name())))
+ .stringValue());
this.maxIterations = ((Literal) getOnlyArg(Options.PROGRAM,
Options.MAX_ITERATIONS, store.getValueFactory()
@@ -761,7 +770,7 @@
final IGASContext<VS, ES, ST> gasContext = gasEngine.newGASContext(
graphAccessor, gasProgram);
- gasContext.setDirectedTraversal(directedTraversal);
+ gasContext.setTraversalDirection(traversalDirection);
gasContext.setMaxIterations(maxIterations);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
