diff --git a/api/client/swh/graph/client.py b/api/client/swh/graph/client.py --- a/api/client/swh/graph/client.py +++ b/api/client/swh/graph/client.py @@ -30,6 +30,13 @@ # Web API endpoints + def neighbors(self, src, edges="*", direction="forward"): + return self.get('neighbors/{}'.format(src), + params={ + 'edges': edges, + 'direction': direction + }) + def stats(self): return self.get('stats') diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java --- a/api/server/src/main/java/org/softwareheritage/graph/App.java +++ b/api/server/src/main/java/org/softwareheritage/graph/App.java @@ -12,6 +12,7 @@ import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.algo.Neighbors; import org.softwareheritage.graph.algo.Stats; import org.softwareheritage.graph.algo.Visit; import org.softwareheritage.graph.algo.Walk; @@ -41,6 +42,7 @@ Javalin app = Javalin.create().start(5009); app.before("/stats/*", ctx -> { checkQueryStrings(ctx, ""); }); + app.before("/neighbors/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/visit/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/walk/*", ctx -> { checkQueryStrings(ctx, "direction|edges|traversal"); }); @@ -49,6 +51,15 @@ // Graph traversal endpoints // By default the traversal is a forward DFS using all edges + app.get("/neighbors/:src", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); + + Neighbors neighbors = new Neighbors(graph, src, edgesFmt, direction); + ctx.json(neighbors.getNeighbors()); + }); + app.get("/visit/:src", ctx -> { SwhId src = new SwhId(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Neighbors.java @@ -0,0 +1,49 @@ +package org.softwareheritage.graph.algo; + +import java.util.ArrayList; + +import it.unimi.dsi.big.webgraph.LazyLongIterator; + +import org.softwareheritage.graph.AllowedEdges; +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhId; + +public class Neighbors { + Graph graph; + boolean useTransposed; + AllowedEdges edges; + + ArrayList neighbors; + + public Neighbors(Graph graph, SwhId src, String edgesFmt, String direction) { + if (!direction.matches("forward|backward")) { + throw new IllegalArgumentException("Unknown traversal direction: " + direction); + } + + this.graph = graph; + this.useTransposed = (direction.equals("backward")); + this.edges = new AllowedEdges(edgesFmt); + this.neighbors = new ArrayList(); + + iterateNeighbors(src); + } + + public ArrayList getNeighbors() { + return neighbors; + } + + private void iterateNeighbors(SwhId swhId) { + long nodeId = graph.getNodeId(swhId); + long degree = graph.degree(nodeId, useTransposed); + LazyLongIterator neighborsNodeIds = graph.neighbors(nodeId, useTransposed); + + while (degree-- > 0) { + long neighborNodeId = neighborsNodeIds.nextLong(); + SwhId neighborSwhId = graph.getSwhId(neighborNodeId); + if (edges.isAllowed(swhId.getType(), neighborSwhId.getType())) { + neighbors.add(neighborSwhId); + } + } + } +} + diff --git a/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java new file mode 100644 --- /dev/null +++ b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java @@ -0,0 +1,122 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.algo.Neighbors; + +public class NeighborsTest extends GraphTest { + @Test + public void zeroNeighbor() { + Graph graph = getGraph(); + ArrayList expectedNodes = new ArrayList<>(); + + SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + Neighbors neighbors1 = new Neighbors(graph, src1, "*", "backward"); + assertEquals(expectedNodes, neighbors1.getNeighbors()); + + SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); + Neighbors neighbors2 = new Neighbors(graph, src2, "*", "forward"); + assertEquals(expectedNodes, neighbors2.getNeighbors()); + + SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015"); + Neighbors neighbors3 = new Neighbors(graph, src3, "*", "forward"); + assertEquals(expectedNodes, neighbors3.getNeighbors()); + + SwhId src4 = new SwhId("swh:1:rel:0000000000000000000000000000000000000019"); + Neighbors neighbors4 = new Neighbors(graph, src4, "*", "backward"); + assertEquals(expectedNodes, neighbors4.getNeighbors()); + + SwhId src5 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); + Neighbors neighbors5 = new Neighbors(graph, src5, "snp:*,rev:*,rel:*", "forward"); + assertEquals(expectedNodes, neighbors5.getNeighbors()); + } + + @Test + public void oneNeighbor() { + Graph graph = getGraph(); + + SwhId src1 = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); + Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward"); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002")); + assertEquals(expectedNodes1, neighbors1.getNeighbors()); + + SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000017"); + Neighbors neighbors2 = new Neighbors(graph, src2, "dir:cnt", "forward"); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000014")); + assertEquals(expectedNodes2, neighbors2.getNeighbors()); + + SwhId src3 = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); + Neighbors neighbors3 = new Neighbors(graph, src3, "*", "backward"); + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); + assertEquals(expectedNodes3, neighbors3.getNeighbors()); + + SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); + Neighbors neighbors4 = new Neighbors(graph, src4, "rev:rev", "backward"); + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); + assertEquals(expectedNodes4, neighbors4.getNeighbors()); + } + + @Test + public void twoNeighbors() { + Graph graph = getGraph(); + + SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward"); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes1.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009")); + assertEquals(expectedNodes1, neighbors1.getNeighbors()); + + SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); + Neighbors neighbors2 = new Neighbors(graph, src2, "dir:cnt", "forward"); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + assertEquals(expectedNodes2, neighbors2.getNeighbors()); + + SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"); + Neighbors neighbors3 = new Neighbors(graph, src3, "*", "backward"); + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000008")); + expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002")); + assertEquals(expectedNodes3, neighbors3.getNeighbors()); + + SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); + Neighbors neighbors4 = new Neighbors(graph, src4, "rev:snp,rev:rel", "backward"); + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes4.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); + assertEquals(expectedNodes4, neighbors4.getNeighbors()); + } + + @Test + public void threeNeighbors() { + Graph graph = getGraph(); + + SwhId src1 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); + Neighbors neighbors1 = new Neighbors(graph, src1, "*", "forward"); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000006")); + expectedNodes1.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes1.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + assertEquals(expectedNodes1, neighbors1.getNeighbors()); + + SwhId src2 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); + Neighbors neighbors2 = new Neighbors(graph, src2, "*", "backward"); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes2.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes2.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); + assertEquals(expectedNodes2, neighbors2.getNeighbors()); + } +} diff --git a/docs/api.rst b/docs/api.rst --- a/docs/api.rst +++ b/docs/api.rst @@ -30,6 +30,35 @@ nodes, or from directories nodes. - ``"*:rel"`` node types allowing all edges to releases. +Neighbors +--------- + +.. http:get:: /graph/neighbors/:src + + Returns node direct neighbors (linked with exactly one edge) in the graph. + + :param string src: source node specified as a SWH PID + + :query string edges: edges types allowed to be listed as neighbors; default + to ``"*"`` + :query string direction: direction in which graph edges will be followed; + can be either ``forward`` or ``backward``, default to ``forward`` + + :statuscode 200: success + :statuscode 400: invalid query string provided + :statuscode 404: starting node cannot be found + + .. sourcecode:: http + + HTTP/1.1 200 OK + Content-Type: application/json + + [ + "swh:1:cnt:94a9ed024d3859793618152ea559a168bbcbb5e2", + "swh:1:dir:d198bc9d7a6bcf6db04f476d29314f157507d505", + ... + ] + Walk ----