You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2015/06/24 20:43:10 UTC
incubator-tinkerpop git commit: added dedup('a',
'b') which currently only works with MatchStep. However,
will generalize to work on paths and maps -- scoping stlye. This allows us to
dedup patterns in MatchStep and thus, greatly reduce the search space i
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/master f384fa468 -> b2875c85c
added dedup('a','b') which currently only works with MatchStep. However, will generalize to work on paths and maps -- scoping stlye. This allows us to dedup patterns in MatchStep and thus, greatly reduce the search space if someone knows they don't want duplicates.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/b2875c85
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/b2875c85
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/b2875c85
Branch: refs/heads/master
Commit: b2875c85c074174280413389d3c0168bcfd51294
Parents: f384fa4
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Wed Jun 24 12:43:04 2015 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Wed Jun 24 12:43:04 2015 -0600
----------------------------------------------------------------------
.../traversal/dsl/graph/GraphTraversal.java | 5 +
.../gremlin/process/traversal/dsl/graph/__.java | 4 +
.../process/traversal/step/map/MatchStep.java | 117 +++++++++++++------
.../traversal/step/map/GroovyMatchTest.groovy | 17 ++-
.../process/traversal/step/map/MatchTest.java | 18 +++
5 files changed, 122 insertions(+), 39 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/b2875c85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
index 4e3416d..89676fd 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java
@@ -660,6 +660,11 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> {
return this.asAdmin().addStep(scope.equals(Scope.global) ? new DedupGlobalStep<>(this.asAdmin()) : new DedupLocalStep(this.asAdmin()));
}
+ public default GraphTraversal<S, E> dedup(final String label, final String... labels) {
+ ((MatchStep<?, ?>) this.asAdmin().getEndStep()).setDedupLabels(label, labels);
+ return this;
+ }
+
public default GraphTraversal<S, E> where(final Scope scope, final String startKey, final P<String> predicate) {
return this.asAdmin().addStep(new WherePredicateStep<>(this.asAdmin(), scope, Optional.ofNullable(startKey), predicate));
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/b2875c85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
index bc13fae..e81fc52 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/__.java
@@ -511,6 +511,10 @@ public class __ {
return __.<A>start().dedup();
}
+ public static <A> GraphTraversal<A, A> dedup(final String label, final String... labels) {
+ return __.<A>start().dedup(label, labels);
+ }
+
public static <A> GraphTraversal<A, A> dedup(final Scope scope) {
return __.<A>start().dedup(scope);
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/b2875c85/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
index e915b51..07770cf 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
@@ -78,6 +78,9 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
private MatchAlgorithm matchAlgorithm;
private Class<? extends MatchAlgorithm> matchAlgorithmClass = CountMatchAlgorithm.class; // default is CountMatchAlgorithm (use MatchAlgorithmStrategy to change)
+ private Set<List<Object>> dedups = null;
+ private List<String> dedupLabels = null;
+
public MatchStep(final Traversal.Admin traversal, final String startKey, final ConjunctionStep.Conjunction conjunction, final Traversal... matchTraversals) {
super(traversal);
this.conjunction = conjunction;
@@ -238,10 +241,32 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
for (final Traversal.Admin<Object, Object> traversal : this.matchTraversals) {
clone.matchTraversals.add(clone.integrateChild(traversal.clone()));
}
+ if (this.dedups != null) clone.dedups = new HashSet<>();
clone.initializeMatchAlgorithm();
return clone;
}
+ public void setDedupLabels(final String label, final String... labels) {
+ this.dedups = new HashSet<>();
+ this.dedupLabels = new ArrayList<>(labels.length + 1);
+ this.dedupLabels.add(label);
+ Collections.addAll(this.dedupLabels, labels);
+ }
+
+ private boolean isDuplicate(final Traverser<S> traverser) {
+ if (null == this.dedups)
+ return false;
+ for (final String key : this.dedupLabels) {
+ if (!traverser.path().hasLabel(key))
+ return false;
+ }
+ final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
+ for (final String key : this.dedupLabels) {
+ objects.add(traverser.path().get(Pop.last, key));
+ }
+ return this.dedups.contains(objects);
+ }
+
private boolean hasMatched(final ConjunctionStep.Conjunction conjunction, final Traverser<S> traverser) {
final Path path = traverser.path();
int counter = 0;
@@ -251,17 +276,34 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
counter++;
}
}
- return this.matchTraversals.size() == counter;
+ boolean matched = this.matchTraversals.size() == counter;
+ if (matched && this.dedupLabels != null) {
+ final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
+ for (final String key : this.dedupLabels) {
+ objects.add(traverser.path().get(Pop.last, key));
+ }
+ this.dedups.add(objects);
+ }
+ return matched;
}
private Map<String, E> getBindings(final Traverser<S> traverser) {
final Map<String, E> bindings = new HashMap<>();
- traverser.path().forEach((object, labels) -> {
- for (final String label : labels) {
- if (this.matchStartLabels.contains(label) || this.matchEndLabels.contains(label))
- bindings.put(label, (E) object);
- }
- });
+ if (null == this.dedupLabels) {
+ traverser.path().forEach((object, labels) -> {
+ for (final String label : labels) {
+ if (this.matchStartLabels.contains(label) || this.matchEndLabels.contains(label))
+ bindings.put(label, (E) object);
+ }
+ });
+ } else {
+ traverser.path().forEach((object, labels) -> {
+ for (final String label : labels) {
+ if (this.dedupLabels.contains(label))
+ bindings.put(label, (E) object);
+ }
+ });
+ }
return bindings;
}
@@ -292,14 +334,18 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
if (null == traverser) {
traverser = this.starts.next();
traverser.path().addLabel(this.getId()); // so the traverser never returns to this branch ever again
- } else if (hasMatched(this.conjunction, traverser))
- return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));
+ }
- if (this.conjunction == ConjunctionStep.Conjunction.AND) {
- this.getMatchAlgorithm().apply(traverser).addStart(traverser); // determine which sub-pattern the traverser should try next
- } else { // OR
- for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) {
- matchTraversal.addStart(traverser.split());
+ if (!this.isDuplicate(traverser)) {
+ if (hasMatched(this.conjunction, traverser))
+ return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));
+
+ if (this.conjunction == ConjunctionStep.Conjunction.AND) {
+ this.getMatchAlgorithm().apply(traverser).addStart(traverser); // determine which sub-pattern the traverser should try next
+ } else { // OR
+ for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) {
+ matchTraversal.addStart(traverser.split());
+ }
}
}
}
@@ -307,25 +353,30 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
@Override
protected Iterator<Traverser<Map<String, E>>> computerAlgorithm() throws NoSuchElementException {
- final Traverser.Admin traverser = this.starts.next();
- if (!traverser.path().hasLabel(this.getId()))
- traverser.path().addLabel(this.getId()); // so the traverser never returns to this branch ever again
- if (hasMatched(this.conjunction, traverser)) {
- traverser.setStepId(this.getNextStep().getId());
- return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));
- }
- if (this.conjunction == ConjunctionStep.Conjunction.AND) {
- final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser); // determine which sub-pattern the traverser should try next
- traverser.setStepId(matchTraversal.getStartStep().getId()); // go down the traversal match sub-pattern
- return IteratorUtils.of(traverser);
- } else { // OR
- final List<Traverser<Map<String, E>>> traversers = new ArrayList<>(this.matchTraversals.size());
- this.matchTraversals.forEach(matchTraversal -> {
- final Traverser.Admin split = traverser.split();
- split.setStepId(matchTraversal.getStartStep().getId());
- traversers.add(split);
- });
- return traversers.iterator();
+ while (true) {
+ final Traverser.Admin traverser = this.starts.next();
+ if (!traverser.path().hasLabel(this.getId()))
+ traverser.path().addLabel(this.getId()); // so the traverser never returns to this branch ever again
+
+ if (!this.isDuplicate(traverser)) {
+ if (hasMatched(this.conjunction, traverser)) {
+ traverser.setStepId(this.getNextStep().getId());
+ return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));
+ }
+ if (this.conjunction == ConjunctionStep.Conjunction.AND) {
+ final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser); // determine which sub-pattern the traverser should try next
+ traverser.setStepId(matchTraversal.getStartStep().getId()); // go down the traversal match sub-pattern
+ return IteratorUtils.of(traverser);
+ } else { // OR
+ final List<Traverser<Map<String, E>>> traversers = new ArrayList<>(this.matchTraversals.size());
+ this.matchTraversals.forEach(matchTraversal -> {
+ final Traverser.Admin split = traverser.split();
+ split.setStepId(matchTraversal.getStartStep().getId());
+ traversers.add(split);
+ });
+ return traversers.iterator();
+ }
+ }
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/b2875c85/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
----------------------------------------------------------------------
diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
index 51e2e65..d4c6da0 100644
--- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
+++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
@@ -24,10 +24,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalScriptHelper
import org.apache.tinkerpop.gremlin.structure.Vertex
import org.junit.Before
-import static org.apache.tinkerpop.gremlin.process.traversal.P.eq
-import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.and
-import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where
-
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
@@ -305,7 +301,7 @@ public abstract class GroovyMatchTest {
g.V.match('a',
__.as('a').out.as('b'),
__.not(__.as('a').out('created').as('b')));
- """,g)
+ """, g)
}
@Override
@@ -317,7 +313,16 @@ public abstract class GroovyMatchTest {
__.as('b').in('created').count.is(eq(3)))),
__.as('a').both.as('b'),
where(__.as('b').in()));
- """,g)
+ """, g)
+ }
+
+ @Override
+ public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa__a_both_b__b_both_cX_dedupXa_bX() {
+ TraversalScriptHelper.compute("""
+ g.V.match('a',
+ __.as('a').both.as('b'),
+ __.as('b').both.as('c')).dedup('a','b')
+ """, g)
}
}
}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/b2875c85/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
index 9fe3876..989c855 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
@@ -125,6 +125,9 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
// uses 'out of order' conjunction nested where()
public abstract Traversal<Vertex, Map<String, Object>> get_g_V_matchXa__whereXandXa_created_b__b_0created_count_isXeqX3XXXX__a_both_b__whereXb_inXX();
+ // testing distinct key values
+ public abstract Traversal<Vertex, Map<String, Object>> get_g_V_matchXa__a_both_b__b_both_cX_dedupXa_bX();
+
@Test
@LoadGraphWith(MODERN)
public void g_V_matchXa_out_bX() throws Exception {
@@ -410,6 +413,14 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
"a", convertToVertex(graph, "peter"), "b", convertToVertex(graph, "lop")), traversal);
}
+ @Test
+ @LoadGraphWith(MODERN)
+ public void g_V_matchXa__a_both_b__b_both_cX_dedupXa_bX() {
+ final Traversal<Vertex, Map<String, Object>> traversal = get_g_V_matchXa__a_both_b__b_both_cX_dedupXa_bX();
+ printTraversalForm(traversal);
+ assertEquals(12, traversal.toList().size());
+ }
+
public static class GreedyMatchTraversals extends Traversals {
@Before
public void setupTest() {
@@ -647,5 +658,12 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
as("a").both().as("b"),
where(as("b").in()));
}
+
+ @Override
+ public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa__a_both_b__b_both_cX_dedupXa_bX() {
+ return g.V().match("a",
+ as("a").both().as("b"),
+ as("b").both().as("c")).dedup("a", "b");
+ }
}
}