bigdata-commit Mailing List for Blazegraph (powered by bigdata) (Page 31)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

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.





2010	Jan	Feb	Mar	Apr	May	Jun	Jul (139)	Aug (94)	Sep (232)	Oct (143)	Nov (138)	Dec (55)
2011	Jan (127)	Feb (90)	Mar (101)	Apr (74)	May (148)	Jun (241)	Jul (169)	Aug (121)	Sep (157)	Oct (199)	Nov (281)	Dec (75)
2012	Jan (107)	Feb (122)	Mar (184)	Apr (73)	May (14)	Jun (49)	Jul (26)	Aug (103)	Sep (133)	Oct (61)	Nov (51)	Dec (55)
2013	Jan (59)	Feb (72)	Mar (99)	Apr (62)	May (92)	Jun (19)	Jul (31)	Aug (138)	Sep (47)	Oct (83)	Nov (95)	Dec (111)
2014	Jan (125)	Feb (60)	Mar (119)	Apr (136)	May (270)	Jun (83)	Jul (88)	Aug (30)	Sep (47)	Oct (27)	Nov (23)	Dec
2015	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep (3)	Oct	Nov	Dec
2016	Jan	Feb	Mar (4)	Apr (1)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec

bigdata-commit Mailing List for Blazegraph (powered by bigdata) (Page 31)

Fast, scalable, robust graph database platform

bigdata-commit — Commit traffic.