diff --git a/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java b/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java @@ -0,0 +1,48 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.softwareheritage.graph.Node; + +public class AllowedEdges { + // First dimension is source node type, second dimension is destination node type + boolean[][] allowed; + + public AllowedEdges(String edgesFmt) { + int nbNodeTypes = Node.Type.values().length; + this.allowed = new boolean[nbNodeTypes][nbNodeTypes]; + // Special values (null, empty, "*") + if (edgesFmt == null || edgesFmt.isEmpty()) { + return; + } + if (edgesFmt.equals("*")) { + for (int i = 0; i < nbNodeTypes; i++) { + for (int j = 0; j < nbNodeTypes; j++) { + allowed[i][j] = true; + } + } + return; + } + + // Format: "src1:dst1,src2:dst2,[...]" + String[] edgeTypes = edgesFmt.split(","); + for (String edgeType : edgeTypes) { + String[] nodeTypes = edgeType.split(":"); + if (nodeTypes.length != 2) { + throw new IllegalArgumentException("Cannot parse edge type: " + edgeType); + } + + ArrayList srcTypes = Node.Type.parse(nodeTypes[0]); + ArrayList dstTypes = Node.Type.parse(nodeTypes[1]); + for (Node.Type srcType : srcTypes) { + for (Node.Type dstType : dstTypes) { + allowed[srcType.ordinal()][dstType.ordinal()] = true; + } + } + } + } + + public boolean isAllowed(Node.Type currentType, Node.Type neighborType) { + return allowed[currentType.ordinal()][neighborType.ordinal()]; + } +} 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 @@ -7,12 +7,14 @@ import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.PropertyNamingStrategy; import io.javalin.Javalin; +import io.javalin.http.Context; import io.javalin.plugin.json.JavalinJackson; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.algo.Stats; import org.softwareheritage.graph.algo.Visit; +import org.softwareheritage.graph.algo.Walk; public class App { public static void main(String[] args) throws IOException { @@ -38,33 +40,65 @@ Javalin app = Javalin.create().start(5010); - app.get("/stats", ctx -> { - ctx.json(stats); + app.before("/stats/*", ctx -> { checkQueryStrings(ctx, ""); }); + app.before("/visit/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); + app.before("/walk/*", ctx -> { checkQueryStrings(ctx, "direction|edges|traversal"); }); + + app.get("/stats/", ctx -> { ctx.json(stats); }); + + // Graph traversal endpoints + // By default the traversal is a forward DFS using all edges + + app.get("/visit/:src", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); + + Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.NODES_AND_PATHS); + ctx.json(visit); }); - app.get("/visit/:swh_id", ctx -> { - try { - Map> queryParamMap = ctx.queryParamMap(); - for (String key : queryParamMap.keySet()) { - if (!key.matches("direction|edges|traversal")) { - throw new IllegalArgumentException("Unknown query string: " + key); - } - } + app.get("/visit/nodes/:src", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); - SwhId swhId = new SwhId(ctx.pathParam("swh_id")); + Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.ONLY_NODES); + ctx.json(visit.getNodes()); + }); - // By default, traversal is a forward DFS using all edges - String traversal = ctx.queryParam("traversal", "dfs"); - String direction = ctx.queryParam("direction", "forward"); - String edges = ctx.queryParam("edges", "all"); + app.get("/visit/paths/:src", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); - ctx.json(new Visit(graph, swhId, edges, traversal, direction)); - } catch (IllegalArgumentException e) { - ctx.status(400); - ctx.result(e.getMessage()); - } + Visit visit = new Visit(graph, src, edgesFmt, direction, Visit.OutputFmt.ONLY_PATHS); + ctx.json(visit.getPaths()); }); - app.error(404, ctx -> { ctx.result("Not found"); }); + app.get("/walk/:src/:dst", ctx -> { + SwhId src = new SwhId(ctx.pathParam("src")); + String dstFmt = ctx.pathParam("dst"); + String direction = ctx.queryParam("direction", "forward"); + String edgesFmt = ctx.queryParam("edges", "*"); + String traversal = ctx.queryParam("traversal", "dfs"); + + Walk walk = new Walk(graph, src, dstFmt, edgesFmt, direction, traversal); + ctx.json(walk.getPath()); + }); + + app.exception(IllegalArgumentException.class, (e, ctx) -> { + ctx.status(400); + ctx.result(e.getMessage()); + }); + } + + private static void checkQueryStrings(Context ctx, String allowedFmt) { + Map> queryParamMap = ctx.queryParamMap(); + for (String key : queryParamMap.keySet()) { + if (!key.matches(allowedFmt)) { + throw new IllegalArgumentException("Unknown query string: " + key); + } + } } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/Node.java b/api/server/src/main/java/org/softwareheritage/graph/Node.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/Node.java @@ -0,0 +1,32 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +public class Node { + public enum Type { + CNT, + DIR, + REL, + REV, + SNP; + + public static Node.Type fromStr(String strType) { + return Node.Type.valueOf(strType.toUpperCase()); + } + + public static ArrayList parse(String strType) { + ArrayList types = new ArrayList<>(); + + if (strType.equals("*")) { + List nodeTypes = Arrays.asList(Node.Type.values()); + types.addAll(nodeTypes); + } else { + types.add(Node.Type.fromStr(strType)); + } + + return types; + } + } +} diff --git a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java --- a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java +++ b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java @@ -2,11 +2,13 @@ import com.fasterxml.jackson.annotation.JsonValue; +import org.softwareheritage.graph.Node; + public class SwhId { public static final int HASH_LENGTH = 40; String swhId; - String type; + Node.Type type; String hash; // SWH ID format: 'swh:1:type:hash' @@ -19,10 +21,11 @@ throw new IllegalArgumentException("Expected SWH ID format to be 'swh:1:type:hash', got: " + swhId); } - this.type = parts[2]; + String type = parts[2]; if (!type.matches("cnt|dir|rel|rev|snp")) { throw new IllegalArgumentException("Unknown SWH ID type in: " + swhId); } + this.type = Node.Type.fromStr(type); this.hash = parts[3]; if (!hash.matches("[0-9a-f]{" + HASH_LENGTH + "}")) { @@ -40,6 +43,11 @@ } @Override + public int hashCode() { + return swhId.hashCode(); + } + + @Override public String toString() { return swhId; } @@ -49,7 +57,7 @@ return swhId; } - public String getType() { + public Node.Type getType() { return type; } diff --git a/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java b/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java --- a/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java +++ b/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java @@ -1,6 +1,7 @@ package org.softwareheritage.graph; import java.util.ArrayList; +import java.util.Collections; import com.fasterxml.jackson.annotation.JsonValue; @@ -44,6 +45,10 @@ return path.size(); } + public void reverse() { + Collections.reverse(path); + } + @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java --- a/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java @@ -1,46 +1,59 @@ package org.softwareheritage.graph.algo; import java.util.ArrayList; +import java.util.LinkedHashSet; import java.util.Stack; import it.unimi.dsi.big.webgraph.LazyLongIterator; +import org.softwareheritage.graph.AllowedEdges; import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.Node; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.SwhPath; public class Visit { + public enum OutputFmt { ONLY_NODES, ONLY_PATHS, NODES_AND_PATHS } + Graph graph; boolean useTransposed; - String allowedEdges; - Stack currentPath; + AllowedEdges edges; + + // LinkedHashSet is necessary to preserve insertion order + LinkedHashSet nodes; ArrayList paths; + Stack currentPath; - public Visit(Graph graph, SwhId swhId, String allowedEdges, String algorithm, String direction) { - if (!algorithm.matches("dfs|bfs")) { - throw new IllegalArgumentException("Unknown traversal algorithm: " + algorithm); - } + public Visit(Graph graph, SwhId src, String edgesFmt, String direction, OutputFmt output) { if (!direction.matches("forward|backward")) { throw new IllegalArgumentException("Unknown traversal direction: " + direction); } this.graph = graph; this.useTransposed = (direction.equals("backward")); - this.allowedEdges = allowedEdges; + this.edges = new AllowedEdges(edgesFmt); + this.nodes = new LinkedHashSet(); this.paths = new ArrayList(); this.currentPath = new Stack(); - if (algorithm.equals("dfs")) { - dfs(graph.getNodeId(swhId)); + long nodeId = graph.getNodeId(src); + if (output == OutputFmt.ONLY_NODES) { + dfsOutputOnlyNodes(nodeId); + } else { + dfs(nodeId); } } - // Allow Jackson JSON to only serialize the 'paths' field + public LinkedHashSet getNodes() { + return nodes; + } + public ArrayList getPaths() { return paths; } private void dfs(long currentNodeId) { + nodes.add(graph.getSwhId(currentNodeId)); currentPath.push(currentNodeId); long degree = graph.degree(currentNodeId, useTransposed); @@ -49,7 +62,9 @@ while (degree-- > 0) { long neighborNodeId = neighbors.nextLong(); - if (isEdgeAllowed(currentNodeId, neighborNodeId)) { + Node.Type currentNodeType = graph.getSwhId(currentNodeId).getType(); + Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType(); + if (edges.isAllowed(currentNodeType, neighborNodeType)) { dfs(neighborNodeId); visitedNeighbors++; } @@ -66,15 +81,18 @@ currentPath.pop(); } - private boolean isEdgeAllowed(long currentNodeId, long neighborNodeId) { - if (allowedEdges.equals("all")) { - return true; - } + private void dfsOutputOnlyNodes(long currentNodeId) { + nodes.add(graph.getSwhId(currentNodeId)); + long degree = graph.degree(currentNodeId, useTransposed); + LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed); - String currentType = graph.getSwhId(currentNodeId).getType(); - String neighborType = graph.getSwhId(neighborNodeId).getType(); - String edgeType = currentType + ":" + neighborType; - String edgeTypeRev = neighborType + ":" + currentType; - return allowedEdges.contains(edgeType) || allowedEdges.contains(edgeTypeRev); + while (degree-- > 0) { + long neighborNodeId = neighbors.nextLong(); + Node.Type currentNodeType = graph.getSwhId(currentNodeId).getType(); + Node.Type neighborNodeType = graph.getSwhId(neighborNodeId).getType(); + if (edges.isAllowed(currentNodeType, neighborNodeType)) { + dfsOutputOnlyNodes(neighborNodeId); + } + } } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Walk.java @@ -0,0 +1,148 @@ +package org.softwareheritage.graph.algo; + +import java.util.Stack; +import java.util.Queue; +import java.util.LinkedList; + +import it.unimi.dsi.big.webgraph.LazyLongIterator; +import it.unimi.dsi.bits.LongArrayBitVector; +import it.unimi.dsi.fastutil.longs.LongBigArrays; + +import org.softwareheritage.graph.AllowedEdges; +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.Node; +import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.SwhPath; + +public class Walk { + Graph graph; + boolean useTransposed; + AllowedEdges edges; + + SwhPath path; + long[][] nodeParent; + + public Walk( + Graph graph, SwhId src, String dstFmt, String edgesFmt, String direction, String traversal) { + if (!traversal.matches("dfs|bfs")) { + throw new IllegalArgumentException("Unknown traversal algorithm: " + traversal); + } + 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.path = new SwhPath(); + this.nodeParent = LongBigArrays.newBigArray(graph.getNbNodes()); + LongBigArrays.fill(nodeParent, -1); + + long srcNodeId = graph.getNodeId(src); + long dstNodeId; + if (traversal.equals("dfs")) { + dstNodeId = dfs(srcNodeId, dstFmt); + } else { + dstNodeId = bfs(srcNodeId, dstFmt); + } + + if (dstNodeId == -1) { + throw new IllegalArgumentException("Unable to find destination point: " + dstFmt); + } else { + backtracking(srcNodeId, dstNodeId); + } + } + + public SwhPath getPath() { + return path; + } + + private void backtracking(long srcNodeId, long dstNodeId) { + long currentNodeId = dstNodeId; + while (currentNodeId != srcNodeId) { + path.add(graph.getSwhId(currentNodeId)); + currentNodeId = LongBigArrays.get(nodeParent, currentNodeId); + } + path.add(graph.getSwhId(srcNodeId)); + path.reverse(); + } + + private long dfs(long srcNodeId, String dstFmt) { + Stack stack = new Stack(); + LongArrayBitVector visited = LongArrayBitVector.ofLength(graph.getNbNodes()); + + stack.push(srcNodeId); + visited.set(srcNodeId); + + while (!stack.isEmpty()) { + long currentNodeId = stack.pop(); + SwhId currentSwhId = graph.getSwhId(currentNodeId); + if (isDestinationNode(currentSwhId, dstFmt)) { + return currentNodeId; + } + + long degree = graph.degree(currentNodeId, useTransposed); + LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed); + + while (degree-- > 0) { + long neighborNodeId = neighbors.nextLong(); + SwhId neighborSwhId = graph.getSwhId(neighborNodeId); + if (!visited.getBoolean(neighborNodeId) + && edges.isAllowed(currentSwhId.getType(), neighborSwhId.getType())) { + stack.push(neighborNodeId); + visited.set(neighborNodeId); + LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId); + } + } + } + + return -1; + } + + private long bfs(long srcNodeId, String dstFmt) { + Queue queue = new LinkedList(); + LongArrayBitVector visited = LongArrayBitVector.ofLength(graph.getNbNodes()); + + queue.add(srcNodeId); + visited.set(srcNodeId); + + while (!queue.isEmpty()) { + long currentNodeId = queue.poll(); + SwhId currentSwhId = graph.getSwhId(currentNodeId); + if (isDestinationNode(currentSwhId, dstFmt)) { + return currentNodeId; + } + + long degree = graph.degree(currentNodeId, useTransposed); + LazyLongIterator neighbors = graph.neighbors(currentNodeId, useTransposed); + + while (degree-- > 0) { + long neighborNodeId = neighbors.nextLong(); + SwhId neighborSwhId = graph.getSwhId(neighborNodeId); + if (!visited.getBoolean(neighborNodeId) + && edges.isAllowed(currentSwhId.getType(), neighborSwhId.getType())) { + queue.add(neighborNodeId); + visited.set(neighborNodeId); + LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId); + } + } + } + + return -1; + } + + private boolean isDestinationNode(SwhId swhId, String dstFmt) { + // dstFmt is either a SwhId... + if (swhId.toString().equals(dstFmt)) { + return true; + } + + // ...or a Node.Type + try { + Node.Type dstType = Node.Type.fromStr(dstFmt); + return (swhId.getType().equals(dstType)); + } catch (IllegalArgumentException e) { + return false; + } + } +} diff --git a/api/server/src/test/java/org/softwareheritage/graph/EdgesTest.java b/api/server/src/test/java/org/softwareheritage/graph/EdgesTest.java new file mode 100644 --- /dev/null +++ b/api/server/src/test/java/org/softwareheritage/graph/EdgesTest.java @@ -0,0 +1,112 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.junit.Test; +import static org.junit.Assert.assertTrue; + +import org.softwareheritage.graph.AllowedEdges; +import org.softwareheritage.graph.Node; + +public class EdgesTest { + class EdgeType { + Node.Type src; + Node.Type dst; + + public EdgeType(Node.Type src, Node.Type dst) { + this.src = src; + this.dst = dst; + } + + @Override + public boolean equals(Object otherObj) { + if (otherObj == this) return true; + if (!(otherObj instanceof EdgeType)) return false; + + EdgeType other = (EdgeType) otherObj; + return src == other.src && dst == other.dst; + } + } + + void assertEdgeRestriction(AllowedEdges edges, ArrayList expectedAllowed) { + Node.Type[] nodeTypes = Node.Type.values(); + for (Node.Type src : nodeTypes) { + for (Node.Type dst : nodeTypes) { + EdgeType edge = new EdgeType(src, dst); + boolean isAllowed = edges.isAllowed(src, dst); + boolean isExpected = false; + for (EdgeType expected : expectedAllowed) { + if (expected.equals(edge)) { + isExpected = true; + break; + } + } + + assertTrue("Edge type: " + src + " -> " + dst, isAllowed == isExpected); + } + } + } + + @Test + public void dirToDirDirToCntEdges() { + AllowedEdges edges = new AllowedEdges("dir:dir,dir:cnt"); + ArrayList expected = new ArrayList<>(); + expected.add(new EdgeType(Node.Type.DIR, Node.Type.DIR)); + expected.add(new EdgeType(Node.Type.DIR, Node.Type.CNT)); + assertEdgeRestriction(edges, expected); + } + + @Test + public void relToRevRevToRevRevToDirEdges() { + AllowedEdges edges = new AllowedEdges("rel:rev,rev:rev,rev:dir"); + ArrayList expected = new ArrayList<>(); + expected.add(new EdgeType(Node.Type.REL, Node.Type.REV)); + expected.add(new EdgeType(Node.Type.REV, Node.Type.REV)); + expected.add(new EdgeType(Node.Type.REV, Node.Type.DIR)); + assertEdgeRestriction(edges, expected); + } + + @Test + public void revToAllDirToDirEdges() { + AllowedEdges edges = new AllowedEdges("rev:*,dir:dir"); + ArrayList expected = new ArrayList<>(); + for (Node.Type dst : Node.Type.values()) { + expected.add(new EdgeType(Node.Type.REV, dst)); + } + expected.add(new EdgeType(Node.Type.DIR, Node.Type.DIR)); + assertEdgeRestriction(edges, expected); + } + + @Test + public void allToCntEdges() { + AllowedEdges edges = new AllowedEdges("*:cnt"); + ArrayList expected = new ArrayList<>(); + for (Node.Type src : Node.Type.values()) { + expected.add(new EdgeType(src, Node.Type.CNT)); + } + assertEdgeRestriction(edges, expected); + } + + @Test + public void allEdges() { + AllowedEdges edges = new AllowedEdges("*:*"); + AllowedEdges edges2 = new AllowedEdges("*"); + ArrayList expected = new ArrayList<>(); + for (Node.Type src : Node.Type.values()) { + for (Node.Type dst : Node.Type.values()) { + expected.add(new EdgeType(src, dst)); + } + } + assertEdgeRestriction(edges, expected); + assertEdgeRestriction(edges2, expected); + } + + @Test + public void noEdges() { + AllowedEdges edges = new AllowedEdges(""); + AllowedEdges edges2 = new AllowedEdges(null); + ArrayList expected = new ArrayList<>(); + assertEdgeRestriction(edges, expected); + assertEdgeRestriction(edges2, expected); + } +} diff --git a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java --- a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java @@ -1,6 +1,7 @@ package org.softwareheritage.graph; import java.util.ArrayList; +import java.util.LinkedHashSet; import org.junit.Assert; import org.junit.Test; @@ -13,16 +14,33 @@ import org.softwareheritage.graph.algo.Visit; public class VisitTest extends GraphTest { - void assertEqualSwhPaths(ArrayList expecteds, ArrayList actuals) { + Visit.OutputFmt outputFmt = Visit.OutputFmt.NODES_AND_PATHS; + + private void assertEqualPaths(ArrayList expecteds, ArrayList actuals) { + Assert.assertThat(expecteds, containsInAnyOrder(actuals.toArray())); + } + + private void assertEqualNodes(LinkedHashSet expecteds, LinkedHashSet actuals) { Assert.assertThat(expecteds, containsInAnyOrder(actuals.toArray())); } + private void assertSameNodesFromPaths(ArrayList paths, LinkedHashSet nodes) { + LinkedHashSet expectedNodes = new LinkedHashSet(); + for (SwhPath path : paths) { + for (SwhId node : path.getPath()) { + expectedNodes.add(node); + } + } + assertEqualNodes(expectedNodes, nodes); + } + @Test - public void dfsForwardFromRoot() { + public void forwardFromRoot() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -107,15 +125,17 @@ "swh:1:cnt:0000000000000000000000000000000000000001" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardFromMiddle() { + public void forwardFromMiddle() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -150,15 +170,17 @@ "swh:1:cnt:0000000000000000000000000000000000000011" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardFromLeaf() { + public void forwardFromLeaf() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "*", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -166,15 +188,17 @@ "swh:1:cnt:0000000000000000000000000000000000000004" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsBackwardFromRoot() { + public void backwardFromRoot() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); + Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -182,15 +206,17 @@ "swh:1:snp:0000000000000000000000000000000000000020" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsBackwardFromMiddle() { + public void backwardFromMiddle() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); + Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -201,15 +227,17 @@ "swh:1:rel:0000000000000000000000000000000000000019" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsBackwardFromLeaf() { + public void backwardFromLeaf() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); + Visit visit = new Visit(graph, swhId, "*", "backward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -250,15 +278,17 @@ "swh:1:snp:0000000000000000000000000000000000000020" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardOnlySnpRevAllowed() { + public void forwardSnpToRev() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Visit visit = new Visit(graph, swhId, "snp:rev", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "snp:rev", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -267,15 +297,17 @@ "swh:1:rev:0000000000000000000000000000000000000009" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardOnlyRevRelAllowed() { + public void forwardRelToRevRevToRev() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rel:0000000000000000000000000000000000000010"); - Visit visit = new Visit(graph, swhId, "rel:rev,rev:rev", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "rel:rev,rev:rev", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -285,15 +317,17 @@ "swh:1:rev:0000000000000000000000000000000000000003" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardOnlyRevDirCntAllowed() { + public void forwardRevToAllDirToAll() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000013"); - Visit visit = new Visit(graph, swhId, "rev:rev,rev:dir,dir:dir,dir:cnt", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "rev:*,dir:*", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -371,15 +405,49 @@ "swh:1:cnt:0000000000000000000000000000000000000001" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsForwardNoEdgesAllowed() { + public void forwardSnpToAllRevToAll() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Visit visit = new Visit(graph, swhId, "", "dfs", "forward"); + Visit visit = new Visit(graph, swhId, "snp:*,rev:*", "forward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); + + ArrayList expectedPaths = new ArrayList(); + expectedPaths.add( + new SwhPath( + "swh:1:snp:0000000000000000000000000000000000000020", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:rev:0000000000000000000000000000000000000003", + "swh:1:dir:0000000000000000000000000000000000000002" + )); + expectedPaths.add( + new SwhPath( + "swh:1:snp:0000000000000000000000000000000000000020", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:dir:0000000000000000000000000000000000000008" + )); + expectedPaths.add( + new SwhPath( + "swh:1:snp:0000000000000000000000000000000000000020", + "swh:1:rel:0000000000000000000000000000000000000010" + )); + + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); + } + + @Test + public void forwardNoEdges() { + Graph graph = getGraph(); + SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + Visit visit = new Visit(graph, swhId, "", "forward", outputFmt); + ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -387,15 +455,17 @@ "swh:1:snp:0000000000000000000000000000000000000020" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsBackwardOnlyRevRelAllowed() { + public void backwardRevToRevRevToRel() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); - Visit visit = new Visit(graph, swhId, "rev:rev,rev:rel", "dfs", "backward"); + Visit visit = new Visit(graph, swhId, "rev:rev,rev:rel", "backward", outputFmt); ArrayList paths = visit.getPaths(); + LinkedHashSet nodes = visit.getNodes(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -413,26 +483,49 @@ "swh:1:rel:0000000000000000000000000000000000000010" )); - assertEqualSwhPaths(expectedPaths, paths); + assertEqualPaths(expectedPaths, paths); + assertSameNodesFromPaths(expectedPaths, nodes); } @Test - public void dfsBackwardAllowedEdgesNotOrderSensitive() { + public void forwardFromRootNodesOnly() { Graph graph = getGraph(); - SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Visit visit1 = new Visit(graph, swhId, "cnt:dir", "dfs", "backward"); - Visit visit2 = new Visit(graph, swhId, "dir:cnt", "dfs", "backward"); - ArrayList paths1 = visit1.getPaths(); - ArrayList paths2 = visit2.getPaths(); - - ArrayList expectedPaths = new ArrayList(); - expectedPaths.add( - new SwhPath( - "swh:1:cnt:0000000000000000000000000000000000000004", - "swh:1:dir:0000000000000000000000000000000000000006" - )); + SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + Visit visit = new Visit(graph, swhId, "*", "forward", Visit.OutputFmt.ONLY_NODES); + LinkedHashSet nodes = visit.getNodes(); + + LinkedHashSet expectedNodes = new LinkedHashSet(); + expectedNodes.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009")); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003")); + expectedNodes.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002")); + expectedNodes.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000008")); + expectedNodes.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000006")); + expectedNodes.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedNodes.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedNodes.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); + + assertEqualNodes(expectedNodes, nodes); + } - assertEqualSwhPaths(expectedPaths, paths1); - assertEqualSwhPaths(expectedPaths, paths2); + @Test + public void backwardRevToAllNodesOnly() { + Graph graph = getGraph(); + SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); + Visit visit = new Visit(graph, swhId, "rev:*", "backward", Visit.OutputFmt.ONLY_NODES); + LinkedHashSet nodes = visit.getNodes(); + + LinkedHashSet expectedNodes = new LinkedHashSet(); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003")); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009")); + expectedNodes.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); + expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000018")); + expectedNodes.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019")); + + assertEqualNodes(expectedNodes, nodes); } } diff --git a/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java new file mode 100644 --- /dev/null +++ b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java @@ -0,0 +1,183 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; +import java.util.LinkedHashSet; + +import org.junit.Assert; +import org.junit.Test; +import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder; + +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.SwhPath; +import org.softwareheritage.graph.algo.Walk; + +public class WalkTest extends GraphTest { + @Test + public void forwardRootToLeaf() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); + String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:snp:0000000000000000000000000000000000000020", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:dir:0000000000000000000000000000000000000008", + "swh:1:dir:0000000000000000000000000000000000000006", + "swh:1:cnt:0000000000000000000000000000000000000005" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + // Most of DFS and BFS traversal outputs are the same because it is a small test graph + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } + + @Test + public void forwardLeafToLeaf() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"); + String dstFmt = "cnt"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "forward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:cnt:0000000000000000000000000000000000000007" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } + + @Test + public void forwardRevToRev() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018"); + String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "forward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "forward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:rev:0000000000000000000000000000000000000018", + "swh:1:rev:0000000000000000000000000000000000000013", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:rev:0000000000000000000000000000000000000003" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } + + @Test + public void backwardRevToRev() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); + String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "backward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:rev", "backward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:rev:0000000000000000000000000000000000000003", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:rev:0000000000000000000000000000000000000013", + "swh:1:rev:0000000000000000000000000000000000000018" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } + + @Test + public void backwardCntToFirstSnp() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"); + String dstFmt = "snp"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "*", "backward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "*", "backward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:cnt:0000000000000000000000000000000000000001", + "swh:1:dir:0000000000000000000000000000000000000002", + "swh:1:rev:0000000000000000000000000000000000000003", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:snp:0000000000000000000000000000000000000020" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + SwhPath bfsExpectedPath = + new SwhPath( + "swh:1:cnt:0000000000000000000000000000000000000001", + "swh:1:dir:0000000000000000000000000000000000000008", + "swh:1:rev:0000000000000000000000000000000000000009", + "swh:1:snp:0000000000000000000000000000000000000020" + ); + Assert.assertEquals(bfsExpectedPath, bfsPath); + } + + @Test + public void forwardRevToFirstCnt() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000013"); + String dstFmt = "cnt"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "rev:*,dir:*", "forward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "rev:*,dir:*", "forward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:rev:0000000000000000000000000000000000000013", + "swh:1:dir:0000000000000000000000000000000000000012", + "swh:1:cnt:0000000000000000000000000000000000000011" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } + + @Test + public void backwardDirToFirstRel() { + Graph graph = getGraph(); + SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000016"); + String dstFmt = "rel"; + + Walk dfsWalk = new Walk(graph, src, dstFmt, "dir:dir,dir:rev,rev:*", "backward", "dfs"); + Walk bfsWalk = new Walk(graph, src, dstFmt, "dir:dir,dir:rev,rev:*", "backward", "bfs"); + + SwhPath dfsPath = dfsWalk.getPath(); + SwhPath dfsExpectedPath = + new SwhPath( + "swh:1:dir:0000000000000000000000000000000000000016", + "swh:1:dir:0000000000000000000000000000000000000017", + "swh:1:rev:0000000000000000000000000000000000000018", + "swh:1:rel:0000000000000000000000000000000000000019" + ); + Assert.assertEquals(dfsExpectedPath, dfsPath); + + SwhPath bfsPath = bfsWalk.getPath(); + Assert.assertEquals(dfsExpectedPath, bfsPath); + } +}