diff --git a/docs/grpc-api.rst b/docs/grpc-api.rst new file mode 100644 index 0000000..d4e2b8c --- /dev/null +++ b/docs/grpc-api.rst @@ -0,0 +1,11 @@ +.. _swh-graph-grpc-api: + +Using the GRPC API +================== + +Protobuf API Specification +-------------------------- + +.. literalinclude:: ../proto/swhgraph.proto + :language: protobuf + :linenos: diff --git a/docs/index.rst b/docs/index.rst index ec4b098..07e1068 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -1,18 +1,19 @@ .. _swh-graph: .. include:: README.rst .. toctree:: :maxdepth: 1 :caption: Overview quickstart api + grpc-api java-api memory compression cli docker git2graph /apidoc/swh.graph diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java index 3719ec5..3fa4359 100644 --- a/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java @@ -1,274 +1,274 @@ package org.softwareheritage.graph.rpc; import com.google.protobuf.FieldMask; import com.martiansoftware.jsap.*; import io.grpc.Server; import io.grpc.Status; import io.grpc.netty.shaded.io.grpc.netty.NettyServerBuilder; import io.grpc.netty.shaded.io.netty.channel.ChannelOption; import io.grpc.stub.StreamObserver; import io.grpc.protobuf.services.ProtoReflectionService; import it.unimi.dsi.logging.ProgressLogger; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.softwareheritage.graph.SWHID; import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.compress.LabelMapBuilder; import java.io.FileInputStream; import java.io.IOException; import java.util.Properties; import java.util.concurrent.Executors; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicLong; /** * Server that manages startup/shutdown of a {@code Greeter} server. */ public class GraphServer { private final static Logger logger = LoggerFactory.getLogger(GraphServer.class); private final SwhBidirectionalGraph graph; private final int port; private final int threads; private Server server; public GraphServer(String graphBasename, int port, int threads) throws IOException { this.graph = loadGraph(graphBasename); this.port = port; this.threads = threads; } public static SwhBidirectionalGraph loadGraph(String basename) throws IOException { // TODO: use loadLabelledMapped() when https://github.com/vigna/webgraph-big/pull/5 is merged SwhBidirectionalGraph g = SwhBidirectionalGraph.loadLabelled(basename, new ProgressLogger(logger)); g.loadContentLength(); g.loadContentIsSkipped(); g.loadPersonIds(); g.loadAuthorTimestamps(); g.loadCommitterTimestamps(); g.loadMessages(); g.loadTagNames(); g.loadLabelNames(); return g; } private void start() throws IOException { server = NettyServerBuilder.forPort(port).withChildOption(ChannelOption.SO_REUSEADDR, true) .executor(Executors.newFixedThreadPool(threads)).addService(new TraversalService(graph)) .addService(ProtoReflectionService.newInstance()).build().start(); logger.info("Server started, listening on " + port); Runtime.getRuntime().addShutdownHook(new Thread(() -> { try { GraphServer.this.stop(); } catch (InterruptedException e) { e.printStackTrace(System.err); } })); } private void stop() throws InterruptedException { if (server != null) { server.shutdown().awaitTermination(30, TimeUnit.SECONDS); } } /** * Await termination on the main thread since the grpc library uses daemon threads. */ private void blockUntilShutdown() throws InterruptedException { if (server != null) { server.awaitTermination(); } } private static JSAPResult parseArgs(String[] args) { JSAPResult config = null; try { SimpleJSAP jsap = new SimpleJSAP(LabelMapBuilder.class.getName(), "", new Parameter[]{ new FlaggedOption("port", JSAP.INTEGER_PARSER, "50091", JSAP.NOT_REQUIRED, 'p', "port", "The port on which the server should listen."), new FlaggedOption("threads", JSAP.INTEGER_PARSER, "1", JSAP.NOT_REQUIRED, 't', "threads", "The number of concurrent threads. 0 = number of cores."), new UnflaggedOption("graphBasename", JSAP.STRING_PARSER, JSAP.REQUIRED, "Basename of the output graph")}); config = jsap.parse(args); if (jsap.messagePrinted()) { System.exit(1); } } catch (JSAPException e) { e.printStackTrace(); } return config; } /** * Main launches the server from the command line. */ public static void main(String[] args) throws IOException, InterruptedException { JSAPResult config = parseArgs(args); String graphBasename = config.getString("graphBasename"); int port = config.getInt("port"); int threads = config.getInt("threads"); if (threads == 0) { threads = Runtime.getRuntime().availableProcessors(); } final GraphServer server = new GraphServer(graphBasename, port, threads); server.start(); server.blockUntilShutdown(); } static class TraversalService extends TraversalServiceGrpc.TraversalServiceImplBase { SwhBidirectionalGraph graph; public TraversalService(SwhBidirectionalGraph graph) { this.graph = graph; } @Override public void stats(StatsRequest request, StreamObserver responseObserver) { StatsResponse.Builder response = StatsResponse.newBuilder(); response.setNumNodes(graph.numNodes()); response.setNumEdges(graph.numArcs()); Properties properties = new Properties(); try { properties.load(new FileInputStream(graph.getPath() + ".properties")); properties.load(new FileInputStream(graph.getPath() + ".stats")); } catch (IOException e) { throw new RuntimeException(e); } - response.setCompression(Double.parseDouble(properties.getProperty("compratio"))); + response.setCompressionRatio(Double.parseDouble(properties.getProperty("compratio"))); response.setBitsPerNode(Double.parseDouble(properties.getProperty("bitspernode"))); response.setBitsPerEdge(Double.parseDouble(properties.getProperty("bitsperlink"))); response.setAvgLocality(Double.parseDouble(properties.getProperty("avglocality"))); response.setIndegreeMin(Long.parseLong(properties.getProperty("minindegree"))); response.setIndegreeMax(Long.parseLong(properties.getProperty("maxindegree"))); response.setIndegreeAvg(Double.parseDouble(properties.getProperty("avgindegree"))); response.setOutdegreeMin(Long.parseLong(properties.getProperty("minoutdegree"))); response.setOutdegreeMax(Long.parseLong(properties.getProperty("maxoutdegree"))); response.setOutdegreeAvg(Double.parseDouble(properties.getProperty("avgoutdegree"))); responseObserver.onNext(response.build()); responseObserver.onCompleted(); } @Override public void getNode(GetNodeRequest request, StreamObserver responseObserver) { long nodeId; try { nodeId = graph.getNodeId(new SWHID(request.getSwhid())); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } Node.Builder builder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(graph.getForwardGraph(), request.hasMask() ? request.getMask() : null, builder, nodeId); responseObserver.onNext(builder.build()); responseObserver.onCompleted(); } @Override public void traverse(TraversalRequest request, StreamObserver responseObserver) { SwhBidirectionalGraph g = graph.copy(); Traversal.SimpleTraversal t; try { t = new Traversal.SimpleTraversal(g, request, responseObserver::onNext); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } t.visit(); responseObserver.onCompleted(); } @Override public void findPathTo(FindPathToRequest request, StreamObserver responseObserver) { SwhBidirectionalGraph g = graph.copy(); Traversal.FindPathTo t; try { t = new Traversal.FindPathTo(g, request); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } t.visit(); Path path = t.getPath(); if (path == null) { responseObserver.onError(Status.NOT_FOUND.asException()); } else { responseObserver.onNext(path); responseObserver.onCompleted(); } } @Override public void findPathBetween(FindPathBetweenRequest request, StreamObserver responseObserver) { SwhBidirectionalGraph g = graph.copy(); Traversal.FindPathBetween t; try { t = new Traversal.FindPathBetween(g, request); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } t.visit(); Path path = t.getPath(); if (path == null) { responseObserver.onError(Status.NOT_FOUND.asException()); } else { responseObserver.onNext(path); responseObserver.onCompleted(); } } @Override public void countNodes(TraversalRequest request, StreamObserver responseObserver) { AtomicLong count = new AtomicLong(0); SwhBidirectionalGraph g = graph.copy(); TraversalRequest fixedReq = TraversalRequest.newBuilder(request) // Ignore return fields, just count nodes .setMask(FieldMask.getDefaultInstance()).build(); Traversal.SimpleTraversal t; try { t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.incrementAndGet()); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } t.visit(); CountResponse response = CountResponse.newBuilder().setCount(count.get()).build(); responseObserver.onNext(response); responseObserver.onCompleted(); } @Override public void countEdges(TraversalRequest request, StreamObserver responseObserver) { AtomicLong count = new AtomicLong(0); SwhBidirectionalGraph g = graph.copy(); TraversalRequest fixedReq = TraversalRequest.newBuilder(request) // Force return empty successors to count the edges .setMask(FieldMask.newBuilder().addPaths("num_successors").build()).build(); Traversal.SimpleTraversal t; try { t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.addAndGet(n.getNumSuccessors())); } catch (IllegalArgumentException e) { responseObserver .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException()); return; } t.visit(); CountResponse response = CountResponse.newBuilder().setCount(count.get()).build(); responseObserver.onNext(response); responseObserver.onCompleted(); } } } diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java index 553f603..ba8ed40 100644 --- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java @@ -1,429 +1,429 @@ package org.softwareheritage.graph.rpc; import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; import it.unimi.dsi.big.webgraph.labelling.Label; import org.softwareheritage.graph.*; import java.util.*; public class Traversal { private static ArcLabelledNodeIterator.LabelledArcIterator filterLabelledSuccessors(SwhUnidirectionalGraph g, long nodeId, AllowedEdges allowedEdges) { if (allowedEdges.restrictedTo == null) { // All edges are allowed, bypass edge check return g.labelledSuccessors(nodeId); } else { ArcLabelledNodeIterator.LabelledArcIterator allSuccessors = g.labelledSuccessors(nodeId); return new ArcLabelledNodeIterator.LabelledArcIterator() { @Override public Label label() { return allSuccessors.label(); } @Override public long nextLong() { long neighbor; while ((neighbor = allSuccessors.nextLong()) != -1) { if (allowedEdges.isAllowed(g.getNodeType(nodeId), g.getNodeType(neighbor))) { return neighbor; } } return -1; } @Override public long skip(final long n) { long i = 0; while (i < n && nextLong() != -1) i++; return i; } }; } } private static class NodeFilterChecker { private final SwhUnidirectionalGraph g; private final NodeFilter filter; private final AllowedNodes allowedNodes; private NodeFilterChecker(SwhUnidirectionalGraph graph, NodeFilter filter) { this.g = graph; this.filter = filter; this.allowedNodes = new AllowedNodes(filter.hasTypes() ? filter.getTypes() : "*"); } public boolean allowed(long nodeId) { if (filter == null) { return true; } if (!this.allowedNodes.isAllowed(g.getNodeType(nodeId))) { return false; } return true; } } public static SwhUnidirectionalGraph getDirectedGraph(SwhBidirectionalGraph g, GraphDirection direction) { switch (direction) { case FORWARD: return g.getForwardGraph(); case BACKWARD: return g.getBackwardGraph(); /* * TODO: add support for BOTH case BOTH: return new SwhUnidirectionalGraph(g.symmetrize(), * g.getProperties()); */ default : throw new IllegalArgumentException("Unknown direction: " + direction); } } public static GraphDirection reverseDirection(GraphDirection direction) { switch (direction) { case FORWARD: return GraphDirection.BACKWARD; case BACKWARD: return GraphDirection.FORWARD; /* * TODO: add support for BOTH case BOTH: return GraphDirection.BOTH; */ default : throw new IllegalArgumentException("Unknown direction: " + direction); } } static class StopTraversalException extends RuntimeException { } static class BFSVisitor { protected final SwhUnidirectionalGraph g; protected long depth = 0; protected long traversalSuccessors = 0; protected long edgesAccessed = 0; protected HashMap parents = new HashMap<>(); protected ArrayDeque queue = new ArrayDeque<>(); private long maxDepth = -1; private long maxEdges = -1; BFSVisitor(SwhUnidirectionalGraph g) { this.g = g; } public void addSource(long nodeId) { queue.add(nodeId); parents.put(nodeId, -1L); } public void setMaxDepth(long depth) { maxDepth = depth; } public void setMaxEdges(long edges) { maxEdges = edges; } public void visitSetup() { edgesAccessed = 0; depth = 0; queue.add(-1L); // depth sentinel } public void visit() { visitSetup(); while (!queue.isEmpty()) { visitStep(); } } public void visitStep() { try { assert !queue.isEmpty(); long curr = queue.poll(); if (curr == -1L) { ++depth; if (!queue.isEmpty()) { queue.add(-1L); visitStep(); } return; } if (maxDepth >= 0 && depth > maxDepth) { throw new StopTraversalException(); } edgesAccessed += g.outdegree(curr); if (maxEdges >= 0 && edgesAccessed > maxEdges) { throw new StopTraversalException(); } visitNode(curr); } catch (StopTraversalException e) { // Traversal is over, clear the to-do queue. queue.clear(); } } protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return g.labelledSuccessors(nodeId); } protected void visitNode(long node) { ArcLabelledNodeIterator.LabelledArcIterator it = getSuccessors(node); traversalSuccessors = 0; for (long succ; (succ = it.nextLong()) != -1;) { traversalSuccessors++; visitEdge(node, succ, it.label()); } } protected void visitEdge(long src, long dst, Label label) { if (!parents.containsKey(dst)) { queue.add(dst); parents.put(dst, src); } } } static class SimpleTraversal extends BFSVisitor { private final NodeFilterChecker nodeReturnChecker; private final AllowedEdges allowedEdges; private final TraversalRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final NodeObserver nodeObserver; private Node.Builder nodeBuilder; SimpleTraversal(SwhBidirectionalGraph bidirectionalGraph, TraversalRequest request, NodeObserver nodeObserver) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.nodeObserver = nodeObserver; this.nodeReturnChecker = new NodeFilterChecker(g, request.getReturnNodes()); this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); addSource(srcNodeId); }); if (request.hasMaxDepth()) { setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { setMaxEdges(request.getMaxEdges()); } } @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdges); } @Override public void visitNode(long node) { nodeBuilder = null; if (nodeReturnChecker.allowed(node) && (!request.hasMinDepth() || depth >= request.getMinDepth())) { nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, node); } super.visitNode(node); if (request.getReturnNodes().hasMinTraversalSuccessors() && traversalSuccessors < request.getReturnNodes().getMinTraversalSuccessors() || request.getReturnNodes().hasMaxTraversalSuccessors() && traversalSuccessors > request.getReturnNodes().getMaxTraversalSuccessors()) { nodeBuilder = null; } if (nodeBuilder != null) { nodeObserver.onNext(nodeBuilder.build()); } } @Override protected void visitEdge(long src, long dst, Label label) { super.visitEdge(src, dst, label); NodePropertyBuilder.buildSuccessorProperties(g, nodeDataMask, nodeBuilder, src, dst, label); } } static class FindPathTo extends BFSVisitor { private final AllowedEdges allowedEdges; private final FindPathToRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final NodeFilterChecker targetChecker; private Long targetNode = null; FindPathTo(SwhBidirectionalGraph bidirectionalGraph, FindPathToRequest request) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.targetChecker = new NodeFilterChecker(g, request.getTarget()); this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); if (request.hasMaxDepth()) { setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { setMaxEdges(request.getMaxEdges()); } request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); addSource(srcNodeId); }); } @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdges); } @Override public void visitNode(long node) { if (targetChecker.allowed(node)) { targetNode = node; throw new StopTraversalException(); } super.visitNode(node); } public Path getPath() { if (targetNode == null) { return null; } Path.Builder pathBuilder = Path.newBuilder(); long curNode = targetNode; ArrayList path = new ArrayList<>(); while (curNode != -1) { path.add(curNode); curNode = parents.get(curNode); } Collections.reverse(path); for (long nodeId : path) { Node.Builder nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId); pathBuilder.addNode(nodeBuilder.build()); } return pathBuilder.build(); } } static class FindPathBetween extends BFSVisitor { 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 Long middleNode = null; FindPathBetween(SwhBidirectionalGraph bidirectionalGraph, FindPathBetweenRequest request) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); GraphDirection direction = request.getDirection(); GraphDirection directionReverse = request.hasDirectionReverse() ? request.getDirectionReverse() : reverseDirection(request.getDirection()); SwhUnidirectionalGraph srcGraph = getDirectedGraph(bidirectionalGraph, direction); SwhUnidirectionalGraph dstGraph = getDirectedGraph(bidirectionalGraph, directionReverse); this.allowedEdgesSrc = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); this.allowedEdgesDst = request.hasEdgesReverse() ? new AllowedEdges(request.getEdgesReverse()) : (request.hasEdges() ? (direction == directionReverse ? new AllowedEdges(request.getEdges()) : new AllowedEdges(request.getEdges()).reverse()) : new AllowedEdges("*")); this.srcVisitor = new BFSVisitor(srcGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesSrc); } @Override public void visitNode(long node) { if (dstVisitor.parents.containsKey(node)) { middleNode = node; throw new StopTraversalException(); } super.visitNode(node); } }; this.dstVisitor = new BFSVisitor(dstGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesDst); } @Override public void visitNode(long node) { if (srcVisitor.parents.containsKey(node)) { middleNode = node; throw new StopTraversalException(); } super.visitNode(node); } }; if (request.hasMaxDepth()) { this.srcVisitor.setMaxDepth(request.getMaxDepth()); this.dstVisitor.setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { this.srcVisitor.setMaxEdges(request.getMaxEdges()); this.dstVisitor.setMaxEdges(request.getMaxEdges()); } request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); srcVisitor.addSource(srcNodeId); }); request.getDstList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); dstVisitor.addSource(srcNodeId); }); } @Override public void visit() { srcVisitor.visitSetup(); dstVisitor.visitSetup(); while (!srcVisitor.queue.isEmpty() || !dstVisitor.queue.isEmpty()) { if (!srcVisitor.queue.isEmpty()) { srcVisitor.visitStep(); } if (!dstVisitor.queue.isEmpty()) { dstVisitor.visitStep(); } } } public Path getPath() { if (middleNode == null) { return null; } Path.Builder pathBuilder = Path.newBuilder(); ArrayList path = new ArrayList<>(); long curNode = middleNode; while (curNode != -1) { path.add(curNode); curNode = srcVisitor.parents.get(curNode); } - pathBuilder.setMiddleNodeIndex(path.size() - 1); + pathBuilder.setMidpointIndex(path.size() - 1); Collections.reverse(path); curNode = dstVisitor.parents.get(middleNode); while (curNode != -1) { path.add(curNode); curNode = dstVisitor.parents.get(curNode); } for (long nodeId : path) { Node.Builder nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId); pathBuilder.addNode(nodeBuilder.build()); } return pathBuilder.build(); } } public interface NodeObserver { void onNext(Node nodeId); } } diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java index 7a7b682..be76492 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java @@ -1,203 +1,203 @@ package org.softwareheritage.graph.rpc; import io.grpc.Status; import io.grpc.StatusRuntimeException; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; import org.softwareheritage.graph.SWHID; import java.util.ArrayList; import java.util.List; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertThrows; public class FindPathBetweenTest extends TraversalServiceTest { private FindPathBetweenRequest.Builder getRequestBuilder(SWHID src, SWHID dst) { return FindPathBetweenRequest.newBuilder().addSrc(src.toString()).addDst(dst.toString()); } @Test public void testSwhidErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client .findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(TEST_ORIGIN_ID) .addDst("swh:1:cnt:000000000000000000000000000000000000000z").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } @Test public void testEdgeErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc(TEST_ORIGIN_ID).addDst(TEST_ORIGIN_ID).setEdges("batracien:reptile").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } // Test path between ori 1 and cnt 4 (forward graph) @Test public void forwardRootToLeaf() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 4)).build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9), fakeSWHID("dir", 8), fakeSWHID("dir", 6), fakeSWHID("cnt", 4)); Assertions.assertEquals(expected, actual); } // Test path between rev 18 and rev 3 (forward graph) @Test public void forwardRevToRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 18), fakeSWHID("rev", 3)).build())); List expected = List.of(fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("rev", 9), fakeSWHID("rev", 3)); Assertions.assertEquals(expected, actual); } // Test path between rev 3 and rev 18 (backward graph) @Test public void backwardRevToRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 3), fakeSWHID("rev", 18)) .setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13), fakeSWHID("rev", 18)); Assertions.assertEquals(expected, actual); } // Test path between cnt 4 and itself (forward graph) @Test public void forwardCntToItself() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 4)).build())); List expected = List.of(fakeSWHID("cnt", 4)); Assertions.assertEquals(expected, actual); } // Start from ori and rel 19 and find cnt 14 or cnt 7 (forward graph) @Test public void forwardMultipleSourcesDest() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 14)) .addSrc(TEST_ORIGIN_ID).addDst(fakeSWHID("cnt", 7).toString()).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("cnt", 14)); } // Start from cnt 4 and cnt 11 and find rev 13 or rev 9 (backward graph) @Test public void backwardMultipleSourcesDest() { ArrayList actual = getSWHIDs(client.findPathBetween( getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 13)).setDirection(GraphDirection.BACKWARD) .addSrc(fakeSWHID("cnt", 11).toString()).addDst(fakeSWHID("rev", 9).toString()).build())); List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13)); Assertions.assertEquals(expected, actual); } // Start from all directories and find the origin (backward graph) @Test public void backwardMultipleSourcesAllDirToOri() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("dir", 2), new SWHID(TEST_ORIGIN_ID)) .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString()) .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString()) .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20), new SWHID(TEST_ORIGIN_ID)); Assertions.assertEquals(expected, actual); } // Start from cnt 4 and find any rev (backward graph) @Test public void backwardCntToAnyRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 3)) .addDst(fakeSWHID("rev", 9).toString()).addDst(fakeSWHID("rev", 13).toString()) .addDst(fakeSWHID("rev", 18).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("cnt", 4), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("rev", 9)); Assertions.assertEquals(expected, actual); } // Impossible path between rev 9 and cnt 14 @Test public void forwardImpossiblePath() { StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 9), fakeSWHID("cnt", 14)).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); // Reverse direction thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 14), fakeSWHID("rev", 9)) .setDirection(GraphDirection.BACKWARD).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } // Common ancestor between cnt 4 and cnt 15 : rev 18 @Test public void commonAncestorBackwardBackward() { Path p = client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 15)) .setDirection(GraphDirection.BACKWARD).setDirectionReverse(GraphDirection.BACKWARD).build()); ArrayList actual = getSWHIDs(p); SWHID expected = fakeSWHID("rev", 18); - Assertions.assertEquals(expected, actual.get(p.getMiddleNodeIndex())); + Assertions.assertEquals(expected, actual.get(p.getMidpointIndex())); } // Common descendant between rev 13 and rev 3 : cnt 1 (with rev:dir,dir:dir,dir:cnt) @Test public void commonDescendantForwardForward() { Path p = client.findPathBetween( getRequestBuilder(fakeSWHID("rev", 13), fakeSWHID("rev", 3)).setDirection(GraphDirection.FORWARD) .setDirectionReverse(GraphDirection.FORWARD).setEdges("rev:dir,dir:dir,dir:cnt").build()); ArrayList actual = getSWHIDs(p); SWHID expected = fakeSWHID("cnt", 1); - Assertions.assertEquals(expected, actual.get(p.getMiddleNodeIndex())); + Assertions.assertEquals(expected, actual.get(p.getMidpointIndex())); } // Path between rel 19 and cnt 15 with various max depths @Test public void maxDepth() { // Works with max_depth = 2 ArrayList actual = getSWHIDs(client .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(2).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("dir", 16), fakeSWHID("cnt", 15)); Assertions.assertEquals(expected, actual); // Check that it throws NOT_FOUND with max depth = 1 StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween( getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(1).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } // Path between rel 19 and cnt 15 with various max edges @Test public void maxEdges() { // Works with max_edges = 3 ArrayList actual = getSWHIDs(client .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(3).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("dir", 16), fakeSWHID("cnt", 15)); Assertions.assertEquals(expected, actual); // Check that it throws NOT_FOUND with max_edges = 2 StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween( getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(2).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } } diff --git a/proto/swhgraph.proto b/proto/swhgraph.proto index db418d8..ca3c897 100644 --- a/proto/swhgraph.proto +++ b/proto/swhgraph.proto @@ -1,272 +1,316 @@ syntax = "proto3"; import "google/protobuf/field_mask.proto"; option java_multiple_files = true; option java_package = "org.softwareheritage.graph.rpc"; option java_outer_classname = "GraphService"; package swh.graph; +/* Graph traversal service */ service TraversalService { /* GetNode returns a single Node and its properties. */ rpc GetNode (GetNodeRequest) returns (Node); /* Traverse performs a breadth-first graph traversal from a set of source - * nodes, then streams the nodes it encounters, along with their properties. + * nodes, then streams the nodes it encounters (if they match a given + * return filter), along with their properties. */ rpc Traverse (TraversalRequest) returns (stream Node); /* FindPathTo searches for the shortest path between a set of source nodes * and a node that matches a specific *criteria*. + * + * It does so by performing a breadth-first search from the source node, + * until any node that matches the given criteria is found, then follows + * back its parents to return the shortest path from the source set to that + * node. */ rpc FindPathTo (FindPathToRequest) returns (Path); /* FindPathBetween searches for the shortest path between a set of source - * nodes and a set of destination nodes. */ + * nodes and a set of destination nodes. + * + * It does so by performing a *bidirectional breadth-first search*, i.e., + * two parallel breadth-first searches, one from the source set ("src-BFS") + * and one from the destination set ("dst-BFS"), until both searches find a + * common node that joins their visited sets. This node is called the + * "midpoint node". + * The path returned is the path src -> ... -> midpoint * -> ... -> dst, + * which is the shortest path between src and dst. + * + * The graph direction of both BFS can be configured separately. By + * default, the dst-BFS will use the graph in the opposite direction than + * the src-BFS (if direction = FORWARD, by default direction_reverse = + * BACKWARD, and vice-versa). The default behavior is thus to search for + * the shortest path between two nodes in a given direction. However, one + * can also specify FORWARD or BACKWARD for *both* the src-BFS and the + * dst-BFS. This will search for a common descendant or a common ancestor + * between the two sets, respectively. These will be the midpoints of the + * returned path. + */ rpc FindPathBetween (FindPathBetweenRequest) returns (Path); /* CountNodes does the same as Traverse, but only returns the number of * nodes accessed during the traversal. */ rpc CountNodes (TraversalRequest) returns (CountResponse); /* CountEdges does the same as Traverse, but only returns the number of * edges accessed during the traversal. */ rpc CountEdges (TraversalRequest) returns (CountResponse); /* Stats returns various */ rpc Stats (StatsRequest) returns (StatsResponse); } +/* Direction of the graph */ enum GraphDirection { + /* Forward DAG: ori -> snp -> rel -> rev -> dir -> cnt */ FORWARD = 0; + /* Transposed DAG: cnt -> dir -> rev -> rel -> snp -> ori */ BACKWARD = 1; } /* Describe a node to return */ message GetNodeRequest { /* SWHID of the node to return */ string swhid = 1; /* FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). * By default, all fields are returned. */ optional google.protobuf.FieldMask mask = 8; } /* TraversalRequest describes how a breadth-first traversal should be * performed, and what should be returned to the client. */ message TraversalRequest { /* Set of source nodes (SWHIDs) */ repeated string src = 1; /* Direction of the graph to traverse. Defaults to FORWARD. */ GraphDirection direction = 2; /* Edge restriction string (e.g. "rev:dir,dir:cnt"). * Defaults to "*" (all). */ optional string edges = 3; /* Maximum number of edges accessed in the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_edges = 4; /* Do not return nodes with a depth lower than this number. * By default, all depths are returned. */ optional int64 min_depth = 5; /* Maximum depth of the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_depth = 6; /* Filter which nodes will be sent to the stream. By default, all nodes are * returned. */ optional NodeFilter return_nodes = 7; /* FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). * By default, all fields are returned. */ optional google.protobuf.FieldMask mask = 8; } /* FindPathToRequest describes a request to find the shortest path between a * set of nodes and a given target criteria, as well as what should be returned * in the path. */ message FindPathToRequest { /* Set of source nodes (SWHIDs) */ repeated string src = 1; /* Target criteria, i.e., what constitutes a valid path destination. */ NodeFilter target = 2; /* Direction of the graph to traverse. Defaults to FORWARD. */ GraphDirection direction = 3; /* Edge restriction string (e.g. "rev:dir,dir:cnt"). * Defaults to "*" (all). */ optional string edges = 4; /* Maximum number of edges accessed in the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_edges = 5; /* Maximum depth of the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_depth = 6; /* FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). * By default, all fields are returned. */ optional google.protobuf.FieldMask mask = 7; } /* FindPathToRequest describes a request to find the shortest path between a * set of source nodes and a set of destination nodes. It works by performing a * bidirectional breadth-first traversal from both sets at the same time. */ message FindPathBetweenRequest { /* Set of source nodes (SWHIDs) */ repeated string src = 1; /* Set of destination nodes (SWHIDs) */ repeated string dst = 2; /* Direction of the graph to traverse from the source set. Defaults to * FORWARD. */ GraphDirection direction = 3; /* Direction of the graph to traverse from the destination set. Defaults to * the opposite of `direction`. If direction and direction_reverse are * identical, it will find the first common successor of both sets in the * given direction. */ optional GraphDirection direction_reverse = 4; /* Edge restriction string for the traversal from the source set. * (e.g. "rev:dir,dir:cnt"). Defaults to "*" (all). */ optional string edges = 5; /* Edge restriction string for the reverse traversal from the destination * set. * If not specified: * - If `edges` is not specified either, defaults to "*" * - If direction == direction_reverse, defaults to `edges` * - If direction != direction_reverse, defaults to the reverse of `edges` * (e.g. "rev:dir" becomes "dir:rev"). */ optional string edges_reverse = 6; /* Maximum number of edges accessed in the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_edges = 7; /* Maximum depth of the traversal, after which it stops. * Defaults to infinite. */ optional int64 max_depth = 8; /* FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). * By default, all fields are returned. */ optional google.protobuf.FieldMask mask = 9; } /* Represents various criteria that make a given node is "valid". A node is * only valid if all the subcriteria present in this message are fulfilled. */ message NodeFilter { /* Node restriction string. (e.g. "dir,cnt,rev"). Defaults to "*" (all). */ optional string types = 1; /* Minimum number of successors encountered *during the traversal*. * Default: no constraint */ optional int64 min_traversal_successors = 2; /* Maximum number of successors encountered *during the traversal*. * Default: no constraint */ optional int64 max_traversal_successors = 3; } /* Represents a node in the graph. */ message Node { /* The SWHID of the graph node. */ string swhid = 1; /* List of relevant successors of this node. */ repeated Successor successor = 2; /* Number of relevant successors. */ optional int64 num_successors = 9; /* Node properties */ oneof data { ContentData cnt = 3; RevisionData rev = 5; ReleaseData rel = 6; OriginData ori = 8; }; } /* Represents a path in the graph. */ message Path { /* List of nodes in the path, from source to destination */ repeated Node node = 1; - /* Index of the "middle node" of the path. For paths obtained in + /* Index of the "midpoint" of the path. For paths obtained with * bidirectional search queries, this is the node that joined the two * sets together. When looking for a common ancestor between two nodes by * performing a FindPathBetween search with two backward graphs, this will * be the index of the common ancestor in the path. */ - optional int32 middle_node_index = 2; + optional int32 midpoint_index = 2; } /* Represents a successor of a given node. */ message Successor { /* The SWHID of the successor */ optional string swhid = 1; /* A list of edge labels for the given edge */ repeated EdgeLabel label = 2; } /* Content node properties */ message ContentData { /* Length of the blob, in bytes */ optional int64 length = 1; /* Whether the content was skipped during ingestion. */ optional bool is_skipped = 2; } /* Revision node properties */ message RevisionData { /* Revision author ID (anonymized) */ optional int64 author = 1; /* UNIX timestamp of the revision date (UTC) */ optional int64 author_date = 2; /* Timezone of the revision author date as an offset from UTC */ optional int32 author_date_offset = 3; /* Revision committer ID (anonymized) */ optional int64 committer = 4; /* UNIX timestamp of the revision committer date (UTC) */ optional int64 committer_date = 5; /* Timezone of the revision committer date as an offset from UTC */ optional int32 committer_date_offset = 6; /* Revision message */ optional bytes message = 7; } /* Release node properties */ message ReleaseData { + /* Release author ID (anonymized) */ optional int64 author = 1; /* UNIX timestamp of the release date (UTC) */ optional int64 author_date = 2; /* Timezone of the release author date as an offset from UTC */ optional int32 author_date_offset = 3; /* Release name */ optional bytes name = 4; /* Release message */ optional bytes message = 5; } /* Origin node properties */ message OriginData { /* URL of the origin */ optional string url = 1; } message EdgeLabel { /* Directory entry name for directories, branch name for snapshots */ bytes name = 1; /* Entry permission (only set for directories). */ int32 permission = 2; } message CountResponse { int64 count = 1; } message StatsRequest { } message StatsResponse { + /* Number of nodes in the graph */ int64 num_nodes = 1; + /* Number of edges in the graph */ int64 num_edges = 2; - double compression = 3; + /* Ratio between the graph size and the information-theoretical lower + * bound */ + double compression_ratio = 3; + /* Number of bits per node (overall graph size in bits divided by the + * number of nodes) */ double bits_per_node = 4; + /* Number of bits per edge (overall graph size in bits divided by the + * number of arcs). */ double bits_per_edge = 5; double avg_locality = 6; + /* Smallest indegree */ int64 indegree_min = 7; + /* Largest indegree */ int64 indegree_max = 8; + /* Average indegree */ double indegree_avg = 9; + /* Smallest outdegree */ int64 outdegree_min = 10; + /* Largest outdegree */ int64 outdegree_max = 11; + /* Average outdegree */ double outdegree_avg = 12; } diff --git a/swh/graph/http_naive_client.py b/swh/graph/http_naive_client.py index c8bf729..a94efe8 100644 --- a/swh/graph/http_naive_client.py +++ b/swh/graph/http_naive_client.py @@ -1,395 +1,395 @@ # Copyright (C) 2021 The Software Heritage developers # See the AUTHORS file at the top-level directory of this distribution # License: GNU General Public License version 3, or any later version # See top-level LICENSE file for more information import functools import inspect import re import statistics from typing import ( Callable, Dict, Iterable, Iterator, List, Optional, Set, Tuple, TypeVar, Union, ) from swh.model.swhids import CoreSWHID, ExtendedSWHID, ValidationError from .http_client import GraphArgumentException _NODE_TYPES = "ori|snp|rel|rev|dir|cnt" NODES_RE = re.compile(rf"(\*|{_NODE_TYPES})") EDGES_RE = re.compile(rf"(\*|{_NODE_TYPES}):(\*|{_NODE_TYPES})") T = TypeVar("T", bound=Callable) SWHIDlike = Union[CoreSWHID, ExtendedSWHID, str] def check_arguments(f: T) -> T: """Decorator for generic argument checking for methods of NaiveClient. Checks ``src`` is a valid and known SWHID, and ``edges`` has the right format.""" signature = inspect.signature(f) @functools.wraps(f) def newf(*args, **kwargs): __tracebackhide__ = True # for pytest try: bound_args = signature.bind(*args, **kwargs) except TypeError as e: # rethrow the exception from here so pytest doesn't flood the terminal # with signature.bind's call stack. raise TypeError(*e.args) from None self = bound_args.arguments["self"] src = bound_args.arguments.get("src") if src: self._check_swhid(src) edges = bound_args.arguments.get("edges") if edges: if edges != "*" and not EDGES_RE.match(edges): raise GraphArgumentException(f"invalid edge restriction: {edges}") return_types = bound_args.arguments.get("return_types") if return_types: if not NODES_RE.match(return_types): raise GraphArgumentException( f"invalid return_types restriction: {return_types}" ) return f(*args, **kwargs) return newf # type: ignore def filter_node_types(node_types: str, nodes: Iterable[str]) -> Iterator[str]: if node_types == "*": yield from nodes else: prefixes = tuple(f"swh:1:{type_}:" for type_ in node_types.split(",")) for node in nodes: if node.startswith(prefixes): yield node class NaiveClient: """An alternative implementation of the graph server, written in pure-python and meant for simulating it in other components' test cases; constructed from a list of nodes and (directed) edges, both represented as SWHIDs. It is NOT meant to be efficient in any way; only to be a very simple implementation that provides the same behavior. >>> nodes = [ ... "swh:1:rev:1111111111111111111111111111111111111111", ... "swh:1:rev:2222222222222222222222222222222222222222", ... "swh:1:rev:3333333333333333333333333333333333333333", ... ] >>> edges = [ ... ( ... "swh:1:rev:1111111111111111111111111111111111111111", ... "swh:1:rev:2222222222222222222222222222222222222222", ... ), ... ( ... "swh:1:rev:2222222222222222222222222222222222222222", ... "swh:1:rev:3333333333333333333333333333333333333333", ... ), ... ] >>> c = NaiveClient(nodes=nodes, edges=edges) >>> list(c.leaves("swh:1:rev:1111111111111111111111111111111111111111")) ['swh:1:rev:3333333333333333333333333333333333333333'] """ def __init__( self, *, nodes: List[SWHIDlike], edges: List[Tuple[SWHIDlike, SWHIDlike]] ): self.graph = Graph(nodes, edges) def _check_swhid(self, swhid): try: ExtendedSWHID.from_string(swhid) except ValidationError as e: raise GraphArgumentException(*e.args) from None if swhid not in self.graph.nodes: raise GraphArgumentException(f"SWHID not found: {swhid}") def stats(self) -> Dict: return { "num_nodes": len(self.graph.nodes), "num_edges": sum(map(len, self.graph.forward_edges.values())), - "compression": 1.0, + "compression_ratio": 1.0, "bits_per_edge": 100.0, "bits_per_node": 100.0, "avg_locality": 0.0, "indegree_min": min(map(len, self.graph.backward_edges.values())), "indegree_max": max(map(len, self.graph.backward_edges.values())), "indegree_avg": statistics.mean( map(len, self.graph.backward_edges.values()) ), "outdegree_min": min(map(len, self.graph.forward_edges.values())), "outdegree_max": max(map(len, self.graph.forward_edges.values())), "outdegree_avg": statistics.mean( map(len, self.graph.forward_edges.values()) ), } @check_arguments def leaves( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, [ node for node in self.graph.get_subgraph(src, edges, direction) if not self.graph.get_filtered_neighbors(node, edges, direction) ], ) @check_arguments def neighbors( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, self.graph.get_filtered_neighbors(src, edges, direction) ) @check_arguments def visit_nodes( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, self.graph.get_subgraph(src, edges, direction) ) @check_arguments def visit_edges( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0 ) -> Iterator[Tuple[str, str]]: if max_edges == 0: max_edges = None # type: ignore else: max_edges -= 1 yield from list(self.graph.iter_edges_dfs(direction, edges, src))[:max_edges] @check_arguments def visit_paths( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0 ) -> Iterator[List[str]]: # TODO: max_edges for path in self.graph.iter_paths_dfs(direction, edges, src): if path[-1] in self.leaves(src, edges, direction): yield list(path) @check_arguments def walk( self, src: str, dst: str, edges: str = "*", traversal: str = "dfs", direction: str = "forward", limit: Optional[int] = None, ) -> Iterator[str]: # TODO: implement algo="bfs" # TODO: limit match_path: Callable[[str], bool] if ":" in dst: match_path = dst.__eq__ self._check_swhid(dst) else: match_path = lambda node: node.startswith(f"swh:1:{dst}:") # noqa for path in self.graph.iter_paths_dfs(direction, edges, src): if match_path(path[-1]): if not limit: # 0 or None yield from path elif limit > 0: yield from path[0:limit] else: yield from path[limit:] @check_arguments def random_walk( self, src: str, dst: str, edges: str = "*", direction: str = "forward", limit: Optional[int] = None, ): # TODO: limit yield from self.walk(src, dst, edges, "dfs", direction, limit) @check_arguments def count_leaves( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(list(self.leaves(src, edges, direction))) @check_arguments def count_neighbors( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(self.graph.get_filtered_neighbors(src, edges, direction)) @check_arguments def count_visit_nodes( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(self.graph.get_subgraph(src, edges, direction)) class Graph: def __init__( self, nodes: List[SWHIDlike], edges: List[Tuple[SWHIDlike, SWHIDlike]] ): self.nodes = [str(node) for node in nodes] self.forward_edges: Dict[str, List[str]] = {} self.backward_edges: Dict[str, List[str]] = {} for node in nodes: self.forward_edges[str(node)] = [] self.backward_edges[str(node)] = [] for (src, dst) in edges: self.forward_edges[str(src)].append(str(dst)) self.backward_edges[str(dst)].append(str(src)) def get_filtered_neighbors( self, src: str, edges_fmt: str, direction: str, ) -> Set[str]: if direction == "forward": edges = self.forward_edges elif direction == "backward": edges = self.backward_edges else: raise GraphArgumentException(f"invalid direction: {direction}") neighbors = edges.get(src, []) if edges_fmt == "*": return set(neighbors) else: filtered_neighbors: Set[str] = set() for edges_fmt_item in edges_fmt.split(","): (src_fmt, dst_fmt) = edges_fmt_item.split(":") if src_fmt != "*" and not src.startswith(f"swh:1:{src_fmt}:"): continue if dst_fmt == "*": filtered_neighbors.update(neighbors) else: prefix = f"swh:1:{dst_fmt}:" filtered_neighbors.update( n for n in neighbors if n.startswith(prefix) ) return filtered_neighbors def get_subgraph(self, src: str, edges_fmt: str, direction: str) -> Set[str]: seen = set() to_visit = {src} while to_visit: node = to_visit.pop() seen.add(node) neighbors = set(self.get_filtered_neighbors(node, edges_fmt, direction)) new_nodes = neighbors - seen to_visit.update(new_nodes) return seen def iter_paths_dfs( self, direction: str, edges_fmt: str, src: str ) -> Iterator[Tuple[str, ...]]: for (path, node) in DfsSubgraphIterator(self, direction, edges_fmt, src): yield path + (node,) def iter_edges_dfs( self, direction: str, edges_fmt: str, src: str ) -> Iterator[Tuple[str, str]]: for (path, node) in DfsSubgraphIterator(self, direction, edges_fmt, src): if len(path) > 0: yield (path[-1], node) class SubgraphIterator(Iterator[Tuple[Tuple[str, ...], str]]): def __init__(self, graph: Graph, direction: str, edges_fmt: str, src: str): self.graph = graph self.direction = direction self.edges_fmt = edges_fmt self.seen: Set[str] = set() self.src = src def more_work(self) -> bool: raise NotImplementedError() def pop(self) -> Tuple[Tuple[str, ...], str]: raise NotImplementedError() def push(self, new_path: Tuple[str, ...], neighbor: str) -> None: raise NotImplementedError() def __next__(self) -> Tuple[Tuple[str, ...], str]: # Stores (path, next_node) if not self.more_work(): raise StopIteration() (path, node) = self.pop() new_path = path + (node,) if node not in self.seen: neighbors = self.graph.get_filtered_neighbors( node, self.edges_fmt, self.direction ) # We want to visit the first neighbor first, and to_visit is a stack; # so we need to reversed() the list of neighbors to get it on top # of the stack. for neighbor in reversed(list(neighbors)): self.push(new_path, neighbor) self.seen.add(node) return (path, node) class DfsSubgraphIterator(SubgraphIterator): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.to_visit: List[Tuple[Tuple[str, ...], str]] = [((), self.src)] def more_work(self) -> bool: return bool(self.to_visit) def pop(self) -> Tuple[Tuple[str, ...], str]: return self.to_visit.pop() def push(self, new_path: Tuple[str, ...], neighbor: str) -> None: self.to_visit.append((new_path, neighbor)) diff --git a/swh/graph/rpc/swhgraph_pb2.py b/swh/graph/rpc/swhgraph_pb2.py index 04e45ce..b48ad97 100644 --- a/swh/graph/rpc/swhgraph_pb2.py +++ b/swh/graph/rpc/swhgraph_pb2.py @@ -1,196 +1,196 @@ # -*- coding: utf-8 -*- # Generated by the protocol buffer compiler. DO NOT EDIT! # source: swh/graph/rpc/swhgraph.proto """Generated protocol buffer code.""" from google.protobuf.internal import enum_type_wrapper from google.protobuf import descriptor as _descriptor from google.protobuf import descriptor_pool as _descriptor_pool from google.protobuf import message as _message from google.protobuf import reflection as _reflection from google.protobuf import symbol_database as _symbol_database # @@protoc_insertion_point(imports) _sym_db = _symbol_database.Default() from google.protobuf import field_mask_pb2 as google_dot_protobuf_dot_field__mask__pb2 -DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x1cswh/graph/rpc/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\"\xd8\x02\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\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_mask\"\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\"[\n\x04Path\x12\x1d\n\x04node\x18\x01 \x03(\x0b\x32\x0f.swh.graph.Node\x12\x1e\n\x11middle_node_index\x18\x02 \x01(\x05H\x00\x88\x01\x01\x42\x14\n\x12_middle_node_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\"\x95\x02\n\rStatsResponse\x12\x11\n\tnum_nodes\x18\x01 \x01(\x03\x12\x11\n\tnum_edges\x18\x02 \x01(\x03\x12\x13\n\x0b\x63ompression\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\x1cswh/graph/rpc/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\"\xd8\x02\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\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_mask\"\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') _GRAPHDIRECTION = DESCRIPTOR.enum_types_by_name['GraphDirection'] GraphDirection = enum_type_wrapper.EnumTypeWrapper(_GRAPHDIRECTION) FORWARD = 0 BACKWARD = 1 _GETNODEREQUEST = DESCRIPTOR.message_types_by_name['GetNodeRequest'] _TRAVERSALREQUEST = DESCRIPTOR.message_types_by_name['TraversalRequest'] _FINDPATHTOREQUEST = DESCRIPTOR.message_types_by_name['FindPathToRequest'] _FINDPATHBETWEENREQUEST = DESCRIPTOR.message_types_by_name['FindPathBetweenRequest'] _NODEFILTER = DESCRIPTOR.message_types_by_name['NodeFilter'] _NODE = DESCRIPTOR.message_types_by_name['Node'] _PATH = DESCRIPTOR.message_types_by_name['Path'] _SUCCESSOR = DESCRIPTOR.message_types_by_name['Successor'] _CONTENTDATA = DESCRIPTOR.message_types_by_name['ContentData'] _REVISIONDATA = DESCRIPTOR.message_types_by_name['RevisionData'] _RELEASEDATA = DESCRIPTOR.message_types_by_name['ReleaseData'] _ORIGINDATA = DESCRIPTOR.message_types_by_name['OriginData'] _EDGELABEL = DESCRIPTOR.message_types_by_name['EdgeLabel'] _COUNTRESPONSE = DESCRIPTOR.message_types_by_name['CountResponse'] _STATSREQUEST = DESCRIPTOR.message_types_by_name['StatsRequest'] _STATSRESPONSE = DESCRIPTOR.message_types_by_name['StatsResponse'] GetNodeRequest = _reflection.GeneratedProtocolMessageType('GetNodeRequest', (_message.Message,), { 'DESCRIPTOR' : _GETNODEREQUEST, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.GetNodeRequest) }) _sym_db.RegisterMessage(GetNodeRequest) TraversalRequest = _reflection.GeneratedProtocolMessageType('TraversalRequest', (_message.Message,), { 'DESCRIPTOR' : _TRAVERSALREQUEST, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.TraversalRequest) }) _sym_db.RegisterMessage(TraversalRequest) FindPathToRequest = _reflection.GeneratedProtocolMessageType('FindPathToRequest', (_message.Message,), { 'DESCRIPTOR' : _FINDPATHTOREQUEST, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.FindPathToRequest) }) _sym_db.RegisterMessage(FindPathToRequest) FindPathBetweenRequest = _reflection.GeneratedProtocolMessageType('FindPathBetweenRequest', (_message.Message,), { 'DESCRIPTOR' : _FINDPATHBETWEENREQUEST, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.FindPathBetweenRequest) }) _sym_db.RegisterMessage(FindPathBetweenRequest) NodeFilter = _reflection.GeneratedProtocolMessageType('NodeFilter', (_message.Message,), { 'DESCRIPTOR' : _NODEFILTER, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.NodeFilter) }) _sym_db.RegisterMessage(NodeFilter) Node = _reflection.GeneratedProtocolMessageType('Node', (_message.Message,), { 'DESCRIPTOR' : _NODE, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.Node) }) _sym_db.RegisterMessage(Node) Path = _reflection.GeneratedProtocolMessageType('Path', (_message.Message,), { 'DESCRIPTOR' : _PATH, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.Path) }) _sym_db.RegisterMessage(Path) Successor = _reflection.GeneratedProtocolMessageType('Successor', (_message.Message,), { 'DESCRIPTOR' : _SUCCESSOR, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.Successor) }) _sym_db.RegisterMessage(Successor) ContentData = _reflection.GeneratedProtocolMessageType('ContentData', (_message.Message,), { 'DESCRIPTOR' : _CONTENTDATA, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.ContentData) }) _sym_db.RegisterMessage(ContentData) RevisionData = _reflection.GeneratedProtocolMessageType('RevisionData', (_message.Message,), { 'DESCRIPTOR' : _REVISIONDATA, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.RevisionData) }) _sym_db.RegisterMessage(RevisionData) ReleaseData = _reflection.GeneratedProtocolMessageType('ReleaseData', (_message.Message,), { 'DESCRIPTOR' : _RELEASEDATA, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.ReleaseData) }) _sym_db.RegisterMessage(ReleaseData) OriginData = _reflection.GeneratedProtocolMessageType('OriginData', (_message.Message,), { 'DESCRIPTOR' : _ORIGINDATA, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.OriginData) }) _sym_db.RegisterMessage(OriginData) EdgeLabel = _reflection.GeneratedProtocolMessageType('EdgeLabel', (_message.Message,), { 'DESCRIPTOR' : _EDGELABEL, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.EdgeLabel) }) _sym_db.RegisterMessage(EdgeLabel) CountResponse = _reflection.GeneratedProtocolMessageType('CountResponse', (_message.Message,), { 'DESCRIPTOR' : _COUNTRESPONSE, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.CountResponse) }) _sym_db.RegisterMessage(CountResponse) StatsRequest = _reflection.GeneratedProtocolMessageType('StatsRequest', (_message.Message,), { 'DESCRIPTOR' : _STATSREQUEST, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.StatsRequest) }) _sym_db.RegisterMessage(StatsRequest) StatsResponse = _reflection.GeneratedProtocolMessageType('StatsResponse', (_message.Message,), { 'DESCRIPTOR' : _STATSRESPONSE, '__module__' : 'swh.graph.rpc.swhgraph_pb2' # @@protoc_insertion_point(class_scope:swh.graph.StatsResponse) }) _sym_db.RegisterMessage(StatsResponse) _TRAVERSALSERVICE = DESCRIPTOR.services_by_name['TraversalService'] if _descriptor._USE_C_DESCRIPTORS == False: DESCRIPTOR._options = None DESCRIPTOR._serialized_options = b'\n\036org.softwareheritage.graph.rpcB\014GraphServiceP\001' _GRAPHDIRECTION._serialized_start=2853 _GRAPHDIRECTION._serialized_end=2896 _GETNODEREQUEST._serialized_start=77 _GETNODEREQUEST._serialized_end=164 _TRAVERSALREQUEST._serialized_start=167 _TRAVERSALREQUEST._serialized_end=511 _FINDPATHTOREQUEST._serialized_start=514 _FINDPATHTOREQUEST._serialized_end=793 _FINDPATHBETWEENREQUEST._serialized_start=796 _FINDPATHBETWEENREQUEST._serialized_end=1181 _NODEFILTER._serialized_start=1184 _NODEFILTER._serialized_end=1362 _NODE._serialized_start=1365 _NODE._serialized_end=1639 _PATH._serialized_start=1641 - _PATH._serialized_end=1732 - _SUCCESSOR._serialized_start=1734 - _SUCCESSOR._serialized_end=1812 - _CONTENTDATA._serialized_start=1814 - _CONTENTDATA._serialized_end=1899 - _REVISIONDATA._serialized_start=1902 - _REVISIONDATA._serialized_end=2228 - _RELEASEDATA._serialized_start=2231 - _RELEASEDATA._serialized_end=2436 - _ORIGINDATA._serialized_start=2438 - _ORIGINDATA._serialized_end=2476 - _EDGELABEL._serialized_start=2478 - _EDGELABEL._serialized_end=2523 - _COUNTRESPONSE._serialized_start=2525 - _COUNTRESPONSE._serialized_end=2555 - _STATSREQUEST._serialized_start=2557 - _STATSREQUEST._serialized_end=2571 - _STATSRESPONSE._serialized_start=2574 + _PATH._serialized_end=1726 + _SUCCESSOR._serialized_start=1728 + _SUCCESSOR._serialized_end=1806 + _CONTENTDATA._serialized_start=1808 + _CONTENTDATA._serialized_end=1893 + _REVISIONDATA._serialized_start=1896 + _REVISIONDATA._serialized_end=2222 + _RELEASEDATA._serialized_start=2225 + _RELEASEDATA._serialized_end=2430 + _ORIGINDATA._serialized_start=2432 + _ORIGINDATA._serialized_end=2470 + _EDGELABEL._serialized_start=2472 + _EDGELABEL._serialized_end=2517 + _COUNTRESPONSE._serialized_start=2519 + _COUNTRESPONSE._serialized_end=2549 + _STATSREQUEST._serialized_start=2551 + _STATSREQUEST._serialized_end=2565 + _STATSRESPONSE._serialized_start=2568 _STATSRESPONSE._serialized_end=2851 _TRAVERSALSERVICE._serialized_start=2899 _TRAVERSALSERVICE._serialized_end=3362 # @@protoc_insertion_point(module_scope) diff --git a/swh/graph/rpc/swhgraph_pb2.pyi b/swh/graph/rpc/swhgraph_pb2.pyi index d81177c..140f704 100644 --- a/swh/graph/rpc/swhgraph_pb2.pyi +++ b/swh/graph/rpc/swhgraph_pb2.pyi @@ -1,639 +1,652 @@ """ @generated by mypy-protobuf. Do not edit manually! isort:skip_file """ import builtins import google.protobuf.descriptor import google.protobuf.field_mask_pb2 import google.protobuf.internal.containers import google.protobuf.internal.enum_type_wrapper import google.protobuf.message import typing import typing_extensions DESCRIPTOR: google.protobuf.descriptor.FileDescriptor class _GraphDirection: ValueType = typing.NewType('ValueType', builtins.int) V: typing_extensions.TypeAlias = ValueType class _GraphDirectionEnumTypeWrapper(google.protobuf.internal.enum_type_wrapper._EnumTypeWrapper[_GraphDirection.ValueType], builtins.type): DESCRIPTOR: google.protobuf.descriptor.EnumDescriptor FORWARD: _GraphDirection.ValueType # 0 BACKWARD: _GraphDirection.ValueType # 1 class GraphDirection(_GraphDirection, metaclass=_GraphDirectionEnumTypeWrapper): pass FORWARD: GraphDirection.ValueType # 0 BACKWARD: GraphDirection.ValueType # 1 global___GraphDirection = GraphDirection class GetNodeRequest(google.protobuf.message.Message): + """Describe a node to return""" DESCRIPTOR: google.protobuf.descriptor.Descriptor SWHID_FIELD_NUMBER: builtins.int MASK_FIELD_NUMBER: builtins.int swhid: typing.Text + """SWHID of the node to return""" + @property - def mask(self) -> google.protobuf.field_mask_pb2.FieldMask: ... + def mask(self) -> google.protobuf.field_mask_pb2.FieldMask: + """FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). + By default, all fields are returned. + """ + pass def __init__(self, *, swhid: typing.Text = ..., mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_mask",b"_mask","mask",b"mask"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_mask",b"_mask","mask",b"mask","swhid",b"swhid"]) -> None: ... def WhichOneof(self, oneof_group: typing_extensions.Literal["_mask",b"_mask"]) -> typing.Optional[typing_extensions.Literal["mask"]]: ... global___GetNodeRequest = GetNodeRequest class TraversalRequest(google.protobuf.message.Message): """TraversalRequest describes how a breadth-first traversal should be performed, and what should be returned to the client. """ DESCRIPTOR: google.protobuf.descriptor.Descriptor SRC_FIELD_NUMBER: builtins.int DIRECTION_FIELD_NUMBER: builtins.int EDGES_FIELD_NUMBER: builtins.int MAX_EDGES_FIELD_NUMBER: builtins.int MIN_DEPTH_FIELD_NUMBER: builtins.int MAX_DEPTH_FIELD_NUMBER: builtins.int RETURN_NODES_FIELD_NUMBER: builtins.int MASK_FIELD_NUMBER: builtins.int @property def src(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]: - """Set of source nodes""" + """Set of source nodes (SWHIDs)""" pass direction: global___GraphDirection.ValueType """Direction of the graph to traverse. Defaults to FORWARD.""" edges: typing.Text """Edge restriction string (e.g. "rev:dir,dir:cnt"). Defaults to "*" (all). """ max_edges: builtins.int """Maximum number of edges accessed in the traversal, after which it stops. Defaults to infinite. """ min_depth: builtins.int """Do not return nodes with a depth lower than this number. By default, all depths are returned. """ max_depth: builtins.int """Maximum depth of the traversal, after which it stops. Defaults to infinite. """ @property def return_nodes(self) -> global___NodeFilter: """Filter which nodes will be sent to the stream. By default, all nodes are returned. """ pass @property def mask(self) -> google.protobuf.field_mask_pb2.FieldMask: """FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). By default, all fields are returned. """ pass def __init__(self, *, src: typing.Optional[typing.Iterable[typing.Text]] = ..., direction: global___GraphDirection.ValueType = ..., edges: typing.Optional[typing.Text] = ..., max_edges: typing.Optional[builtins.int] = ..., min_depth: typing.Optional[builtins.int] = ..., max_depth: typing.Optional[builtins.int] = ..., return_nodes: typing.Optional[global___NodeFilter] = ..., mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ..., ) -> 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","_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","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","_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","min_depth",b"min_depth","return_nodes",b"return_nodes","src",b"src"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges",b"_edges"]) -> typing.Optional[typing_extensions.Literal["edges"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_mask",b"_mask"]) -> typing.Optional[typing_extensions.Literal["mask"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_depth",b"_max_depth"]) -> typing.Optional[typing_extensions.Literal["max_depth"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_edges",b"_max_edges"]) -> typing.Optional[typing_extensions.Literal["max_edges"]]: ... @typing.overload 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"]]: ... global___TraversalRequest = TraversalRequest class FindPathToRequest(google.protobuf.message.Message): """FindPathToRequest describes a request to find the shortest path between a set of nodes and a given target criteria, as well as what should be returned in the path. """ DESCRIPTOR: google.protobuf.descriptor.Descriptor SRC_FIELD_NUMBER: builtins.int TARGET_FIELD_NUMBER: builtins.int DIRECTION_FIELD_NUMBER: builtins.int EDGES_FIELD_NUMBER: builtins.int MAX_EDGES_FIELD_NUMBER: builtins.int MAX_DEPTH_FIELD_NUMBER: builtins.int MASK_FIELD_NUMBER: builtins.int @property def src(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]: - """Set of source nodes""" + """Set of source nodes (SWHIDs)""" pass @property def target(self) -> global___NodeFilter: """Target criteria, i.e., what constitutes a valid path destination.""" pass direction: global___GraphDirection.ValueType """Direction of the graph to traverse. Defaults to FORWARD.""" edges: typing.Text """Edge restriction string (e.g. "rev:dir,dir:cnt"). Defaults to "*" (all). """ max_edges: builtins.int """Maximum number of edges accessed in the traversal, after which it stops. Defaults to infinite. """ max_depth: builtins.int """Maximum depth of the traversal, after which it stops. Defaults to infinite. """ @property def mask(self) -> google.protobuf.field_mask_pb2.FieldMask: """FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). By default, all fields are returned. """ pass def __init__(self, *, src: typing.Optional[typing.Iterable[typing.Text]] = ..., target: typing.Optional[global___NodeFilter] = ..., direction: global___GraphDirection.ValueType = ..., edges: typing.Optional[typing.Text] = ..., max_edges: typing.Optional[builtins.int] = ..., max_depth: typing.Optional[builtins.int] = ..., mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ..., ) -> 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","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","target",b"target"]) -> 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","direction",b"direction","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","src",b"src","target",b"target"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges",b"_edges"]) -> typing.Optional[typing_extensions.Literal["edges"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_mask",b"_mask"]) -> typing.Optional[typing_extensions.Literal["mask"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_depth",b"_max_depth"]) -> typing.Optional[typing_extensions.Literal["max_depth"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_edges",b"_max_edges"]) -> typing.Optional[typing_extensions.Literal["max_edges"]]: ... global___FindPathToRequest = FindPathToRequest class FindPathBetweenRequest(google.protobuf.message.Message): """FindPathToRequest describes a request to find the shortest path between a set of source nodes and a set of destination nodes. It works by performing a bidirectional breadth-first traversal from both sets at the same time. """ DESCRIPTOR: google.protobuf.descriptor.Descriptor SRC_FIELD_NUMBER: builtins.int DST_FIELD_NUMBER: builtins.int DIRECTION_FIELD_NUMBER: builtins.int DIRECTION_REVERSE_FIELD_NUMBER: builtins.int EDGES_FIELD_NUMBER: builtins.int EDGES_REVERSE_FIELD_NUMBER: builtins.int MAX_EDGES_FIELD_NUMBER: builtins.int MAX_DEPTH_FIELD_NUMBER: builtins.int MASK_FIELD_NUMBER: builtins.int @property def src(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]: - """Set of source nodes""" + """Set of source nodes (SWHIDs)""" pass @property def dst(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]: - """Set of destination nodes""" + """Set of destination nodes (SWHIDs)""" pass direction: global___GraphDirection.ValueType """Direction of the graph to traverse from the source set. Defaults to FORWARD. """ direction_reverse: global___GraphDirection.ValueType """Direction of the graph to traverse from the destination set. Defaults to the opposite of `direction`. If direction and direction_reverse are identical, it will find the first common successor of both sets in the given direction. """ edges: typing.Text """Edge restriction string for the traversal from the source set. (e.g. "rev:dir,dir:cnt"). Defaults to "*" (all). """ edges_reverse: typing.Text """Edge restriction string for the reverse traversal from the destination set. If not specified: - If `edges` is not specified either, defaults to "*" - If direction == direction_reverse, defaults to `edges` - If direction != direction_reverse, defaults to the reverse of `edges` (e.g. "rev:dir" becomes "dir:rev"). """ max_edges: builtins.int """Maximum number of edges accessed in the traversal, after which it stops. Defaults to infinite. """ max_depth: builtins.int """Maximum depth of the traversal, after which it stops. Defaults to infinite. """ @property def mask(self) -> google.protobuf.field_mask_pb2.FieldMask: """FieldMask of which fields are to be returned (e.g., "swhid,cnt.length"). By default, all fields are returned. """ pass def __init__(self, *, src: typing.Optional[typing.Iterable[typing.Text]] = ..., dst: typing.Optional[typing.Iterable[typing.Text]] = ..., direction: global___GraphDirection.ValueType = ..., direction_reverse: typing.Optional[global___GraphDirection.ValueType] = ..., edges: typing.Optional[typing.Text] = ..., edges_reverse: typing.Optional[typing.Text] = ..., max_edges: typing.Optional[builtins.int] = ..., max_depth: typing.Optional[builtins.int] = ..., mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_direction_reverse",b"_direction_reverse","_edges",b"_edges","_edges_reverse",b"_edges_reverse","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","direction_reverse",b"direction_reverse","edges",b"edges","edges_reverse",b"edges_reverse","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_direction_reverse",b"_direction_reverse","_edges",b"_edges","_edges_reverse",b"_edges_reverse","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","direction",b"direction","direction_reverse",b"direction_reverse","dst",b"dst","edges",b"edges","edges_reverse",b"edges_reverse","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","src",b"src"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_direction_reverse",b"_direction_reverse"]) -> typing.Optional[typing_extensions.Literal["direction_reverse"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges",b"_edges"]) -> typing.Optional[typing_extensions.Literal["edges"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges_reverse",b"_edges_reverse"]) -> typing.Optional[typing_extensions.Literal["edges_reverse"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_mask",b"_mask"]) -> typing.Optional[typing_extensions.Literal["mask"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_depth",b"_max_depth"]) -> typing.Optional[typing_extensions.Literal["max_depth"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_edges",b"_max_edges"]) -> typing.Optional[typing_extensions.Literal["max_edges"]]: ... global___FindPathBetweenRequest = FindPathBetweenRequest class NodeFilter(google.protobuf.message.Message): """Represents various criteria that make a given node is "valid". A node is only valid if all the subcriteria present in this message are fulfilled. """ DESCRIPTOR: google.protobuf.descriptor.Descriptor TYPES_FIELD_NUMBER: builtins.int MIN_TRAVERSAL_SUCCESSORS_FIELD_NUMBER: builtins.int MAX_TRAVERSAL_SUCCESSORS_FIELD_NUMBER: builtins.int types: typing.Text """Node restriction string. (e.g. "dir,cnt,rev"). Defaults to "*" (all).""" min_traversal_successors: builtins.int """Minimum number of successors encountered *during the traversal*. Default: no constraint """ max_traversal_successors: builtins.int """Maximum number of successors encountered *during the traversal*. Default: no constraint """ def __init__(self, *, types: typing.Optional[typing.Text] = ..., min_traversal_successors: typing.Optional[builtins.int] = ..., max_traversal_successors: typing.Optional[builtins.int] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_max_traversal_successors",b"_max_traversal_successors","_min_traversal_successors",b"_min_traversal_successors","_types",b"_types","max_traversal_successors",b"max_traversal_successors","min_traversal_successors",b"min_traversal_successors","types",b"types"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_max_traversal_successors",b"_max_traversal_successors","_min_traversal_successors",b"_min_traversal_successors","_types",b"_types","max_traversal_successors",b"max_traversal_successors","min_traversal_successors",b"min_traversal_successors","types",b"types"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_traversal_successors",b"_max_traversal_successors"]) -> typing.Optional[typing_extensions.Literal["max_traversal_successors"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_min_traversal_successors",b"_min_traversal_successors"]) -> typing.Optional[typing_extensions.Literal["min_traversal_successors"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_types",b"_types"]) -> typing.Optional[typing_extensions.Literal["types"]]: ... global___NodeFilter = NodeFilter class Node(google.protobuf.message.Message): """Represents a node in the graph.""" DESCRIPTOR: google.protobuf.descriptor.Descriptor SWHID_FIELD_NUMBER: builtins.int SUCCESSOR_FIELD_NUMBER: builtins.int NUM_SUCCESSORS_FIELD_NUMBER: builtins.int CNT_FIELD_NUMBER: builtins.int REV_FIELD_NUMBER: builtins.int REL_FIELD_NUMBER: builtins.int ORI_FIELD_NUMBER: builtins.int swhid: typing.Text """The SWHID of the graph node.""" @property def successor(self) -> google.protobuf.internal.containers.RepeatedCompositeFieldContainer[global___Successor]: """List of relevant successors of this node.""" pass num_successors: builtins.int """Number of relevant successors.""" @property def cnt(self) -> global___ContentData: ... @property def rev(self) -> global___RevisionData: ... @property def rel(self) -> global___ReleaseData: ... @property def ori(self) -> global___OriginData: ... def __init__(self, *, swhid: typing.Text = ..., successor: typing.Optional[typing.Iterable[global___Successor]] = ..., num_successors: typing.Optional[builtins.int] = ..., cnt: typing.Optional[global___ContentData] = ..., rev: typing.Optional[global___RevisionData] = ..., rel: typing.Optional[global___ReleaseData] = ..., ori: typing.Optional[global___OriginData] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_num_successors",b"_num_successors","cnt",b"cnt","data",b"data","num_successors",b"num_successors","ori",b"ori","rel",b"rel","rev",b"rev"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_num_successors",b"_num_successors","cnt",b"cnt","data",b"data","num_successors",b"num_successors","ori",b"ori","rel",b"rel","rev",b"rev","successor",b"successor","swhid",b"swhid"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_num_successors",b"_num_successors"]) -> typing.Optional[typing_extensions.Literal["num_successors"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["data",b"data"]) -> typing.Optional[typing_extensions.Literal["cnt","rev","rel","ori"]]: ... global___Node = Node class Path(google.protobuf.message.Message): """Represents a path in the graph.""" DESCRIPTOR: google.protobuf.descriptor.Descriptor NODE_FIELD_NUMBER: builtins.int - MIDDLE_NODE_INDEX_FIELD_NUMBER: builtins.int + MIDPOINT_INDEX_FIELD_NUMBER: builtins.int @property def node(self) -> google.protobuf.internal.containers.RepeatedCompositeFieldContainer[global___Node]: """List of nodes in the path, from source to destination""" pass - middle_node_index: builtins.int - """Index of the "middle node" of the path. For paths obtained in + midpoint_index: builtins.int + """Index of the "midpoint" of the path. For paths obtained with bidirectional search queries, this is the node that joined the two sets together. When looking for a common ancestor between two nodes by performing a FindPathBetween search with two backward graphs, this will be the index of the common ancestor in the path. """ def __init__(self, *, node: typing.Optional[typing.Iterable[global___Node]] = ..., - middle_node_index: typing.Optional[builtins.int] = ..., + midpoint_index: typing.Optional[builtins.int] = ..., ) -> None: ... - def HasField(self, field_name: typing_extensions.Literal["_middle_node_index",b"_middle_node_index","middle_node_index",b"middle_node_index"]) -> builtins.bool: ... - def ClearField(self, field_name: typing_extensions.Literal["_middle_node_index",b"_middle_node_index","middle_node_index",b"middle_node_index","node",b"node"]) -> None: ... - def WhichOneof(self, oneof_group: typing_extensions.Literal["_middle_node_index",b"_middle_node_index"]) -> typing.Optional[typing_extensions.Literal["middle_node_index"]]: ... + def HasField(self, field_name: typing_extensions.Literal["_midpoint_index",b"_midpoint_index","midpoint_index",b"midpoint_index"]) -> builtins.bool: ... + def ClearField(self, field_name: typing_extensions.Literal["_midpoint_index",b"_midpoint_index","midpoint_index",b"midpoint_index","node",b"node"]) -> None: ... + def WhichOneof(self, oneof_group: typing_extensions.Literal["_midpoint_index",b"_midpoint_index"]) -> typing.Optional[typing_extensions.Literal["midpoint_index"]]: ... global___Path = Path class Successor(google.protobuf.message.Message): """Represents a successor of a given node.""" DESCRIPTOR: google.protobuf.descriptor.Descriptor SWHID_FIELD_NUMBER: builtins.int LABEL_FIELD_NUMBER: builtins.int swhid: typing.Text """The SWHID of the successor""" @property def label(self) -> google.protobuf.internal.containers.RepeatedCompositeFieldContainer[global___EdgeLabel]: """A list of edge labels for the given edge""" pass def __init__(self, *, swhid: typing.Optional[typing.Text] = ..., label: typing.Optional[typing.Iterable[global___EdgeLabel]] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_swhid",b"_swhid","swhid",b"swhid"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_swhid",b"_swhid","label",b"label","swhid",b"swhid"]) -> None: ... def WhichOneof(self, oneof_group: typing_extensions.Literal["_swhid",b"_swhid"]) -> typing.Optional[typing_extensions.Literal["swhid"]]: ... global___Successor = Successor class ContentData(google.protobuf.message.Message): """Content node properties""" DESCRIPTOR: google.protobuf.descriptor.Descriptor LENGTH_FIELD_NUMBER: builtins.int IS_SKIPPED_FIELD_NUMBER: builtins.int length: builtins.int """Length of the blob, in bytes""" is_skipped: builtins.bool """Whether the content was skipped during ingestion.""" def __init__(self, *, length: typing.Optional[builtins.int] = ..., is_skipped: typing.Optional[builtins.bool] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_is_skipped",b"_is_skipped","_length",b"_length","is_skipped",b"is_skipped","length",b"length"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_is_skipped",b"_is_skipped","_length",b"_length","is_skipped",b"is_skipped","length",b"length"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_is_skipped",b"_is_skipped"]) -> typing.Optional[typing_extensions.Literal["is_skipped"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_length",b"_length"]) -> typing.Optional[typing_extensions.Literal["length"]]: ... global___ContentData = ContentData class RevisionData(google.protobuf.message.Message): """Revision node properties""" DESCRIPTOR: google.protobuf.descriptor.Descriptor AUTHOR_FIELD_NUMBER: builtins.int AUTHOR_DATE_FIELD_NUMBER: builtins.int AUTHOR_DATE_OFFSET_FIELD_NUMBER: builtins.int COMMITTER_FIELD_NUMBER: builtins.int COMMITTER_DATE_FIELD_NUMBER: builtins.int COMMITTER_DATE_OFFSET_FIELD_NUMBER: builtins.int MESSAGE_FIELD_NUMBER: builtins.int author: builtins.int """Revision author ID (anonymized)""" author_date: builtins.int """UNIX timestamp of the revision date (UTC)""" author_date_offset: builtins.int """Timezone of the revision author date as an offset from UTC""" committer: builtins.int """Revision committer ID (anonymized)""" committer_date: builtins.int """UNIX timestamp of the revision committer date (UTC)""" committer_date_offset: builtins.int """Timezone of the revision committer date as an offset from UTC""" message: builtins.bytes """Revision message""" def __init__(self, *, author: typing.Optional[builtins.int] = ..., author_date: typing.Optional[builtins.int] = ..., author_date_offset: typing.Optional[builtins.int] = ..., committer: typing.Optional[builtins.int] = ..., committer_date: typing.Optional[builtins.int] = ..., committer_date_offset: typing.Optional[builtins.int] = ..., message: typing.Optional[builtins.bytes] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_author",b"_author","_author_date",b"_author_date","_author_date_offset",b"_author_date_offset","_committer",b"_committer","_committer_date",b"_committer_date","_committer_date_offset",b"_committer_date_offset","_message",b"_message","author",b"author","author_date",b"author_date","author_date_offset",b"author_date_offset","committer",b"committer","committer_date",b"committer_date","committer_date_offset",b"committer_date_offset","message",b"message"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_author",b"_author","_author_date",b"_author_date","_author_date_offset",b"_author_date_offset","_committer",b"_committer","_committer_date",b"_committer_date","_committer_date_offset",b"_committer_date_offset","_message",b"_message","author",b"author","author_date",b"author_date","author_date_offset",b"author_date_offset","committer",b"committer","committer_date",b"committer_date","committer_date_offset",b"committer_date_offset","message",b"message"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author",b"_author"]) -> typing.Optional[typing_extensions.Literal["author"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author_date",b"_author_date"]) -> typing.Optional[typing_extensions.Literal["author_date"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author_date_offset",b"_author_date_offset"]) -> typing.Optional[typing_extensions.Literal["author_date_offset"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_committer",b"_committer"]) -> typing.Optional[typing_extensions.Literal["committer"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_committer_date",b"_committer_date"]) -> typing.Optional[typing_extensions.Literal["committer_date"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_committer_date_offset",b"_committer_date_offset"]) -> typing.Optional[typing_extensions.Literal["committer_date_offset"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_message",b"_message"]) -> typing.Optional[typing_extensions.Literal["message"]]: ... global___RevisionData = RevisionData class ReleaseData(google.protobuf.message.Message): """Release node properties""" DESCRIPTOR: google.protobuf.descriptor.Descriptor AUTHOR_FIELD_NUMBER: builtins.int AUTHOR_DATE_FIELD_NUMBER: builtins.int AUTHOR_DATE_OFFSET_FIELD_NUMBER: builtins.int NAME_FIELD_NUMBER: builtins.int MESSAGE_FIELD_NUMBER: builtins.int author: builtins.int + """Release author ID (anonymized)""" + author_date: builtins.int """UNIX timestamp of the release date (UTC)""" author_date_offset: builtins.int """Timezone of the release author date as an offset from UTC""" name: builtins.bytes """Release name""" message: builtins.bytes """Release message""" def __init__(self, *, author: typing.Optional[builtins.int] = ..., author_date: typing.Optional[builtins.int] = ..., author_date_offset: typing.Optional[builtins.int] = ..., name: typing.Optional[builtins.bytes] = ..., message: typing.Optional[builtins.bytes] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_author",b"_author","_author_date",b"_author_date","_author_date_offset",b"_author_date_offset","_message",b"_message","_name",b"_name","author",b"author","author_date",b"author_date","author_date_offset",b"author_date_offset","message",b"message","name",b"name"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_author",b"_author","_author_date",b"_author_date","_author_date_offset",b"_author_date_offset","_message",b"_message","_name",b"_name","author",b"author","author_date",b"author_date","author_date_offset",b"author_date_offset","message",b"message","name",b"name"]) -> None: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author",b"_author"]) -> typing.Optional[typing_extensions.Literal["author"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author_date",b"_author_date"]) -> typing.Optional[typing_extensions.Literal["author_date"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_author_date_offset",b"_author_date_offset"]) -> typing.Optional[typing_extensions.Literal["author_date_offset"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_message",b"_message"]) -> typing.Optional[typing_extensions.Literal["message"]]: ... @typing.overload def WhichOneof(self, oneof_group: typing_extensions.Literal["_name",b"_name"]) -> typing.Optional[typing_extensions.Literal["name"]]: ... global___ReleaseData = ReleaseData class OriginData(google.protobuf.message.Message): """Origin node properties""" DESCRIPTOR: google.protobuf.descriptor.Descriptor URL_FIELD_NUMBER: builtins.int url: typing.Text """URL of the origin""" def __init__(self, *, url: typing.Optional[typing.Text] = ..., ) -> None: ... def HasField(self, field_name: typing_extensions.Literal["_url",b"_url","url",b"url"]) -> builtins.bool: ... def ClearField(self, field_name: typing_extensions.Literal["_url",b"_url","url",b"url"]) -> None: ... def WhichOneof(self, oneof_group: typing_extensions.Literal["_url",b"_url"]) -> typing.Optional[typing_extensions.Literal["url"]]: ... global___OriginData = OriginData class EdgeLabel(google.protobuf.message.Message): DESCRIPTOR: google.protobuf.descriptor.Descriptor NAME_FIELD_NUMBER: builtins.int PERMISSION_FIELD_NUMBER: builtins.int name: builtins.bytes """Directory entry name for directories, branch name for snapshots""" permission: builtins.int """Entry permission (only set for directories).""" def __init__(self, *, name: builtins.bytes = ..., permission: builtins.int = ..., ) -> None: ... def ClearField(self, field_name: typing_extensions.Literal["name",b"name","permission",b"permission"]) -> None: ... global___EdgeLabel = EdgeLabel class CountResponse(google.protobuf.message.Message): DESCRIPTOR: google.protobuf.descriptor.Descriptor COUNT_FIELD_NUMBER: builtins.int count: builtins.int def __init__(self, *, count: builtins.int = ..., ) -> None: ... def ClearField(self, field_name: typing_extensions.Literal["count",b"count"]) -> None: ... global___CountResponse = CountResponse class StatsRequest(google.protobuf.message.Message): DESCRIPTOR: google.protobuf.descriptor.Descriptor def __init__(self, ) -> None: ... global___StatsRequest = StatsRequest class StatsResponse(google.protobuf.message.Message): DESCRIPTOR: google.protobuf.descriptor.Descriptor NUM_NODES_FIELD_NUMBER: builtins.int NUM_EDGES_FIELD_NUMBER: builtins.int - COMPRESSION_FIELD_NUMBER: builtins.int + COMPRESSION_RATIO_FIELD_NUMBER: builtins.int BITS_PER_NODE_FIELD_NUMBER: builtins.int BITS_PER_EDGE_FIELD_NUMBER: builtins.int AVG_LOCALITY_FIELD_NUMBER: builtins.int INDEGREE_MIN_FIELD_NUMBER: builtins.int INDEGREE_MAX_FIELD_NUMBER: builtins.int INDEGREE_AVG_FIELD_NUMBER: builtins.int OUTDEGREE_MIN_FIELD_NUMBER: builtins.int OUTDEGREE_MAX_FIELD_NUMBER: builtins.int OUTDEGREE_AVG_FIELD_NUMBER: builtins.int num_nodes: builtins.int + """Number of nodes in the graph""" + num_edges: builtins.int - compression: builtins.float + """Number of edges in the graph""" + + compression_ratio: builtins.float bits_per_node: builtins.float bits_per_edge: builtins.float avg_locality: builtins.float indegree_min: builtins.int indegree_max: builtins.int indegree_avg: builtins.float outdegree_min: builtins.int outdegree_max: builtins.int outdegree_avg: builtins.float def __init__(self, *, num_nodes: builtins.int = ..., num_edges: builtins.int = ..., - compression: builtins.float = ..., + compression_ratio: builtins.float = ..., bits_per_node: builtins.float = ..., bits_per_edge: builtins.float = ..., avg_locality: builtins.float = ..., indegree_min: builtins.int = ..., indegree_max: builtins.int = ..., indegree_avg: builtins.float = ..., outdegree_min: builtins.int = ..., outdegree_max: builtins.int = ..., outdegree_avg: builtins.float = ..., ) -> None: ... - def ClearField(self, field_name: typing_extensions.Literal["avg_locality",b"avg_locality","bits_per_edge",b"bits_per_edge","bits_per_node",b"bits_per_node","compression",b"compression","indegree_avg",b"indegree_avg","indegree_max",b"indegree_max","indegree_min",b"indegree_min","num_edges",b"num_edges","num_nodes",b"num_nodes","outdegree_avg",b"outdegree_avg","outdegree_max",b"outdegree_max","outdegree_min",b"outdegree_min"]) -> None: ... + def ClearField(self, field_name: typing_extensions.Literal["avg_locality",b"avg_locality","bits_per_edge",b"bits_per_edge","bits_per_node",b"bits_per_node","compression_ratio",b"compression_ratio","indegree_avg",b"indegree_avg","indegree_max",b"indegree_max","indegree_min",b"indegree_min","num_edges",b"num_edges","num_nodes",b"num_nodes","outdegree_avg",b"outdegree_avg","outdegree_max",b"outdegree_max","outdegree_min",b"outdegree_min"]) -> None: ... global___StatsResponse = StatsResponse diff --git a/swh/graph/rpc/swhgraph_pb2_grpc.py b/swh/graph/rpc/swhgraph_pb2_grpc.py index 2f08d12..1ca7ce0 100644 --- a/swh/graph/rpc/swhgraph_pb2_grpc.py +++ b/swh/graph/rpc/swhgraph_pb2_grpc.py @@ -1,276 +1,303 @@ # Generated by the gRPC Python protocol compiler plugin. DO NOT EDIT! """Client and server classes corresponding to protobuf-defined services.""" import grpc from swh.graph.rpc import swhgraph_pb2 as swh_dot_graph_dot_rpc_dot_swhgraph__pb2 class TraversalServiceStub(object): - """Missing associated documentation comment in .proto file.""" + """Graph traversal service + """ def __init__(self, channel): """Constructor. Args: channel: A grpc.Channel. """ self.GetNode = channel.unary_unary( '/swh.graph.TraversalService/GetNode', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.GetNodeRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.FromString, ) self.Traverse = channel.unary_stream( '/swh.graph.TraversalService/Traverse', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.FromString, ) self.FindPathTo = channel.unary_unary( '/swh.graph.TraversalService/FindPathTo', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathToRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.FromString, ) self.FindPathBetween = channel.unary_unary( '/swh.graph.TraversalService/FindPathBetween', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathBetweenRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.FromString, ) self.CountNodes = channel.unary_unary( '/swh.graph.TraversalService/CountNodes', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.FromString, ) self.CountEdges = channel.unary_unary( '/swh.graph.TraversalService/CountEdges', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.FromString, ) self.Stats = channel.unary_unary( '/swh.graph.TraversalService/Stats', request_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsRequest.SerializeToString, response_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsResponse.FromString, ) class TraversalServiceServicer(object): - """Missing associated documentation comment in .proto file.""" + """Graph traversal service + """ def GetNode(self, request, context): """GetNode returns a single Node and its properties. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def Traverse(self, request, context): """Traverse performs a breadth-first graph traversal from a set of source - nodes, then streams the nodes it encounters, along with their properties. + nodes, then streams the nodes it encounters (if they match a given + return filter), along with their properties. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def FindPathTo(self, request, context): """FindPathTo searches for the shortest path between a set of source nodes and a node that matches a specific *criteria*. + + It does so by performing a breadth-first search from the source node, + until any node that matches the given criteria is found, then follows + back its parents to return the shortest path from the source set to that + node. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def FindPathBetween(self, request, context): """FindPathBetween searches for the shortest path between a set of source - nodes and a set of destination nodes. + nodes and a set of destination nodes. + + It does so by performing a *bidirectional breadth-first search*, i.e., + two parallel breadth-first searches, one from the source set ("src-BFS") + and one from the destination set ("dst-BFS"), until both searches find a + common node that joins their visited sets. This node is called the + "midpoint node". + The path returned is the path src -> ... -> midpoint * -> ... -> dst, + which is the shortest path between src and dst. + + The graph direction of both BFS can be configured separately. By + default, the dst-BFS will use the graph in the opposite direction than + the src-BFS (if direction = FORWARD, by default direction_reverse = + BACKWARD, and vice-versa). The default behavior is thus to search for + the shortest path between two nodes in a given direction. However, one + can also specify FORWARD or BACKWARD for *both* the src-BFS and the + dst-BFS. This will search for a common descendant or a common ancestor + between the two sets, respectively. These will be the midpoints of the + returned path. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def CountNodes(self, request, context): """CountNodes does the same as Traverse, but only returns the number of nodes accessed during the traversal. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def CountEdges(self, request, context): """CountEdges does the same as Traverse, but only returns the number of edges accessed during the traversal. """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def Stats(self, request, context): """Stats returns various """ context.set_code(grpc.StatusCode.UNIMPLEMENTED) context.set_details('Method not implemented!') raise NotImplementedError('Method not implemented!') def add_TraversalServiceServicer_to_server(servicer, server): rpc_method_handlers = { 'GetNode': grpc.unary_unary_rpc_method_handler( servicer.GetNode, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.GetNodeRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.SerializeToString, ), 'Traverse': grpc.unary_stream_rpc_method_handler( servicer.Traverse, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.SerializeToString, ), 'FindPathTo': grpc.unary_unary_rpc_method_handler( servicer.FindPathTo, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathToRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.SerializeToString, ), 'FindPathBetween': grpc.unary_unary_rpc_method_handler( servicer.FindPathBetween, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathBetweenRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.SerializeToString, ), 'CountNodes': grpc.unary_unary_rpc_method_handler( servicer.CountNodes, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.SerializeToString, ), 'CountEdges': grpc.unary_unary_rpc_method_handler( servicer.CountEdges, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.SerializeToString, ), 'Stats': grpc.unary_unary_rpc_method_handler( servicer.Stats, request_deserializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsRequest.FromString, response_serializer=swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsResponse.SerializeToString, ), } generic_handler = grpc.method_handlers_generic_handler( 'swh.graph.TraversalService', rpc_method_handlers) server.add_generic_rpc_handlers((generic_handler,)) # This class is part of an EXPERIMENTAL API. class TraversalService(object): - """Missing associated documentation comment in .proto file.""" + """Graph traversal service + """ @staticmethod def GetNode(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/GetNode', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.GetNodeRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def Traverse(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_stream(request, target, '/swh.graph.TraversalService/Traverse', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Node.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def FindPathTo(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/FindPathTo', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathToRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def FindPathBetween(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/FindPathBetween', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.FindPathBetweenRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.Path.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def CountNodes(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/CountNodes', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def CountEdges(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/CountEdges', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.TraversalRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.CountResponse.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) @staticmethod def Stats(request, target, options=(), channel_credentials=None, call_credentials=None, insecure=False, compression=None, wait_for_ready=None, timeout=None, metadata=None): return grpc.experimental.unary_unary(request, target, '/swh.graph.TraversalService/Stats', swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsRequest.SerializeToString, swh_dot_graph_dot_rpc_dot_swhgraph__pb2.StatsResponse.FromString, options, channel_credentials, insecure, call_credentials, compression, wait_for_ready, timeout, metadata) diff --git a/swh/graph/tests/test_http_client.py b/swh/graph/tests/test_http_client.py index daaa37c..93240ef 100644 --- a/swh/graph/tests/test_http_client.py +++ b/swh/graph/tests/test_http_client.py @@ -1,373 +1,373 @@ import hashlib import pytest from pytest import raises from swh.core.api import RemoteException from swh.graph.http_client import GraphArgumentException TEST_ORIGIN_ID = "swh:1:ori:{}".format( hashlib.sha1(b"https://example.com/swh/graph").hexdigest() ) def test_stats(graph_client): stats = graph_client.stats() assert stats["num_nodes"] == 21 assert stats["num_edges"] == 23 - assert isinstance(stats["compression"], float) + assert isinstance(stats["compression_ratio"], float) assert isinstance(stats["bits_per_node"], float) assert isinstance(stats["bits_per_edge"], float) assert isinstance(stats["avg_locality"], float) assert stats["indegree_min"] == 0 assert stats["indegree_max"] == 3 assert isinstance(stats["indegree_avg"], float) assert stats["outdegree_min"] == 0 assert stats["outdegree_max"] == 3 assert isinstance(stats["outdegree_avg"], float) def test_leaves(graph_client): actual = list(graph_client.leaves(TEST_ORIGIN_ID)) expected = [ "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:cnt:0000000000000000000000000000000000000005", "swh:1:cnt:0000000000000000000000000000000000000007", ] assert set(actual) == set(expected) def test_neighbors(graph_client): actual = list( graph_client.neighbors( "swh:1:rev:0000000000000000000000000000000000000009", direction="backward" ) ) expected = [ "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000013", ] assert set(actual) == set(expected) def test_visit_nodes(graph_client): actual = list( graph_client.visit_nodes( "swh:1:rel:0000000000000000000000000000000000000010", edges="rel:rev,rev:rev", ) ) expected = [ "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", ] assert set(actual) == set(expected) def test_visit_nodes_filtered(graph_client): actual = list( graph_client.visit_nodes( "swh:1:rel:0000000000000000000000000000000000000010", return_types="dir", ) ) expected = [ "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", ] assert set(actual) == set(expected) def test_visit_nodes_filtered_star(graph_client): actual = list( graph_client.visit_nodes( "swh:1:rel:0000000000000000000000000000000000000010", return_types="*", ) ) expected = [ "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:cnt:0000000000000000000000000000000000000005", ] assert set(actual) == set(expected) def test_visit_edges(graph_client): actual = list( graph_client.visit_edges( "swh:1:rel:0000000000000000000000000000000000000010", edges="rel:rev,rev:rev,rev:dir", ) ) expected = [ ( "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", ), ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", ), ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", ), ( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", ), ] assert set(actual) == set(expected) def test_visit_edges_limited(graph_client): actual = list( graph_client.visit_edges( "swh:1:rel:0000000000000000000000000000000000000010", max_edges=4, edges="rel:rev,rev:rev,rev:dir", ) ) expected = [ ( "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", ), ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", ), ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", ), ( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", ), ] # As there are four valid answers (up to reordering), we cannot check for # equality. Instead, we check the client returned all edges but one. assert set(actual).issubset(set(expected)) assert len(actual) == 3 def test_visit_edges_diamond_pattern(graph_client): actual = list( graph_client.visit_edges( "swh:1:rev:0000000000000000000000000000000000000009", edges="*", ) ) expected = [ ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", ), ( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", ), ( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", ), ( "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001", ), ( "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001", ), ( "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007", ), ( "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", ), ( "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004", ), ( "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005", ), ] assert set(actual) == set(expected) @pytest.mark.skip(reason="currently disabled due to T1969") def test_walk(graph_client): args = ("swh:1:dir:0000000000000000000000000000000000000016", "rel") kwargs = { "edges": "dir:dir,dir:rev,rev:*", "direction": "backward", "traversal": "bfs", } actual = list(graph_client.walk(*args, **kwargs)) expected = [ "swh:1:dir:0000000000000000000000000000000000000016", "swh:1:dir:0000000000000000000000000000000000000017", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019", ] assert set(actual) == set(expected) kwargs2 = kwargs.copy() kwargs2["limit"] = -1 actual = list(graph_client.walk(*args, **kwargs2)) expected = ["swh:1:rel:0000000000000000000000000000000000000019"] assert set(actual) == set(expected) kwargs2 = kwargs.copy() kwargs2["limit"] = 2 actual = list(graph_client.walk(*args, **kwargs2)) expected = [ "swh:1:dir:0000000000000000000000000000000000000016", "swh:1:dir:0000000000000000000000000000000000000017", ] assert set(actual) == set(expected) @pytest.mark.skip(reason="Random walk is deprecated") def test_random_walk_dst_is_type(graph_client): """as the walk is random, we test a visit from a cnt node to a release reachable from every single path in the backward graph, and only check the final node of the path (i.e., the release) """ args = ("swh:1:cnt:0000000000000000000000000000000000000015", "rel") kwargs = {"direction": "backward"} expected_root = "swh:1:rel:0000000000000000000000000000000000000019" actual = list(graph_client.random_walk(*args, **kwargs)) assert len(actual) > 1 # no release directly links to a content assert actual[0] == args[0] assert actual[-1] == expected_root kwargs2 = kwargs.copy() kwargs2["limit"] = -1 actual = list(graph_client.random_walk(*args, **kwargs2)) assert actual == [expected_root] kwargs2["limit"] = -2 actual = list(graph_client.random_walk(*args, **kwargs2)) assert len(actual) == 2 assert actual[-1] == expected_root kwargs2["limit"] = 3 actual = list(graph_client.random_walk(*args, **kwargs2)) assert len(actual) == 3 @pytest.mark.skip(reason="Random walk is deprecated") def test_random_walk_dst_is_node(graph_client): """Same as test_random_walk_dst_is_type, but we target the specific release node instead of a type """ args = ( "swh:1:cnt:0000000000000000000000000000000000000015", "swh:1:rel:0000000000000000000000000000000000000019", ) kwargs = {"direction": "backward"} expected_root = "swh:1:rel:0000000000000000000000000000000000000019" actual = list(graph_client.random_walk(*args, **kwargs)) assert len(actual) > 1 # no origin directly links to a content assert actual[0] == args[0] assert actual[-1] == expected_root kwargs2 = kwargs.copy() kwargs2["limit"] = -1 actual = list(graph_client.random_walk(*args, **kwargs2)) assert actual == [expected_root] kwargs2["limit"] = -2 actual = list(graph_client.random_walk(*args, **kwargs2)) assert len(actual) == 2 assert actual[-1] == expected_root kwargs2["limit"] = 3 actual = list(graph_client.random_walk(*args, **kwargs2)) assert len(actual) == 3 def test_count(graph_client): actual = graph_client.count_leaves(TEST_ORIGIN_ID) assert actual == 4 actual = graph_client.count_visit_nodes( "swh:1:rel:0000000000000000000000000000000000000010", edges="rel:rev,rev:rev" ) assert actual == 3 actual = graph_client.count_neighbors( "swh:1:rev:0000000000000000000000000000000000000009", direction="backward" ) assert actual == 3 def test_param_validation(graph_client): with raises(GraphArgumentException) as exc_info: # SWHID not found list(graph_client.leaves("swh:1:rel:00ffffffff000000000000000000000000000010")) if exc_info.value.response: assert exc_info.value.response.status_code == 404 with raises(GraphArgumentException) as exc_info: # malformed SWHID list( graph_client.neighbors("swh:1:rel:00ffffffff00000000zzzzzzz000000000000010") ) if exc_info.value.response: assert exc_info.value.response.status_code == 400 with raises(GraphArgumentException) as exc_info: # malformed edge specificaiton list( graph_client.visit_nodes( "swh:1:dir:0000000000000000000000000000000000000016", edges="dir:notanodetype,dir:rev,rev:*", direction="backward", ) ) if exc_info.value.response: assert exc_info.value.response.status_code == 400 with raises(GraphArgumentException) as exc_info: # malformed direction list( graph_client.visit_nodes( "swh:1:dir:0000000000000000000000000000000000000016", edges="dir:dir,dir:rev,rev:*", direction="notadirection", ) ) if exc_info.value.response: assert exc_info.value.response.status_code == 400 @pytest.mark.skip(reason="currently disabled due to T1969") def test_param_validation_walk(graph_client): """test validation of walk-specific parameters only""" with raises(RemoteException) as exc_info: # malformed traversal order list( graph_client.walk( "swh:1:dir:0000000000000000000000000000000000000016", "rel", edges="dir:dir,dir:rev,rev:*", direction="backward", traversal="notatraversalorder", ) ) assert exc_info.value.response.status_code == 400