This is an automated email from the ASF dual-hosted git repository.
jin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph.git
The following commit(s) were added to refs/heads/master by this push:
new 8e99d85d3 feat(api-core): support label & property filtering for both
edge and vertex & support kout dfs mode (#2295)
8e99d85d3 is described below
commit 8e99d85d33e23a7837a9963e3233f43e7bc31e68
Author: Wu Chencan <[email protected]>
AuthorDate: Sun Sep 10 16:47:45 2023 +0800
feat(api-core): support label & property filtering for both edge and vertex
& support kout dfs mode (#2295)
- Support label & property filtering for both edge and vertex and the
filtering is implemented in Kout Post and Kneighbor - Post Apis, reducing
unnecessary graph searches through pruning
- Support Kout dfs mode in Kout Post Api
Originally only edge label filtering was supported, now label and property
filtering for edge and vertex is supported.
- add classes VEStepEntity and VEStep to support serialization in request
- add class Steps to support filtering of edge and vertex in runtime(core)
- add new method edgesOfVertex(Id source, Steps steps) to support label and
property filtering for both edge and vertex in HugeTraverser.java
---------
Co-authored-by: imbajin <[email protected]>
---
.../hugegraph/api/traversers/KneighborAPI.java | 20 +--
.../apache/hugegraph/api/traversers/KoutAPI.java | 48 +++--
.../hugegraph/api/traversers/TraverserAPI.java | 60 +++++++
.../org/apache/hugegraph/backend/query/Query.java | 1 +
.../hugegraph/backend/tx/GraphTransaction.java | 55 ++++--
.../traversal/algorithm/HugeTraverser.java | 128 +++++++++++++-
.../traversal/algorithm/KneighborTraverser.java | 6 +-
.../traversal/algorithm/KoutTraverser.java | 40 ++++-
.../algorithm/iterator/NestedIterator.java | 195 +++++++++++++++++++++
.../traversal/algorithm/records/KoutRecords.java | 43 ++++-
.../records/SingleWayMultiPathsRecords.java | 14 +-
.../hugegraph/traversal/algorithm/steps/Steps.java | 187 ++++++++++++++++++++
.../traversal/optimize/TraversalUtil.java | 23 +--
.../hugegraph/api/traversers/KneighborApiTest.java | 22 ++-
.../hugegraph/api/traversers/KoutApiTest.java | 22 ++-
15 files changed, 782 insertions(+), 82 deletions(-)
diff --git
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java
index a0e7d0c4e..8624b2dd0 100644
---
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java
+++
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java
@@ -37,7 +37,7 @@ import org.apache.hugegraph.structure.HugeVertex;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser;
import org.apache.hugegraph.traversal.algorithm.KneighborTraverser;
import org.apache.hugegraph.traversal.algorithm.records.KneighborRecords;
-import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.type.define.Directions;
import org.apache.hugegraph.util.E;
import org.apache.hugegraph.util.Log;
@@ -120,7 +120,7 @@ public class KneighborAPI extends TraverserAPI {
E.checkArgumentNotNull(request, "The request body can't be null");
E.checkArgumentNotNull(request.source,
"The source of request can't be null");
- E.checkArgument(request.step != null,
+ E.checkArgument(request.steps != null,
"The steps of request can't be null");
if (request.countOnly) {
E.checkArgument(!request.withVertex && !request.withPath &&
!request.withEdge,
@@ -128,9 +128,9 @@ public class KneighborAPI extends TraverserAPI {
}
LOG.debug("Graph [{}] get customized kneighbor from source vertex " +
- "'{}', with step '{}', limit '{}', count_only '{}', " +
+ "'{}', with steps '{}', limit '{}', count_only '{}', " +
"with_vertex '{}', with_path '{}' and with_edge '{}'",
- graph, request.source, request.step, request.limit,
+ graph, request.source, request.steps, request.limit,
request.countOnly, request.withVertex, request.withPath,
request.withEdge);
@@ -139,11 +139,11 @@ public class KneighborAPI extends TraverserAPI {
HugeGraph g = graph(manager, graph);
Id sourceId = HugeVertex.getIdValue(request.source);
- EdgeStep step = step(g, request.step);
+ Steps steps = steps(g, request.steps);
KneighborRecords results;
try (KneighborTraverser traverser = new KneighborTraverser(g)) {
- results = traverser.customizedKneighbor(sourceId, step,
+ results = traverser.customizedKneighbor(sourceId, steps,
request.maxDepth,
request.limit);
measure.addIterCount(traverser.vertexIterCounter.get(),
@@ -202,8 +202,8 @@ public class KneighborAPI extends TraverserAPI {
@JsonProperty("source")
public Object source;
- @JsonProperty("step")
- public TraverserAPI.Step step;
+ @JsonProperty("steps")
+ public TraverserAPI.VESteps steps;
@JsonProperty("max_depth")
public int maxDepth;
@JsonProperty("limit")
@@ -219,9 +219,9 @@ public class KneighborAPI extends TraverserAPI {
@Override
public String toString() {
- return String.format("PathRequest{source=%s,step=%s,maxDepth=%s" +
+ return String.format("PathRequest{source=%s,steps=%s,maxDepth=%s" +
"limit=%s,countOnly=%s,withVertex=%s," +
- "withPath=%s,withEdge=%s}", this.source,
this.step,
+ "withPath=%s,withEdge=%s}", this.source,
this.steps,
this.maxDepth, this.limit, this.countOnly,
this.withVertex, this.withPath,
this.withEdge);
}
diff --git
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java
index 1adf2be5e..1f1b6922d 100644
---
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java
+++
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java
@@ -38,7 +38,7 @@ import org.apache.hugegraph.structure.HugeVertex;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser;
import org.apache.hugegraph.traversal.algorithm.KoutTraverser;
import org.apache.hugegraph.traversal.algorithm.records.KoutRecords;
-import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.type.define.Directions;
import org.apache.hugegraph.util.E;
import org.apache.hugegraph.util.Log;
@@ -126,18 +126,19 @@ public class KoutAPI extends TraverserAPI {
E.checkArgumentNotNull(request, "The request body can't be null");
E.checkArgumentNotNull(request.source,
"The source of request can't be null");
- E.checkArgument(request.step != null,
+ E.checkArgument(request.steps != null,
"The steps of request can't be null");
if (request.countOnly) {
E.checkArgument(!request.withVertex && !request.withPath &&
!request.withEdge,
"Can't return vertex, edge or path when count
only");
}
+ HugeTraverser.checkTraverseMode(request.traverseMode);
LOG.debug("Graph [{}] get customized kout from source vertex '{}', " +
- "with step '{}', max_depth '{}', nearest '{}', " +
+ "with steps '{}', max_depth '{}', nearest '{}', " +
"count_only '{}', capacity '{}', limit '{}', " +
"with_vertex '{}', with_path '{}' and with_edge '{}'",
- graph, request.source, request.step, request.maxDepth,
+ graph, request.source, request.steps, request.maxDepth,
request.nearest, request.countOnly, request.capacity,
request.limit, request.withVertex, request.withPath,
request.withEdge);
@@ -147,14 +148,22 @@ public class KoutAPI extends TraverserAPI {
HugeGraph g = graph(manager, graph);
Id sourceId = HugeVertex.getIdValue(request.source);
- EdgeStep step = step(g, request.step);
+ Steps steps = steps(g, request.steps);
KoutRecords results;
try (KoutTraverser traverser = new KoutTraverser(g)) {
- results = traverser.customizedKout(sourceId, step,
- request.maxDepth,
- request.nearest,
- request.capacity,
- request.limit);
+ if (HugeTraverser.isTraverseModeDFS(request.traverseMode)) {
+ results = traverser.dfsKout(sourceId, steps,
+ request.maxDepth,
+ request.nearest,
+ request.capacity,
+ request.limit);
+ } else {
+ results = traverser.customizedKout(sourceId, steps,
+ request.maxDepth,
+ request.nearest,
+ request.capacity,
+ request.limit);
+ }
measure.addIterCount(traverser.vertexIterCounter.get(),
traverser.edgeIterCounter.get());
}
@@ -172,7 +181,7 @@ public class KoutAPI extends TraverserAPI {
if (request.countOnly) {
return manager.serializer(g, measure.measures())
- .writeNodesWithPath("kneighbor", neighbors, size,
paths,
+ .writeNodesWithPath("kout", neighbors, size, paths,
QueryResults.emptyIterator(),
QueryResults.emptyIterator());
}
@@ -210,8 +219,8 @@ public class KoutAPI extends TraverserAPI {
@JsonProperty("source")
public Object source;
- @JsonProperty("step")
- public TraverserAPI.Step step;
+ @JsonProperty("steps")
+ public TraverserAPI.VESteps steps;
@JsonProperty("max_depth")
public int maxDepth;
@JsonProperty("nearest")
@@ -228,16 +237,19 @@ public class KoutAPI extends TraverserAPI {
public boolean withPath = false;
@JsonProperty("with_edge")
public boolean withEdge = false;
+ @JsonProperty("traverse_mode")
+ public String traverseMode = HugeTraverser.TRAVERSE_MODE_BFS;
@Override
public String toString() {
- return String.format("KoutRequest{source=%s,step=%s,maxDepth=%s" +
+ return String.format("KoutRequest{source=%s,steps=%s,maxDepth=%s" +
"nearest=%s,countOnly=%s,capacity=%s," +
"limit=%s,withVertex=%s,withPath=%s," +
- "withEdge=%s}", this.source, this.step,
- this.maxDepth, this.nearest, this.countOnly,
- this.capacity, this.limit, this.withVertex,
- this.withPath, this.withEdge);
+ "withEdge=%s,traverseMode=%s}", this.source,
+ this.steps, this.maxDepth, this.nearest,
+ this.countOnly, this.capacity, this.limit,
+ this.withVertex, this.withPath, this.withEdge,
+ this.traverseMode);
}
}
}
diff --git
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java
index 9649ec03c..cc61a9fad 100644
---
a/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java
+++
b/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java
@@ -19,13 +19,16 @@ package org.apache.hugegraph.api.traversers;
import static
org.apache.hugegraph.traversal.algorithm.HugeTraverser.DEFAULT_MAX_DEGREE;
+import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.hugegraph.HugeGraph;
import org.apache.hugegraph.api.API;
import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.type.define.Directions;
+
import com.fasterxml.jackson.annotation.JsonAlias;
import com.fasterxml.jackson.annotation.JsonProperty;
@@ -36,6 +39,25 @@ public class TraverserAPI extends API {
step.maxDegree, step.skipDegree);
}
+ protected static Steps steps(HugeGraph graph, VESteps steps) {
+ Map<String, Map<String, Object>> vSteps = new HashMap<>();
+ if (steps.vSteps != null) {
+ for (VEStepEntity vStep : steps.vSteps) {
+ vSteps.put(vStep.label, vStep.properties);
+ }
+ }
+
+ Map<String, Map<String, Object>> eSteps = new HashMap<>();
+ if (steps.eSteps != null) {
+ for (VEStepEntity eStep : steps.eSteps) {
+ eSteps.put(eStep.label, eStep.properties);
+ }
+ }
+
+ return new Steps(graph, steps.direction, vSteps, eSteps,
+ steps.maxDegree, steps.skipDegree);
+ }
+
protected static class Step {
@JsonProperty("direction")
@@ -58,4 +80,42 @@ public class TraverserAPI extends API {
this.maxDegree, this.skipDegree);
}
}
+
+ protected static class VEStepEntity {
+
+ @JsonProperty("label")
+ public String label;
+
+ @JsonProperty("properties")
+ public Map<String, Object> properties;
+
+ @Override
+ public String toString() {
+ return String.format("VEStepEntity{label=%s,properties=%s}",
+ this.label, this.properties);
+ }
+ }
+
+ protected static class VESteps {
+
+ @JsonProperty("direction")
+ public Directions direction;
+ @JsonAlias("degree")
+ @JsonProperty("max_degree")
+ public long maxDegree = Long.parseLong(DEFAULT_MAX_DEGREE);
+ @JsonProperty("skip_degree")
+ public long skipDegree = 0L;
+ @JsonProperty("vertex_steps")
+ public List<VEStepEntity> vSteps;
+ @JsonProperty("edge_steps")
+ public List<VEStepEntity> eSteps;
+
+ @Override
+ public String toString() {
+ return String.format("Steps{direction=%s,maxDegree=%s," +
+ "skipDegree=%s,vSteps=%s,eSteps=%s}",
+ this.direction, this.maxDegree,
+ this.skipDegree, this.vSteps, this.eSteps);
+ }
+ }
}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java
index 518ac5303..32f416b37 100644
--- a/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java
+++ b/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java
@@ -306,6 +306,7 @@ public class Query implements Cloneable {
/**
* Set or update the offset and limit by a range [start, end)
* NOTE: it will use the min range one: max start and min end
+ *
* @param start the range start, include it
* @param end the range end, exclude it
*/
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java
index ea1196eae..0574318d7 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java
@@ -690,7 +690,7 @@ public class GraphTransaction extends IndexableTransaction {
// Override vertices in local `addedVertices`
this.addedVertices.remove(vertex.id());
// Force load vertex to ensure all properties are loaded (refer to
#2181)
- if (vertex.schemaLabel().indexLabels().size() > 0) {
+ if (vertex.schemaLabel().indexLabels().size() > 0) {
vertex.forceLoad();
}
// Collect the removed vertex
@@ -937,7 +937,7 @@ public class GraphTransaction extends IndexableTransaction {
* local vertex and duplicated id.
*/
Iterator<HugeEdge> it = this.queryEdgesFromBackend(query);
- @SuppressWarnings({ "unchecked", "rawtypes" })
+ @SuppressWarnings({"unchecked", "rawtypes"})
Iterator<Edge> r = (Iterator) it;
return r;
}
@@ -1195,9 +1195,10 @@ public class GraphTransaction extends
IndexableTransaction {
/**
* Construct one edge condition query based on source vertex, direction and
* edge labels
+ *
* @param sourceVertex source vertex of edge
- * @param direction only be "IN", "OUT" or "BOTH"
- * @param edgeLabels edge labels of queried edges
+ * @param direction only be "IN", "OUT" or "BOTH"
+ * @param edgeLabels edge labels of queried edges
* @return constructed condition query
*/
@Watched
@@ -1230,8 +1231,39 @@ public class GraphTransaction extends
IndexableTransaction {
} else if (edgeLabels.length > 1) {
query.query(Condition.in(HugeKeys.LABEL,
Arrays.asList(edgeLabels)));
+ }
+
+ return query;
+ }
+
+ public static ConditionQuery constructEdgesQuery(Id sourceVertex,
+ Directions direction,
+ List<Id> edgeLabels) {
+ E.checkState(sourceVertex != null,
+ "The edge query must contain source vertex");
+ E.checkState(direction != null,
+ "The edge query must contain direction");
+
+ ConditionQuery query = new ConditionQuery(HugeType.EDGE);
+
+ // Edge source vertex
+ query.eq(HugeKeys.OWNER_VERTEX, sourceVertex);
+
+ // Edge direction
+ if (direction == Directions.BOTH) {
+ query.query(Condition.or(
+ Condition.eq(HugeKeys.DIRECTION, Directions.OUT),
+ Condition.eq(HugeKeys.DIRECTION, Directions.IN)));
} else {
- assert edgeLabels.length == 0;
+ assert direction == Directions.OUT || direction == Directions.IN;
+ query.eq(HugeKeys.DIRECTION, direction);
+ }
+
+ // Edge labels
+ if (edgeLabels.size() == 1) {
+ query.eq(HugeKeys.LABEL, edgeLabels.get(0));
+ } else if (edgeLabels.size() > 1) {
+ query.query(Condition.in(HugeKeys.LABEL, edgeLabels));
}
return query;
@@ -1363,8 +1395,8 @@ public class GraphTransaction extends
IndexableTransaction {
}
boolean supportIn =
this.storeFeatures().supportsQueryWithInCondition();
- for (ConditionQuery cq: ConditionQueryFlatten.flatten(
- (ConditionQuery) query, supportIn)) {
+ for (ConditionQuery cq : ConditionQueryFlatten.flatten(
+ (ConditionQuery) query, supportIn)) {
// Optimize by sysprop
Query q = this.optimizeQuery(cq);
/*
@@ -1387,7 +1419,7 @@ public class GraphTransaction extends
IndexableTransaction {
"Not supported querying by id and conditions: %s",
query);
}
- Id label = (Id) query.condition(HugeKeys.LABEL);
+ Id label = query.condition(HugeKeys.LABEL);
// Optimize vertex query
if (label != null && query.resultType().isVertex()) {
@@ -1580,6 +1612,7 @@ public class GraphTransaction extends
IndexableTransaction {
@SuppressWarnings("unchecked")
Collection<Id> missed = CollectionUtils.subtract(nonNullKeys,
keys);
HugeGraph graph = this.graph();
+
E.checkArgument(false, "All non-null property keys %s of " +
"vertex label '%s' must be set, missed keys %s",
graph.mapPkId2Name(nonNullKeys),
vertexLabel.name(),
@@ -1803,9 +1836,9 @@ public class GraphTransaction extends
IndexableTransaction {
// Filter vertices matched conditions
return q.test(v) ? v : null;
};
- vertices = this.joinTxRecords(query, vertices, matchTxFunc,
- this.addedVertices,
this.removedVertices,
- this.updatedVertices);
+ vertices = this.joinTxRecords(query, vertices, matchTxFunc,
+ this.addedVertices, this.removedVertices,
+ this.updatedVertices);
return vertices;
}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java
index c0d36f31b..f5415d9c5 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java
@@ -17,6 +17,7 @@
package org.apache.hugegraph.traversal.algorithm;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
@@ -48,7 +49,10 @@ import org.apache.hugegraph.iterator.MapperIterator;
import org.apache.hugegraph.perf.PerfUtil.Watched;
import org.apache.hugegraph.schema.SchemaLabel;
import org.apache.hugegraph.structure.HugeEdge;
+import org.apache.hugegraph.structure.HugeVertex;
+import org.apache.hugegraph.traversal.algorithm.iterator.NestedIterator;
import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.traversal.optimize.TraversalUtil;
import org.apache.hugegraph.type.HugeType;
import org.apache.hugegraph.type.define.CollectionType;
@@ -85,6 +89,9 @@ public class HugeTraverser {
// Empirical value of scan limit, with which results can be returned in 3s
public static final String DEFAULT_PAGE_LIMIT = "100000";
public static final long NO_LIMIT = -1L;
+ // traverse mode of kout algorithm: bfs and dfs
+ public static final String TRAVERSE_MODE_BFS = "breadth_first_search";
+ public static final String TRAVERSE_MODE_DFS = "depth_first_search";
protected static final Logger LOG = Log.logger(HugeTraverser.class);
protected static final int MAX_VERTICES = 10;
private static CollectionFactory collectionFactory;
@@ -164,6 +171,17 @@ public class HugeTraverser {
}
}
+ public static void checkTraverseMode(String traverseMode) {
+ E.checkArgument(traverseMode.compareToIgnoreCase(TRAVERSE_MODE_BFS) ==
0 ||
+ traverseMode.compareToIgnoreCase(TRAVERSE_MODE_DFS) ==
0,
+ "The traverse mode must be one of '%s' or '%s', but
got '%s'",
+ TRAVERSE_MODE_BFS, TRAVERSE_MODE_DFS, traverseMode);
+ }
+
+ public static boolean isTraverseModeDFS(String traverseMode) {
+ return traverseMode.compareToIgnoreCase(TRAVERSE_MODE_DFS) == 0;
+ }
+
public static <K, V extends Comparable<? super V>> Map<K, V> topN(
Map<K, V> map,
boolean sorted,
@@ -272,6 +290,15 @@ public class HugeTraverser {
return path;
}
+ public static List<HugeEdge> pathEdges(Iterator<Edge> iterator, HugeEdge
edge) {
+ List<HugeEdge> edges = new ArrayList<>();
+ if (iterator instanceof NestedIterator) {
+ edges = ((NestedIterator) iterator).pathEdges();
+ }
+ edges.add(edge);
+ return edges;
+ }
+
public HugeGraph graph() {
return this.graph;
}
@@ -438,6 +465,93 @@ public class HugeTraverser {
return edgeStep.skipSuperNodeIfNeeded(edges);
}
+ public Iterator<Edge> edgesOfVertex(Id source, Steps steps) {
+ List<Id> edgeLabels = steps.edgeLabels();
+ ConditionQuery cq = GraphTransaction.constructEdgesQuery(
+ source, steps.direction(), edgeLabels);
+ cq.capacity(Query.NO_CAPACITY);
+ if (steps.limit() != NO_LIMIT) {
+ cq.limit(steps.limit());
+ }
+
+ Map<Id, ConditionQuery> edgeConditions =
+ getFilterQueryConditions(steps.edgeSteps(), HugeType.EDGE);
+
+ Iterator<Edge> filteredEdges =
+ new FilterIterator<>(this.graph().edges(cq),
+ edge -> validateEdge(edgeConditions,
(HugeEdge) edge));
+
+ return edgesOfVertexStep(filteredEdges, steps);
+ }
+
+ protected Iterator<Edge> edgesOfVertexStep(Iterator<Edge> edges, Steps
steps) {
+ if (steps.isVertexEmpty()) {
+ return edges;
+ }
+
+ Map<Id, ConditionQuery> vertexConditions =
+ getFilterQueryConditions(steps.vertexSteps(), HugeType.VERTEX);
+
+ return new FilterIterator<>(edges,
+ edge -> validateVertex(vertexConditions,
(HugeEdge) edge));
+ }
+
+ private Boolean validateVertex(Map<Id, ConditionQuery> conditions,
+ HugeEdge edge) {
+ HugeVertex sourceV = edge.sourceVertex();
+ HugeVertex targetV = edge.targetVertex();
+ if (!conditions.containsKey(sourceV.schemaLabel().id()) ||
+ !conditions.containsKey(targetV.schemaLabel().id())) {
+ return false;
+ }
+
+ ConditionQuery cq = conditions.get(sourceV.schemaLabel().id());
+ if (cq != null) {
+ sourceV = (HugeVertex) this.graph.vertex(sourceV.id());
+ if (!cq.test(sourceV)) {
+ return false;
+ }
+ }
+
+ cq = conditions.get(targetV.schemaLabel().id());
+ if (cq != null) {
+ targetV = (HugeVertex) this.graph.vertex(targetV.id());
+ return cq.test(targetV);
+ }
+ return true;
+ }
+
+ private Boolean validateEdge(Map<Id, ConditionQuery> conditions,
+ HugeEdge edge) {
+ if (!conditions.containsKey(edge.schemaLabel().id())) {
+ return false;
+ }
+
+ ConditionQuery cq = conditions.get(edge.schemaLabel().id());
+ if (cq != null) {
+ return cq.test(edge);
+ }
+ return true;
+ }
+
+ private Map<Id, ConditionQuery> getFilterQueryConditions(
+ Map<Id, Steps.StepEntity> idStepEntityMap, HugeType type) {
+ Map<Id, ConditionQuery> conditions = new HashMap<>();
+
+ for (Map.Entry<Id, Steps.StepEntity> entry :
idStepEntityMap.entrySet()) {
+ Steps.StepEntity stepEntity = entry.getValue();
+ if (stepEntity.properties() != null &&
!stepEntity.properties().isEmpty()) {
+ ConditionQuery cq = new ConditionQuery(type);
+ Map<Id, Object> properties = stepEntity.properties();
+ TraversalUtil.fillConditionQuery(cq, properties, this.graph);
+ conditions.put(entry.getKey(), cq);
+ } else {
+ conditions.put(entry.getKey(), null);
+ }
+ }
+ return conditions;
+ }
+
private void fillFilterBySortKeys(Query query, Id[] edgeLabels,
Map<Id, Object> properties) {
if (properties == null || properties.isEmpty()) {
@@ -513,6 +627,19 @@ public class HugeTraverser {
}
}
+ public Iterator<Edge> createNestedIterator(Id sourceV, Steps steps,
+ int depth, Set<Id> visited,
boolean nearest) {
+ E.checkArgument(depth > 0, "The depth should large than 0 for nested
iterator");
+ visited.add(sourceV);
+
+ // build a chained iterator path with length of depth
+ Iterator<Edge> iterator = this.edgesOfVertex(sourceV, steps);
+ for (int i = 1; i < depth; i++) {
+ iterator = new NestedIterator(this, iterator, steps, visited,
nearest);
+ }
+ return iterator;
+ }
+
public static class Node {
private final Id id;
@@ -876,6 +1003,5 @@ public class HugeTraverser {
}
return edges;
}
-
}
}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java
index b3ae29ac8..9f16f480b 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java
@@ -25,7 +25,7 @@ import org.apache.hugegraph.HugeGraph;
import org.apache.hugegraph.backend.id.Id;
import org.apache.hugegraph.structure.HugeEdge;
import org.apache.hugegraph.traversal.algorithm.records.KneighborRecords;
-import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.type.define.Directions;
import org.apache.hugegraph.util.E;
import org.apache.tinkerpop.gremlin.structure.Edge;
@@ -69,7 +69,7 @@ public class KneighborTraverser extends OltpTraverser {
return all;
}
- public KneighborRecords customizedKneighbor(Id source, EdgeStep step,
+ public KneighborRecords customizedKneighbor(Id source, Steps steps,
int maxDepth, long limit) {
E.checkNotNull(source, "source vertex id");
this.checkVertexExist(source, "source vertex");
@@ -85,7 +85,7 @@ public class KneighborTraverser extends OltpTraverser {
if (this.reachLimit(limit, records.size())) {
return;
}
- Iterator<Edge> edges = edgesOfVertex(v, step);
+ Iterator<Edge> edges = edgesOfVertex(v, steps);
this.vertexIterCounter.addAndGet(1L);
while (!this.reachLimit(limit, records.size()) && edges.hasNext())
{
HugeEdge edge = (HugeEdge) edges.next();
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java
index 9f40be8fb..9924c766c 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java
@@ -26,7 +26,7 @@ import org.apache.hugegraph.HugeGraph;
import org.apache.hugegraph.backend.id.Id;
import org.apache.hugegraph.structure.HugeEdge;
import org.apache.hugegraph.traversal.algorithm.records.KoutRecords;
-import org.apache.hugegraph.traversal.algorithm.steps.EdgeStep;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
import org.apache.hugegraph.type.define.Directions;
import org.apache.hugegraph.util.E;
import org.apache.tinkerpop.gremlin.structure.Edge;
@@ -97,7 +97,7 @@ public class KoutTraverser extends OltpTraverser {
return latest;
}
- public KoutRecords customizedKout(Id source, EdgeStep step,
+ public KoutRecords customizedKout(Id source, Steps steps,
int maxDepth, boolean nearest,
long capacity, long limit) {
E.checkNotNull(source, "source vertex id");
@@ -109,13 +109,13 @@ public class KoutTraverser extends OltpTraverser {
depth[0] = maxDepth;
boolean concurrent = maxDepth >= this.concurrentDepth();
- KoutRecords records = new KoutRecords(concurrent, source, nearest);
+ KoutRecords records = new KoutRecords(concurrent, source, nearest, 0);
Consumer<Id> consumer = v -> {
if (this.reachLimit(limit, depth[0], records.size())) {
return;
}
- Iterator<Edge> edges = edgesOfVertex(v, step);
+ Iterator<Edge> edges = edgesOfVertex(v, steps);
this.vertexIterCounter.addAndGet(1L);
while (!this.reachLimit(limit, depth[0], records.size()) &&
edges.hasNext()) {
@@ -138,6 +138,38 @@ public class KoutTraverser extends OltpTraverser {
return records;
}
+ public KoutRecords dfsKout(Id source, Steps steps,
+ int maxDepth, boolean nearest,
+ long capacity, long limit) {
+ E.checkNotNull(source, "source vertex id");
+ this.checkVertexExist(source, "source vertex");
+ checkPositive(maxDepth, "k-out max_depth");
+ checkCapacity(capacity);
+ checkLimit(limit);
+
+ Set<Id> all = newIdSet();
+ all.add(source);
+
+ KoutRecords records = new KoutRecords(false, source, nearest,
maxDepth);
+ Iterator<Edge> iterator = this.createNestedIterator(source, steps,
maxDepth, all, nearest);
+ while (iterator.hasNext()) {
+ HugeEdge edge = (HugeEdge) iterator.next();
+ this.edgeIterCounter.addAndGet(1L);
+
+ Id target = edge.id().otherVertexId();
+ if (!nearest || !all.contains(target)) {
+ records.addFullPath(HugeTraverser.pathEdges(iterator, edge));
+ }
+
+ if (limit != NO_LIMIT && records.size() >= limit ||
+ capacity != NO_LIMIT && all.size() > capacity) {
+ break;
+ }
+ }
+
+ return records;
+ }
+
private void checkCapacity(long capacity, long accessed, long depth) {
if (capacity == NO_LIMIT) {
return;
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/iterator/NestedIterator.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/iterator/NestedIterator.java
new file mode 100644
index 000000000..3b9f03794
--- /dev/null
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/iterator/NestedIterator.java
@@ -0,0 +1,195 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You 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 org.apache.hugegraph.traversal.algorithm.iterator;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.hugegraph.backend.id.Id;
+import org.apache.hugegraph.iterator.WrappedIterator;
+import org.apache.hugegraph.structure.HugeEdge;
+import org.apache.hugegraph.traversal.algorithm.HugeTraverser;
+import org.apache.hugegraph.traversal.algorithm.steps.Steps;
+import org.apache.hugegraph.util.collection.ObjectIntMapping;
+import org.apache.hugegraph.util.collection.ObjectIntMappingFactory;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+
+public class NestedIterator extends WrappedIterator<Edge> {
+
+ private final int MAX_CACHED_COUNT = 1000;
+ /**
+ * Set<Id> visited: visited vertex-ids of all parent-tree
+ * used to exclude visited vertex
+ */
+ private final boolean nearest;
+ private final Set<Id> visited;
+ private final int MAX_VISITED_COUNT = 100000;
+
+ // cache for edges, initial capacity to avoid memory fragment
+ private final List<HugeEdge> cache;
+ private final Map<Long, Integer> parentEdgePointerMap;
+
+ private final Iterator<Edge> parentIterator;
+ private final HugeTraverser traverser;
+ private final Steps steps;
+ private final ObjectIntMapping<Id> idMapping;
+ private HugeEdge currentEdge;
+ private int cachePointer;
+ private Iterator<Edge> currentIterator;
+
+ public NestedIterator(HugeTraverser traverser,
+ Iterator<Edge> parentIterator,
+ Steps steps,
+ Set<Id> visited,
+ boolean nearest) {
+ this.traverser = traverser;
+ this.parentIterator = parentIterator;
+ this.steps = steps;
+ this.visited = visited;
+ this.nearest = nearest;
+
+ this.cache = new ArrayList<>(MAX_CACHED_COUNT);
+ this.parentEdgePointerMap = new HashMap<>();
+
+ this.cachePointer = 0;
+ this.currentEdge = null;
+ this.currentIterator = null;
+
+ this.idMapping = ObjectIntMappingFactory.newObjectIntMapping(false);
+ }
+
+ private static Long makeVertexPairIndex(int source, int target) {
+ return ((long) source & 0xFFFFFFFFL) |
+ (((long) target << 32) & 0xFFFFFFFF00000000L);
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (this.currentIterator == null || !this.currentIterator.hasNext()) {
+ return fetch();
+ }
+ return true;
+ }
+
+ @Override
+ public Edge next() {
+ return this.currentIterator.next();
+ }
+
+ @Override
+ protected Iterator<?> originIterator() {
+ return this.parentIterator;
+ }
+
+ @Override
+ protected boolean fetch() {
+ while (this.currentIterator == null ||
!this.currentIterator.hasNext()) {
+ if (this.currentIterator != null) {
+ this.currentIterator = null;
+ }
+
+ if (this.cache.size() == this.cachePointer && !this.fillCache()) {
+ return false;
+ }
+
+ this.currentEdge = this.cache.get(this.cachePointer);
+ this.cachePointer++;
+ this.currentIterator =
+
traverser.edgesOfVertex(this.currentEdge.id().otherVertexId(), steps);
+ this.traverser.vertexIterCounter.addAndGet(1L);
+
+ }
+ return true;
+ }
+
+ private boolean fillCache() {
+ // fill cache from parent
+ while (this.parentIterator.hasNext() && this.cache.size() <
MAX_CACHED_COUNT) {
+ HugeEdge edge = (HugeEdge) this.parentIterator.next();
+ Id vertexId = edge.id().otherVertexId();
+
+ this.traverser.edgeIterCounter.addAndGet(1L);
+
+ if (!this.nearest || !this.visited.contains(vertexId)) {
+ // update parent edge cache pointer
+ int parentEdgePointer = -1;
+ if (this.parentIterator instanceof NestedIterator) {
+ parentEdgePointer = ((NestedIterator)
this.parentIterator).currentEdgePointer();
+ }
+
+ this.parentEdgePointerMap.put(makeEdgeIndex(edge),
parentEdgePointer);
+
+ this.cache.add(edge);
+ if (this.visited.size() < MAX_VISITED_COUNT) {
+ this.visited.add(vertexId);
+ }
+ }
+ }
+ return this.cache.size() > this.cachePointer;
+ }
+
+ public List<HugeEdge> pathEdges() {
+ List<HugeEdge> edges = new ArrayList<>();
+ HugeEdge currentEdge = this.currentEdge;
+ if (this.parentIterator instanceof NestedIterator) {
+ NestedIterator parent = (NestedIterator) this.parentIterator;
+ int parentEdgePointer =
this.parentEdgePointerMap.get(makeEdgeIndex(currentEdge));
+ edges.addAll(parent.pathEdges(parentEdgePointer));
+ }
+ edges.add(currentEdge);
+ return edges;
+ }
+
+ private List<HugeEdge> pathEdges(int edgePointer) {
+ List<HugeEdge> edges = new ArrayList<>();
+ HugeEdge edge = this.cache.get(edgePointer);
+ if (this.parentIterator instanceof NestedIterator) {
+ NestedIterator parent = (NestedIterator) this.parentIterator;
+ int parentEdgePointer =
this.parentEdgePointerMap.get(makeEdgeIndex(edge));
+ edges.addAll(parent.pathEdges(parentEdgePointer));
+ }
+ edges.add(edge);
+ return edges;
+ }
+
+ public int currentEdgePointer() {
+ return this.cachePointer - 1;
+ }
+
+ private Long makeEdgeIndex(HugeEdge edge) {
+ int sourceV = this.code(edge.id().ownerVertexId());
+ int targetV = this.code(edge.id().otherVertexId());
+ return makeVertexPairIndex(sourceV, targetV);
+ }
+
+ private int code(Id id) {
+ if (id.number()) {
+ long l = id.asLong();
+ if (0 <= l && l <= Integer.MAX_VALUE) {
+ return (int) l;
+ }
+ }
+ int code = this.idMapping.object2Code(id);
+ assert code > 0;
+ return -code;
+ }
+}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java
index 5953e71e2..e4264893a 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java
@@ -23,6 +23,7 @@ import java.util.List;
import java.util.Stack;
import org.apache.hugegraph.backend.id.Id;
+import org.apache.hugegraph.structure.HugeEdge;
import org.apache.hugegraph.traversal.algorithm.HugeTraverser.PathSet;
import org.apache.hugegraph.traversal.algorithm.records.record.Record;
import org.apache.hugegraph.traversal.algorithm.records.record.RecordType;
@@ -32,8 +33,23 @@ import org.apache.hugegraph.util.collection.IntIterator;
public class KoutRecords extends SingleWayMultiPathsRecords {
- public KoutRecords(boolean concurrent, Id source, boolean nearest) {
+ // Non-zero depth is used for deepFirst traverse mode.
+ // In such case, startOneLayer/finishOneLayer should not be called,
+ // instead, we should use addFullPath
+ private final int depth;
+
+ public KoutRecords(boolean concurrent, Id source, boolean nearest, int
depth) {
super(RecordType.INT, concurrent, source, nearest);
+
+ // add depth(num) records to record each layer
+ this.depth = depth;
+ for (int i = 0; i < depth; i++) {
+ this.records().push(this.newRecord());
+ }
+ assert (this.records().size() == (depth + 1));
+
+ // init top layer's parentRecord
+ this.currentRecord(this.records().peek(), null);
}
@Override
@@ -61,4 +77,29 @@ public class KoutRecords extends SingleWayMultiPathsRecords {
}
return paths;
}
+
+ public void addFullPath(List<HugeEdge> edges) {
+ assert (depth == edges.size());
+
+ int sourceCode = this.code(edges.get(0).id().ownerVertexId());
+ int targetCode;
+ for (int i = 0; i < edges.size(); i++) {
+ HugeEdge edge = edges.get(i);
+ Id sourceV = edge.id().ownerVertexId();
+ Id targetV = edge.id().otherVertexId();
+
+ assert (this.code(sourceV) == sourceCode);
+
+ this.edgeResults().addEdge(sourceV, targetV, edge);
+
+ targetCode = this.code(targetV);
+ Record record = this.records().elementAt(i + 1);
+ if (this.sourceCode == targetCode) {
+ break;
+ }
+
+ this.addPathToRecord(sourceCode, targetCode, record);
+ sourceCode = targetCode;
+ }
+ }
}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java
index d41adc92a..fad78edf0 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java
@@ -40,9 +40,8 @@ import org.apache.hugegraph.util.collection.IntSet;
public abstract class SingleWayMultiPathsRecords extends AbstractRecords {
+ protected final int sourceCode;
private final Stack<Record> records;
-
- private final int sourceCode;
private final boolean nearest;
private final IntSet accessedVertices;
private final EdgeRecord edgeResults;
@@ -110,15 +109,16 @@ public abstract class SingleWayMultiPathsRecords extends
AbstractRecords {
@Watched
public void addPath(Id source, Id target) {
- int sourceCode = this.code(source);
- int targetCode = this.code(target);
+ this.addPathToRecord(this.code(source), this.code(target),
this.currentRecord());
+ }
+
+ public void addPathToRecord(int sourceCode, int targetCode, Record record)
{
if (this.nearest && this.accessedVertices.contains(targetCode) ||
- !this.nearest && this.currentRecord().containsKey(targetCode) ||
+ !this.nearest && record.containsKey(targetCode) ||
targetCode == this.sourceCode) {
return;
}
- this.currentRecord().addPath(targetCode, sourceCode);
-
+ record.addPath(targetCode, sourceCode);
this.accessedVertices.add(targetCode);
}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/steps/Steps.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/steps/Steps.java
new file mode 100644
index 000000000..d1a9238be
--- /dev/null
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/steps/Steps.java
@@ -0,0 +1,187 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You 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 org.apache.hugegraph.traversal.algorithm.steps;
+
+import static org.apache.hugegraph.traversal.algorithm.HugeTraverser.NO_LIMIT;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.hugegraph.HugeGraph;
+import org.apache.hugegraph.backend.id.Id;
+import org.apache.hugegraph.schema.EdgeLabel;
+import org.apache.hugegraph.schema.VertexLabel;
+import org.apache.hugegraph.traversal.algorithm.HugeTraverser;
+import org.apache.hugegraph.traversal.optimize.TraversalUtil;
+import org.apache.hugegraph.type.define.Directions;
+import org.apache.hugegraph.util.E;
+
+public class Steps {
+
+ protected final Map<Id, StepEntity> edgeSteps;
+ protected final Map<Id, StepEntity> vertexSteps;
+ protected final Directions direction;
+ protected final long degree;
+ protected final long skipDegree;
+
+ public Steps(HugeGraph graph, Directions direction,
+ Map<String, Map<String, Object>> vSteps,
+ Map<String, Map<String, Object>> eSteps,
+ long degree, long skipDegree) {
+ E.checkArgument(degree == NO_LIMIT || degree > 0L,
+ "The max degree must be > 0 or == -1, but got: %s",
degree);
+ HugeTraverser.checkSkipDegree(skipDegree, degree, NO_LIMIT);
+
+ this.direction = direction;
+
+ // parse vertex steps
+ this.vertexSteps = new HashMap<>();
+ if (vSteps != null && !vSteps.isEmpty()) {
+ initVertexFilter(graph, vSteps);
+ }
+
+ // parse edge steps
+ this.edgeSteps = new HashMap<>();
+ if (eSteps != null && !eSteps.isEmpty()) {
+ initEdgeFilter(graph, eSteps);
+ }
+
+ this.degree = degree;
+ this.skipDegree = skipDegree;
+ }
+
+ private void initVertexFilter(HugeGraph graph, Map<String, Map<String,
Object>> vSteps) {
+ for (Map.Entry<String, Map<String, Object>> entry : vSteps.entrySet())
{
+ if (checkEntryEmpty(entry)) {
+ continue;
+ }
+ E.checkArgument(entry.getKey() != null &&
!entry.getKey().isEmpty(),
+ "The vertex step label could not be null");
+
+ VertexLabel vertexLabel = graph.vertexLabel(entry.getKey());
+ StepEntity stepEntity = handleStepEntity(graph, entry,
vertexLabel.id());
+ this.vertexSteps.put(vertexLabel.id(), stepEntity);
+ }
+ }
+
+ private void initEdgeFilter(HugeGraph graph, Map<String, Map<String,
Object>> eSteps) {
+ for (Map.Entry<String, Map<String, Object>> entry : eSteps.entrySet())
{
+ if (checkEntryEmpty(entry)) {
+ continue;
+ }
+ E.checkArgument(entry.getKey() != null &&
!entry.getKey().isEmpty(),
+ "The edge step label could not be null");
+
+ EdgeLabel edgeLabel = graph.edgeLabel(entry.getKey());
+ StepEntity stepEntity = handleStepEntity(graph, entry,
edgeLabel.id());
+ this.edgeSteps.put(edgeLabel.id(), stepEntity);
+ }
+ }
+
+ private StepEntity handleStepEntity(HugeGraph graph,
+ Map.Entry<String, Map<String, Object>>
entry,
+ Id id) {
+ Map<Id, Object> properties = null;
+ if (entry.getValue() != null) {
+ properties = TraversalUtil.transProperties(graph,
entry.getValue());
+ }
+ return new StepEntity(id, entry.getKey(), properties);
+ }
+
+ private boolean checkEntryEmpty(Map.Entry<String, Map<String, Object>>
entry) {
+ return (entry.getKey() == null || entry.getKey().isEmpty()) &&
+ (entry.getValue() == null || entry.getValue().isEmpty());
+ }
+
+ public long degree() {
+ return this.degree;
+ }
+
+ public Map<Id, StepEntity> edgeSteps() {
+ return this.edgeSteps;
+ }
+
+ public Map<Id, StepEntity> vertexSteps() {
+ return this.vertexSteps;
+ }
+
+ public long skipDegree() {
+ return this.skipDegree;
+ }
+
+ public Directions direction() {
+ return this.direction;
+ }
+
+ public long limit() {
+ return this.skipDegree > 0L ? this.skipDegree : this.degree;
+ }
+
+ public List<Id> edgeLabels() {
+ return new ArrayList<>(this.edgeSteps.keySet());
+ }
+
+ public boolean isVertexEmpty() {
+ return this.vertexSteps.isEmpty();
+ }
+
+ @Override
+ public String toString() {
+ return "Steps{" +
+ "edgeSteps=" + this.edgeSteps +
+ ", vertexSteps=" + this.vertexSteps +
+ ", direction=" + this.direction +
+ ", degree=" + this.degree +
+ ", skipDegree=" + this.skipDegree +
+ '}';
+ }
+
+ public static class StepEntity {
+
+ protected final Id id;
+ protected final String label;
+ protected final Map<Id, Object> properties;
+
+ public StepEntity(Id id, String label, Map<Id, Object> properties) {
+ this.id = id;
+ this.label = label;
+ this.properties = properties;
+ }
+
+ public Id id() {
+ return this.id;
+ }
+
+ public String label() {
+ return this.label;
+ }
+
+ public Map<Id, Object> properties() {
+ return this.properties;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("StepEntity{id=%s,label=%s," +
+ "properties=%s}", this.id,
+ this.label, this.properties);
+ }
+ }
+}
diff --git
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java
index 77de34258..99f45fc1c 100644
---
a/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java
+++
b/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java
@@ -39,11 +39,18 @@ import org.apache.hugegraph.backend.query.Aggregate;
import org.apache.hugegraph.backend.query.Condition;
import org.apache.hugegraph.backend.query.ConditionQuery;
import org.apache.hugegraph.backend.query.Query;
+import org.apache.hugegraph.exception.NotSupportException;
+import org.apache.hugegraph.iterator.FilterIterator;
import org.apache.hugegraph.schema.PropertyKey;
import org.apache.hugegraph.schema.SchemaLabel;
+import org.apache.hugegraph.structure.HugeElement;
+import org.apache.hugegraph.structure.HugeProperty;
import org.apache.hugegraph.type.HugeType;
import org.apache.hugegraph.type.define.Directions;
import org.apache.hugegraph.type.define.HugeKeys;
+import org.apache.hugegraph.util.CollectionUtil;
+import org.apache.hugegraph.util.DateUtil;
+import org.apache.hugegraph.util.E;
import org.apache.hugegraph.util.JsonUtil;
import org.apache.tinkerpop.gremlin.process.traversal.Compare;
import org.apache.tinkerpop.gremlin.process.traversal.Contains;
@@ -83,13 +90,6 @@ import org.apache.tinkerpop.gremlin.structure.T;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph;
-import org.apache.hugegraph.exception.NotSupportException;
-import org.apache.hugegraph.iterator.FilterIterator;
-import org.apache.hugegraph.structure.HugeElement;
-import org.apache.hugegraph.structure.HugeProperty;
-import org.apache.hugegraph.util.CollectionUtil;
-import org.apache.hugegraph.util.DateUtil;
-import org.apache.hugegraph.util.E;
import com.google.common.collect.ImmutableList;
public final class TraversalUtil {
@@ -146,7 +146,8 @@ public final class TraversalUtil {
}
local.setGraph(graph);
}
- for (final Traversal.Admin<?, ?> global : ((TraversalParent)
step).getGlobalChildren()) {
+ for (final Traversal.Admin<?, ?> global :
+ ((TraversalParent) step).getGlobalChildren()) {
if (global.getGraph().filter(g -> !(g instanceof
EmptyGraph)).isPresent()) {
continue;
}
@@ -690,7 +691,7 @@ public final class TraversalUtil {
return token2HugeKey(key) != null;
}
- @SuppressWarnings({ "unchecked", "rawtypes" })
+ @SuppressWarnings({"unchecked", "rawtypes"})
private static void collectPredicates(List<P<Object>> results,
List<P<?>> predicates) {
for (P<?> p : predicates) {
@@ -781,7 +782,7 @@ public final class TraversalUtil {
public static void retrieveSysprop(List<HasContainer> hasContainers,
Function<HasContainer, Boolean> func) {
- for (Iterator<HasContainer> iter = hasContainers.iterator();
iter.hasNext();) {
+ for (Iterator<HasContainer> iter = hasContainers.iterator();
iter.hasNext(); ) {
HasContainer container = iter.next();
if (container.getKey().startsWith("~") && func.apply(container)) {
iter.remove();
@@ -842,7 +843,7 @@ public final class TraversalUtil {
public static Map<Id, Object> transProperties(HugeGraph graph,
Map<String, Object> props) {
Map<Id, Object> pks = new HashMap<>(props.size());
- for (Map.Entry<String, Object> e: props.entrySet()) {
+ for (Map.Entry<String, Object> e : props.entrySet()) {
PropertyKey pk = graph.propertyKey(e.getKey());
pks.put(pk.id(), e.getValue());
}
diff --git
a/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java
b/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java
index f207b59b2..e415fa568 100644
---
a/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java
+++
b/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java
@@ -20,15 +20,16 @@ package org.apache.hugegraph.api.traversers;
import java.util.List;
import java.util.Map;
-import jakarta.ws.rs.core.Response;
+import org.apache.hugegraph.api.BaseApiTest;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
-import org.apache.hugegraph.api.BaseApiTest;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
+import jakarta.ws.rs.core.Response;
+
public class KneighborApiTest extends BaseApiTest {
static final String PATH = TRAVERSERS_API + "/kneighbor";
@@ -64,13 +65,18 @@ public class KneighborApiTest extends BaseApiTest {
String markoId = name2Ids.get("marko");
String reqBody = String.format("{ " +
"\"source\": \"%s\", " +
- "\"step\": { " +
+ "\"steps\": { " +
" \"direction\": \"BOTH\", " +
- " \"labels\": [\"knows\", " +
- " \"created\"], " +
- "\"properties\": { " +
- " \"weight\": \"P.gt(0.1)\"}, " +
- " \"degree\": 10000, " +
+ " \"edge_steps\": [" +
+ " {\"label\": \"knows\"," +
+ " \"properties\": {" +
+ " \"weight\": \"P.gt(0.1)\"}}," +
+ " {\"label\": \"created\"," +
+ " \"properties\": {" +
+ " \"weight\": \"P.gt(0.1)\"}}" +
+ " ], " +
+ " \"vertex_steps\": []," +
+ " \"max_degree\": 10000, " +
" \"skip_degree\": 100000}, " +
"\"max_depth\": 3, " +
"\"limit\": 10000, " +
diff --git
a/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java
b/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java
index 2fb8a6466..11544e3af 100644
---
a/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java
+++
b/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java
@@ -20,15 +20,16 @@ package org.apache.hugegraph.api.traversers;
import java.util.List;
import java.util.Map;
-import jakarta.ws.rs.core.Response;
+import org.apache.hugegraph.api.BaseApiTest;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
-import org.apache.hugegraph.api.BaseApiTest;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
+import jakarta.ws.rs.core.Response;
+
public class KoutApiTest extends BaseApiTest {
static final String PATH = TRAVERSERS_API + "/kout";
@@ -75,13 +76,18 @@ public class KoutApiTest extends BaseApiTest {
String markoId = name2Ids.get("marko");
String reqBody = String.format("{ " +
"\"source\": \"%s\", " +
- "\"step\": { " +
+ "\"steps\": { " +
" \"direction\": \"BOTH\", " +
- " \"labels\": [\"knows\", " +
- " \"created\"], " +
- "\"properties\": { " +
- " \"weight\": \"P.gt(0.1)\"}, " +
- " \"degree\": 10000, " +
+ " \"edge_steps\": [" +
+ " {\"label\": \"knows\"," +
+ " \"properties\": {" +
+ " \"weight\": \"P.gt(0.1)\"}}," +
+ " {\"label\": \"created\"," +
+ " \"properties\": {" +
+ " \"weight\": \"P.gt(0.1)\"}}" +
+ " ], " +
+ " \"vertex_steps\": []," +
+ " \"max_degree\": 10000, " +
" \"skip_degree\": 100000}, " +
"\"max_depth\": 1, " +
"\"nearest\": true, " +
