This is an automated email from the ASF dual-hosted git repository. jin pushed a commit to branch pd-store in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph.git
commit 9c2d3ad6d3c3666dcdaf674c337ec39428dff158 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-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java b/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java index a0e7d0c4e..8624b2dd0 100644 --- a/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KneighborAPI.java +++ b/hugegraph-server/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-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java b/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java index 1adf2be5e..1f1b6922d 100644 --- a/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/KoutAPI.java +++ b/hugegraph-server/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-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java b/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java index 9649ec03c..cc61a9fad 100644 --- a/hugegraph-server/hugegraph-api/src/main/java/org/apache/hugegraph/api/traversers/TraverserAPI.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java index 518ac5303..32f416b37 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/query/Query.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java index 7b5289237..c9502c809 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/backend/tx/GraphTransaction.java +++ b/hugegraph-server/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 @@ -971,7 +971,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; } @@ -1229,9 +1229,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 @@ -1264,8 +1265,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; @@ -1397,8 +1429,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); /* @@ -1421,7 +1453,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()) { @@ -1614,6 +1646,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(), @@ -1837,9 +1870,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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java index c0d36f31b..f5415d9c5 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/HugeTraverser.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java index b3ae29ac8..9f16f480b 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KneighborTraverser.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java index 9f40be8fb..9924c766c 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/KoutTraverser.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/iterator/NestedIterator.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/iterator/NestedIterator.java new file mode 100644 index 000000000..3b9f03794 --- /dev/null +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java index 5953e71e2..e4264893a 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/KoutRecords.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java index d41adc92a..fad78edf0 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/records/SingleWayMultiPathsRecords.java +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/steps/Steps.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/steps/Steps.java new file mode 100644 index 000000000..d1a9238be --- /dev/null +++ b/hugegraph-server/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-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java b/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java index 77de34258..99f45fc1c 100644 --- a/hugegraph-server/hugegraph-core/src/main/java/org/apache/hugegraph/traversal/optimize/TraversalUtil.java +++ b/hugegraph-server/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-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java b/hugegraph-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java index f207b59b2..e415fa568 100644 --- a/hugegraph-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KneighborApiTest.java +++ b/hugegraph-server/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-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java b/hugegraph-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java index 2fb8a6466..11544e3af 100644 --- a/hugegraph-server/hugegraph-test/src/main/java/org/apache/hugegraph/api/traversers/KoutApiTest.java +++ b/hugegraph-server/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, " +
