diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java --- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java @@ -113,8 +113,8 @@ static class StopTraversalException extends RuntimeException { } - /** Generic BFS traversal algorithm. */ - static class BFSVisitor { + /** Generic BFS/DFS traversal algorithm. */ + static class Visitor { /** The graph to traverse. */ protected final SwhUnidirectionalGraph g; /** Depth of the node currently being visited */ @@ -132,20 +132,25 @@ * nodes. */ protected HashMap parents = new HashMap<>(); - /** Queue of nodes to visit (also called "frontier", "open set", "wavefront" etc.) */ - protected ArrayDeque queue = new ArrayDeque<>(); + /** + * Queue (or stack in DFS mode) of nodes to visit (also called "frontier", "open set", "wavefront" + * etc.), + **/ + protected ArrayDeque frontier = new ArrayDeque<>(); /** If > 0, the maximum depth of the traversal. */ private long maxDepth = -1; /** If > 0, the maximum number of edges to traverse. */ private long maxEdges = -1; + /** Determines whether the traversal is performed as a BFS or a DFS. */ + private TraversalOrder traversal_order; - BFSVisitor(SwhUnidirectionalGraph g) { + Visitor(SwhUnidirectionalGraph g) { this.g = g; } - /** Add a new source node to the initial queue. */ + /** Add a new source node to the initial frontier. */ public void addSource(long nodeId) { - queue.add(nodeId); + frontier.add(nodeId); parents.put(nodeId, -1L); } @@ -159,17 +164,24 @@ maxEdges = edges; } + /** + * Set whether the traversal will be performed as a DFS or a BFS (default is BFS). + **/ + public void setTraversalOrder(TraversalOrder order) { + traversal_order = order; + } + /** Setup the visit counters and depth sentinel. */ public void visitSetup() { edgesAccessed = 0; depth = 0; - queue.add(-1L); // depth sentinel + frontier.add(-1L); // depth sentinel } /** Perform the visit */ public void visit() { visitSetup(); - while (!queue.isEmpty()) { + while (!frontier.isEmpty()) { visitStep(); } } @@ -177,12 +189,12 @@ /** Single "step" of a visit. Advance the frontier of exactly one node. */ public void visitStep() { try { - assert !queue.isEmpty(); - long curr = queue.poll(); + assert !frontier.isEmpty(); + long curr = traversal_order == TraversalOrder.DFS ? frontier.pop() : frontier.poll(); if (curr == -1L) { ++depth; - if (!queue.isEmpty()) { - queue.add(-1L); + if (!frontier.isEmpty()) { + frontier.add(-1L); visitStep(); } return; @@ -196,8 +208,8 @@ } visitNode(curr); } catch (StopTraversalException e) { - // Traversal is over, clear the to-do queue. - queue.clear(); + // Traversal is over, clear the to-do queue/stack. + frontier.clear(); } } @@ -222,17 +234,17 @@ /** Visit an edge. Override to do additional processing on the edge. */ protected void visitEdge(long src, long dst, Label label) { if (!parents.containsKey(dst)) { - queue.add(dst); + frontier.add(dst); parents.put(dst, src); } } } /** - * SimpleTraversal is used by the Traverse endpoint. It extends BFSVisitor with additional - * processing, notably related to graph properties and filters. + * SimpleTraversal is used by the Traverse endpoint. It extends Visitor with additional processing, + * notably related to graph properties and filters. */ - static class SimpleTraversal extends BFSVisitor { + static class SimpleTraversal extends Visitor { private final NodeFilterChecker nodeReturnChecker; private final AllowedEdges allowedEdges; private final TraversalRequest request; @@ -259,6 +271,9 @@ if (request.hasMaxEdges()) { setMaxEdges(request.getMaxEdges()); } + if (request.hasTraversalOrder()) { + setTraversalOrder(request.getTraversalOrder()); + } if (request.hasMaxMatchingNodes() && request.getMaxMatchingNodes() > 0) { this.remainingMatches = request.getMaxMatchingNodes(); } else { @@ -311,10 +326,10 @@ /** * FindPathTo searches for a path from a source node to a node matching a given criteria It extends - * BFSVisitor with additional processing, and makes the traversal stop as soon as a node matching - * the given criteria is found. + * Visitor with additional processing, and makes the traversal stop as soon as a node matching the + * given criteria is found. */ - static class FindPathTo extends BFSVisitor { + static class FindPathTo extends Visitor { private final AllowedEdges allowedEdges; private final FindPathToRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; @@ -401,14 +416,14 @@ * common ancestor between the two sets, respectively. These will be the midpoints of the returned * path. */ - static class FindPathBetween extends BFSVisitor { + static class FindPathBetween extends Visitor { private final FindPathBetweenRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final AllowedEdges allowedEdgesSrc; private final AllowedEdges allowedEdgesDst; - private final BFSVisitor srcVisitor; - private final BFSVisitor dstVisitor; + private final Visitor srcVisitor; + private final Visitor dstVisitor; private Long middleNode = null; FindPathBetween(SwhBidirectionalGraph bidirectionalGraph, FindPathBetweenRequest request) { @@ -442,7 +457,7 @@ * Source sub-visitor. Aborts as soon as it finds a node already visited by the destination * sub-visitor. */ - this.srcVisitor = new BFSVisitor(srcGraph) { + this.srcVisitor = new Visitor(srcGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesSrc); @@ -462,7 +477,7 @@ * Destination sub-visitor. Aborts as soon as it finds a node already visited by the source * sub-visitor. */ - this.dstVisitor = new BFSVisitor(dstGraph) { + this.dstVisitor = new Visitor(dstGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesDst); @@ -502,11 +517,11 @@ */ srcVisitor.visitSetup(); dstVisitor.visitSetup(); - while (!srcVisitor.queue.isEmpty() || !dstVisitor.queue.isEmpty()) { - if (!srcVisitor.queue.isEmpty()) { + while (!srcVisitor.frontier.isEmpty() || !dstVisitor.frontier.isEmpty()) { + if (!srcVisitor.frontier.isEmpty()) { srcVisitor.visitStep(); } - if (!dstVisitor.queue.isEmpty()) { + if (!dstVisitor.frontier.isEmpty()) { dstVisitor.visitStep(); } } diff --git a/proto/swhgraph.proto b/proto/swhgraph.proto --- a/proto/swhgraph.proto +++ b/proto/swhgraph.proto @@ -72,6 +72,14 @@ BACKWARD = 1; } +/* Algorithm used by traversal requests */ +enum TraversalOrder { + /* Breadth-first search, the default */ + BFS = 0; + /* Depth-first search */ + DFS = 1; +} + /* Describe a node to return */ message GetNodeRequest { /* SWHID of the node to return */ @@ -109,6 +117,8 @@ /* Maximum number of matching results before stopping. For Traverse(), this is * the total number of results. Defaults to infinite. */ optional int64 max_matching_nodes = 9; + /* Algorithm used by the traversal request; defaults to BFS */ + optional TraversalOrder traversal_order = 10; } /* FindPathToRequest describes a request to find a shortest path between a diff --git a/swh/graph/grpc/swhgraph_pb2.py b/swh/graph/grpc/swhgraph_pb2.py --- a/swh/graph/grpc/swhgraph_pb2.py +++ b/swh/graph/grpc/swhgraph_pb2.py @@ -16,12 +16,16 @@ from google.protobuf import field_mask_pb2 as google_dot_protobuf_dot_field__mask__pb2 -DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x1dswh/graph/grpc/swhgraph.proto\x12\tswh.graph\x1a google/protobuf/field_mask.proto\"W\n\x0eGetNodeRequest\x12\r\n\x05swhid\x18\x01 \x01(\t\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x00\x88\x01\x01\x42\x07\n\x05_mask\"\x90\x03\n\x10TraversalRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12,\n\tdirection\x18\x02 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x03 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x04 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmin_depth\x18\x05 \x01(\x03H\x02\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x03\x88\x01\x01\x12\x30\n\x0creturn_nodes\x18\x07 \x01(\x0b\x32\x15.swh.graph.NodeFilterH\x04\x88\x01\x01\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x12\x1f\n\x12max_matching_nodes\x18\t \x01(\x03H\x06\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_min_depthB\x0c\n\n_max_depthB\x0f\n\r_return_nodesB\x07\n\x05_maskB\x15\n\x13_max_matching_nodes\"\x97\x02\n\x11\x46indPathToRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12%\n\x06target\x18\x02 \x01(\x0b\x32\x15.swh.graph.NodeFilter\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x04 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x05 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x02\x88\x01\x01\x12-\n\x04mask\x18\x07 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x03\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\x81\x03\n\x16\x46indPathBetweenRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12\x0b\n\x03\x64st\x18\x02 \x03(\t\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x39\n\x11\x64irection_reverse\x18\x04 \x01(\x0e\x32\x19.swh.graph.GraphDirectionH\x00\x88\x01\x01\x12\x12\n\x05\x65\x64ges\x18\x05 \x01(\tH\x01\x88\x01\x01\x12\x1a\n\redges_reverse\x18\x06 \x01(\tH\x02\x88\x01\x01\x12\x16\n\tmax_edges\x18\x07 \x01(\x03H\x03\x88\x01\x01\x12\x16\n\tmax_depth\x18\x08 \x01(\x03H\x04\x88\x01\x01\x12-\n\x04mask\x18\t \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x42\x14\n\x12_direction_reverseB\x08\n\x06_edgesB\x10\n\x0e_edges_reverseB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\xb2\x01\n\nNodeFilter\x12\x12\n\x05types\x18\x01 \x01(\tH\x00\x88\x01\x01\x12%\n\x18min_traversal_successors\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12%\n\x18max_traversal_successors\x18\x03 \x01(\x03H\x02\x88\x01\x01\x42\x08\n\x06_typesB\x1b\n\x19_min_traversal_successorsB\x1b\n\x19_max_traversal_successors\"\x92\x02\n\x04Node\x12\r\n\x05swhid\x18\x01 \x01(\t\x12\'\n\tsuccessor\x18\x02 \x03(\x0b\x32\x14.swh.graph.Successor\x12\x1b\n\x0enum_successors\x18\t \x01(\x03H\x01\x88\x01\x01\x12%\n\x03\x63nt\x18\x03 \x01(\x0b\x32\x16.swh.graph.ContentDataH\x00\x12&\n\x03rev\x18\x05 \x01(\x0b\x32\x17.swh.graph.RevisionDataH\x00\x12%\n\x03rel\x18\x06 \x01(\x0b\x32\x16.swh.graph.ReleaseDataH\x00\x12$\n\x03ori\x18\x08 \x01(\x0b\x32\x15.swh.graph.OriginDataH\x00\x42\x06\n\x04\x64\x61taB\x11\n\x0f_num_successors\"U\n\x04Path\x12\x1d\n\x04node\x18\x01 \x03(\x0b\x32\x0f.swh.graph.Node\x12\x1b\n\x0emidpoint_index\x18\x02 \x01(\x05H\x00\x88\x01\x01\x42\x11\n\x0f_midpoint_index\"N\n\tSuccessor\x12\x12\n\x05swhid\x18\x01 \x01(\tH\x00\x88\x01\x01\x12#\n\x05label\x18\x02 \x03(\x0b\x32\x14.swh.graph.EdgeLabelB\x08\n\x06_swhid\"U\n\x0b\x43ontentData\x12\x13\n\x06length\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x17\n\nis_skipped\x18\x02 \x01(\x08H\x01\x88\x01\x01\x42\t\n\x07_lengthB\r\n\x0b_is_skipped\"\xc6\x02\n\x0cRevisionData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x16\n\tcommitter\x18\x04 \x01(\x03H\x03\x88\x01\x01\x12\x1b\n\x0e\x63ommitter_date\x18\x05 \x01(\x03H\x04\x88\x01\x01\x12\"\n\x15\x63ommitter_date_offset\x18\x06 \x01(\x05H\x05\x88\x01\x01\x12\x14\n\x07message\x18\x07 \x01(\x0cH\x06\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x0c\n\n_committerB\x11\n\x0f_committer_dateB\x18\n\x16_committer_date_offsetB\n\n\x08_message\"\xcd\x01\n\x0bReleaseData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x11\n\x04name\x18\x04 \x01(\x0cH\x03\x88\x01\x01\x12\x14\n\x07message\x18\x05 \x01(\x0cH\x04\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x07\n\x05_nameB\n\n\x08_message\"&\n\nOriginData\x12\x10\n\x03url\x18\x01 \x01(\tH\x00\x88\x01\x01\x42\x06\n\x04_url\"-\n\tEdgeLabel\x12\x0c\n\x04name\x18\x01 \x01(\x0c\x12\x12\n\npermission\x18\x02 \x01(\x05\"\x1e\n\rCountResponse\x12\r\n\x05\x63ount\x18\x01 \x01(\x03\"\x0e\n\x0cStatsRequest\"\x9b\x02\n\rStatsResponse\x12\x11\n\tnum_nodes\x18\x01 \x01(\x03\x12\x11\n\tnum_edges\x18\x02 \x01(\x03\x12\x19\n\x11\x63ompression_ratio\x18\x03 \x01(\x01\x12\x15\n\rbits_per_node\x18\x04 \x01(\x01\x12\x15\n\rbits_per_edge\x18\x05 \x01(\x01\x12\x14\n\x0c\x61vg_locality\x18\x06 \x01(\x01\x12\x14\n\x0cindegree_min\x18\x07 \x01(\x03\x12\x14\n\x0cindegree_max\x18\x08 \x01(\x03\x12\x14\n\x0cindegree_avg\x18\t \x01(\x01\x12\x15\n\routdegree_min\x18\n \x01(\x03\x12\x15\n\routdegree_max\x18\x0b \x01(\x03\x12\x15\n\routdegree_avg\x18\x0c \x01(\x01*+\n\x0eGraphDirection\x12\x0b\n\x07\x46ORWARD\x10\x00\x12\x0c\n\x08\x42\x41\x43KWARD\x10\x01\x32\xcf\x03\n\x10TraversalService\x12\x35\n\x07GetNode\x12\x19.swh.graph.GetNodeRequest\x1a\x0f.swh.graph.Node\x12:\n\x08Traverse\x12\x1b.swh.graph.TraversalRequest\x1a\x0f.swh.graph.Node0\x01\x12;\n\nFindPathTo\x12\x1c.swh.graph.FindPathToRequest\x1a\x0f.swh.graph.Path\x12\x45\n\x0f\x46indPathBetween\x12!.swh.graph.FindPathBetweenRequest\x1a\x0f.swh.graph.Path\x12\x43\n\nCountNodes\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12\x43\n\nCountEdges\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12:\n\x05Stats\x12\x17.swh.graph.StatsRequest\x1a\x18.swh.graph.StatsResponseB0\n\x1eorg.softwareheritage.graph.rpcB\x0cGraphServiceP\x01\x62\x06proto3') +DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x1dswh/graph/grpc/swhgraph.proto\x12\tswh.graph\x1a google/protobuf/field_mask.proto\"W\n\x0eGetNodeRequest\x12\r\n\x05swhid\x18\x01 \x01(\t\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x00\x88\x01\x01\x42\x07\n\x05_mask\"\xdd\x03\n\x10TraversalRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12,\n\tdirection\x18\x02 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x03 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x04 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmin_depth\x18\x05 \x01(\x03H\x02\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x03\x88\x01\x01\x12\x30\n\x0creturn_nodes\x18\x07 \x01(\x0b\x32\x15.swh.graph.NodeFilterH\x04\x88\x01\x01\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x12\x1f\n\x12max_matching_nodes\x18\t \x01(\x03H\x06\x88\x01\x01\x12\x37\n\x0ftraversal_order\x18\n \x01(\x0e\x32\x19.swh.graph.TraversalOrderH\x07\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_min_depthB\x0c\n\n_max_depthB\x0f\n\r_return_nodesB\x07\n\x05_maskB\x15\n\x13_max_matching_nodesB\x12\n\x10_traversal_order\"\x97\x02\n\x11\x46indPathToRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12%\n\x06target\x18\x02 \x01(\x0b\x32\x15.swh.graph.NodeFilter\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x04 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x05 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x02\x88\x01\x01\x12-\n\x04mask\x18\x07 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x03\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\x81\x03\n\x16\x46indPathBetweenRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12\x0b\n\x03\x64st\x18\x02 \x03(\t\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x39\n\x11\x64irection_reverse\x18\x04 \x01(\x0e\x32\x19.swh.graph.GraphDirectionH\x00\x88\x01\x01\x12\x12\n\x05\x65\x64ges\x18\x05 \x01(\tH\x01\x88\x01\x01\x12\x1a\n\redges_reverse\x18\x06 \x01(\tH\x02\x88\x01\x01\x12\x16\n\tmax_edges\x18\x07 \x01(\x03H\x03\x88\x01\x01\x12\x16\n\tmax_depth\x18\x08 \x01(\x03H\x04\x88\x01\x01\x12-\n\x04mask\x18\t \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x42\x14\n\x12_direction_reverseB\x08\n\x06_edgesB\x10\n\x0e_edges_reverseB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\xb2\x01\n\nNodeFilter\x12\x12\n\x05types\x18\x01 \x01(\tH\x00\x88\x01\x01\x12%\n\x18min_traversal_successors\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12%\n\x18max_traversal_successors\x18\x03 \x01(\x03H\x02\x88\x01\x01\x42\x08\n\x06_typesB\x1b\n\x19_min_traversal_successorsB\x1b\n\x19_max_traversal_successors\"\x92\x02\n\x04Node\x12\r\n\x05swhid\x18\x01 \x01(\t\x12\'\n\tsuccessor\x18\x02 \x03(\x0b\x32\x14.swh.graph.Successor\x12\x1b\n\x0enum_successors\x18\t \x01(\x03H\x01\x88\x01\x01\x12%\n\x03\x63nt\x18\x03 \x01(\x0b\x32\x16.swh.graph.ContentDataH\x00\x12&\n\x03rev\x18\x05 \x01(\x0b\x32\x17.swh.graph.RevisionDataH\x00\x12%\n\x03rel\x18\x06 \x01(\x0b\x32\x16.swh.graph.ReleaseDataH\x00\x12$\n\x03ori\x18\x08 \x01(\x0b\x32\x15.swh.graph.OriginDataH\x00\x42\x06\n\x04\x64\x61taB\x11\n\x0f_num_successors\"U\n\x04Path\x12\x1d\n\x04node\x18\x01 \x03(\x0b\x32\x0f.swh.graph.Node\x12\x1b\n\x0emidpoint_index\x18\x02 \x01(\x05H\x00\x88\x01\x01\x42\x11\n\x0f_midpoint_index\"N\n\tSuccessor\x12\x12\n\x05swhid\x18\x01 \x01(\tH\x00\x88\x01\x01\x12#\n\x05label\x18\x02 \x03(\x0b\x32\x14.swh.graph.EdgeLabelB\x08\n\x06_swhid\"U\n\x0b\x43ontentData\x12\x13\n\x06length\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x17\n\nis_skipped\x18\x02 \x01(\x08H\x01\x88\x01\x01\x42\t\n\x07_lengthB\r\n\x0b_is_skipped\"\xc6\x02\n\x0cRevisionData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x16\n\tcommitter\x18\x04 \x01(\x03H\x03\x88\x01\x01\x12\x1b\n\x0e\x63ommitter_date\x18\x05 \x01(\x03H\x04\x88\x01\x01\x12\"\n\x15\x63ommitter_date_offset\x18\x06 \x01(\x05H\x05\x88\x01\x01\x12\x14\n\x07message\x18\x07 \x01(\x0cH\x06\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x0c\n\n_committerB\x11\n\x0f_committer_dateB\x18\n\x16_committer_date_offsetB\n\n\x08_message\"\xcd\x01\n\x0bReleaseData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x11\n\x04name\x18\x04 \x01(\x0cH\x03\x88\x01\x01\x12\x14\n\x07message\x18\x05 \x01(\x0cH\x04\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x07\n\x05_nameB\n\n\x08_message\"&\n\nOriginData\x12\x10\n\x03url\x18\x01 \x01(\tH\x00\x88\x01\x01\x42\x06\n\x04_url\"-\n\tEdgeLabel\x12\x0c\n\x04name\x18\x01 \x01(\x0c\x12\x12\n\npermission\x18\x02 \x01(\x05\"\x1e\n\rCountResponse\x12\r\n\x05\x63ount\x18\x01 \x01(\x03\"\x0e\n\x0cStatsRequest\"\x9b\x02\n\rStatsResponse\x12\x11\n\tnum_nodes\x18\x01 \x01(\x03\x12\x11\n\tnum_edges\x18\x02 \x01(\x03\x12\x19\n\x11\x63ompression_ratio\x18\x03 \x01(\x01\x12\x15\n\rbits_per_node\x18\x04 \x01(\x01\x12\x15\n\rbits_per_edge\x18\x05 \x01(\x01\x12\x14\n\x0c\x61vg_locality\x18\x06 \x01(\x01\x12\x14\n\x0cindegree_min\x18\x07 \x01(\x03\x12\x14\n\x0cindegree_max\x18\x08 \x01(\x03\x12\x14\n\x0cindegree_avg\x18\t \x01(\x01\x12\x15\n\routdegree_min\x18\n \x01(\x03\x12\x15\n\routdegree_max\x18\x0b \x01(\x03\x12\x15\n\routdegree_avg\x18\x0c \x01(\x01*+\n\x0eGraphDirection\x12\x0b\n\x07\x46ORWARD\x10\x00\x12\x0c\n\x08\x42\x41\x43KWARD\x10\x01*\"\n\x0eTraversalOrder\x12\x07\n\x03\x42\x46S\x10\x00\x12\x07\n\x03\x44\x46S\x10\x01\x32\xcf\x03\n\x10TraversalService\x12\x35\n\x07GetNode\x12\x19.swh.graph.GetNodeRequest\x1a\x0f.swh.graph.Node\x12:\n\x08Traverse\x12\x1b.swh.graph.TraversalRequest\x1a\x0f.swh.graph.Node0\x01\x12;\n\nFindPathTo\x12\x1c.swh.graph.FindPathToRequest\x1a\x0f.swh.graph.Path\x12\x45\n\x0f\x46indPathBetween\x12!.swh.graph.FindPathBetweenRequest\x1a\x0f.swh.graph.Path\x12\x43\n\nCountNodes\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12\x43\n\nCountEdges\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12:\n\x05Stats\x12\x17.swh.graph.StatsRequest\x1a\x18.swh.graph.StatsResponseB0\n\x1eorg.softwareheritage.graph.rpcB\x0cGraphServiceP\x01\x62\x06proto3') _GRAPHDIRECTION = DESCRIPTOR.enum_types_by_name['GraphDirection'] GraphDirection = enum_type_wrapper.EnumTypeWrapper(_GRAPHDIRECTION) +_TRAVERSALORDER = DESCRIPTOR.enum_types_by_name['TraversalOrder'] +TraversalOrder = enum_type_wrapper.EnumTypeWrapper(_TRAVERSALORDER) FORWARD = 0 BACKWARD = 1 +BFS = 0 +DFS = 1 _GETNODEREQUEST = DESCRIPTOR.message_types_by_name['GetNodeRequest'] @@ -157,40 +161,42 @@ DESCRIPTOR._options = None DESCRIPTOR._serialized_options = b'\n\036org.softwareheritage.graph.rpcB\014GraphServiceP\001' - _GRAPHDIRECTION._serialized_start=2910 - _GRAPHDIRECTION._serialized_end=2953 + _GRAPHDIRECTION._serialized_start=2987 + _GRAPHDIRECTION._serialized_end=3030 + _TRAVERSALORDER._serialized_start=3032 + _TRAVERSALORDER._serialized_end=3066 _GETNODEREQUEST._serialized_start=78 _GETNODEREQUEST._serialized_end=165 _TRAVERSALREQUEST._serialized_start=168 - _TRAVERSALREQUEST._serialized_end=568 - _FINDPATHTOREQUEST._serialized_start=571 - _FINDPATHTOREQUEST._serialized_end=850 - _FINDPATHBETWEENREQUEST._serialized_start=853 - _FINDPATHBETWEENREQUEST._serialized_end=1238 - _NODEFILTER._serialized_start=1241 - _NODEFILTER._serialized_end=1419 - _NODE._serialized_start=1422 - _NODE._serialized_end=1696 - _PATH._serialized_start=1698 - _PATH._serialized_end=1783 - _SUCCESSOR._serialized_start=1785 - _SUCCESSOR._serialized_end=1863 - _CONTENTDATA._serialized_start=1865 - _CONTENTDATA._serialized_end=1950 - _REVISIONDATA._serialized_start=1953 - _REVISIONDATA._serialized_end=2279 - _RELEASEDATA._serialized_start=2282 - _RELEASEDATA._serialized_end=2487 - _ORIGINDATA._serialized_start=2489 - _ORIGINDATA._serialized_end=2527 - _EDGELABEL._serialized_start=2529 - _EDGELABEL._serialized_end=2574 - _COUNTRESPONSE._serialized_start=2576 - _COUNTRESPONSE._serialized_end=2606 - _STATSREQUEST._serialized_start=2608 - _STATSREQUEST._serialized_end=2622 - _STATSRESPONSE._serialized_start=2625 - _STATSRESPONSE._serialized_end=2908 - _TRAVERSALSERVICE._serialized_start=2956 - _TRAVERSALSERVICE._serialized_end=3419 + _TRAVERSALREQUEST._serialized_end=645 + _FINDPATHTOREQUEST._serialized_start=648 + _FINDPATHTOREQUEST._serialized_end=927 + _FINDPATHBETWEENREQUEST._serialized_start=930 + _FINDPATHBETWEENREQUEST._serialized_end=1315 + _NODEFILTER._serialized_start=1318 + _NODEFILTER._serialized_end=1496 + _NODE._serialized_start=1499 + _NODE._serialized_end=1773 + _PATH._serialized_start=1775 + _PATH._serialized_end=1860 + _SUCCESSOR._serialized_start=1862 + _SUCCESSOR._serialized_end=1940 + _CONTENTDATA._serialized_start=1942 + _CONTENTDATA._serialized_end=2027 + _REVISIONDATA._serialized_start=2030 + _REVISIONDATA._serialized_end=2356 + _RELEASEDATA._serialized_start=2359 + _RELEASEDATA._serialized_end=2564 + _ORIGINDATA._serialized_start=2566 + _ORIGINDATA._serialized_end=2604 + _EDGELABEL._serialized_start=2606 + _EDGELABEL._serialized_end=2651 + _COUNTRESPONSE._serialized_start=2653 + _COUNTRESPONSE._serialized_end=2683 + _STATSREQUEST._serialized_start=2685 + _STATSREQUEST._serialized_end=2699 + _STATSRESPONSE._serialized_start=2702 + _STATSRESPONSE._serialized_end=2985 + _TRAVERSALSERVICE._serialized_start=3069 + _TRAVERSALSERVICE._serialized_end=3532 # @@protoc_insertion_point(module_scope) diff --git a/swh/graph/grpc/swhgraph_pb2.pyi b/swh/graph/grpc/swhgraph_pb2.pyi --- a/swh/graph/grpc/swhgraph_pb2.pyi +++ b/swh/graph/grpc/swhgraph_pb2.pyi @@ -37,6 +37,30 @@ global___GraphDirection = GraphDirection +class _TraversalOrder: + ValueType = typing.NewType('ValueType', builtins.int) + V: typing_extensions.TypeAlias = ValueType +class _TraversalOrderEnumTypeWrapper(google.protobuf.internal.enum_type_wrapper._EnumTypeWrapper[_TraversalOrder.ValueType], builtins.type): + DESCRIPTOR: google.protobuf.descriptor.EnumDescriptor + BFS: _TraversalOrder.ValueType # 0 + """Breadth-first search, the default""" + + DFS: _TraversalOrder.ValueType # 1 + """Depth-first search""" + +class TraversalOrder(_TraversalOrder, metaclass=_TraversalOrderEnumTypeWrapper): + """Algorithm used by traversal requests""" + pass + +BFS: TraversalOrder.ValueType # 0 +"""Breadth-first search, the default""" + +DFS: TraversalOrder.ValueType # 1 +"""Depth-first search""" + +global___TraversalOrder = TraversalOrder + + class GetNodeRequest(google.protobuf.message.Message): """Describe a node to return""" DESCRIPTOR: google.protobuf.descriptor.Descriptor @@ -75,6 +99,7 @@ RETURN_NODES_FIELD_NUMBER: builtins.int MASK_FIELD_NUMBER: builtins.int MAX_MATCHING_NODES_FIELD_NUMBER: builtins.int + TRAVERSAL_ORDER_FIELD_NUMBER: builtins.int @property def src(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]: """Set of source nodes (SWHIDs)""" @@ -119,6 +144,9 @@ the total number of results. Defaults to infinite. """ + traversal_order: global___TraversalOrder.ValueType + """Algorithm used by the traversal request; defaults to BFS""" + def __init__(self, *, src: typing.Optional[typing.Iterable[typing.Text]] = ..., @@ -130,9 +158,10 @@ return_nodes: typing.Optional[global___NodeFilter] = ..., mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ..., max_matching_nodes: typing.Optional[builtins.int] = ..., + traversal_order: typing.Optional[global___TraversalOrder.ValueType] = ..., ) -> None: ... - def HasField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes"]) -> builtins.bool: ... - def ClearField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","direction",b"direction","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes","src",b"src"]) -> None: ... + def HasField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","_traversal_order",b"_traversal_order","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes","traversal_order",b"traversal_order"]) -> builtins.bool: ... + def ClearField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","_traversal_order",b"_traversal_order","direction",b"direction","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes","src",b"src","traversal_order",b"traversal_order"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges",b"_edges"]) -> typing.Optional[typing_extensions.Literal["edges"]]: ... @typing.overload @@ -147,6 +176,8 @@ def WhichOneof(self, oneof_group: typing_extensions.Literal["_min_depth",b"_min_depth"]) -> typing.Optional[typing_extensions.Literal["min_depth"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_return_nodes",b"_return_nodes"]) -> typing.Optional[typing_extensions.Literal["return_nodes"]]: ... + @typing.overload + def WhichOneof(self, oneof_group: typing_extensions.Literal["_traversal_order",b"_traversal_order"]) -> typing.Optional[typing_extensions.Literal["traversal_order"]]: ... global___TraversalRequest = TraversalRequest class FindPathToRequest(google.protobuf.message.Message):