diff --git a/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java b/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java --- a/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java +++ b/api/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java @@ -2,13 +2,17 @@ import java.util.ArrayList; +import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Node; public class AllowedEdges { + Graph graph; // First dimension is source node type, second dimension is destination node type boolean[][] allowed; - public AllowedEdges(String edgesFmt) { + public AllowedEdges(Graph graph, String edgesFmt) { + this.graph = graph; + int nbNodeTypes = Node.Type.values().length; this.allowed = new boolean[nbNodeTypes][nbNodeTypes]; // Special values (null, empty, "*") @@ -42,7 +46,13 @@ } } - public boolean isAllowed(Node.Type currentType, Node.Type neighborType) { - return allowed[currentType.ordinal()][neighborType.ordinal()]; + public boolean isAllowed(long srcNodeId, long dstNodeId) { + Node.Type srcType = graph.getNodeType(srcNodeId); + Node.Type dstType = graph.getNodeType(dstNodeId); + return isAllowed(srcType, dstType); + } + + public boolean isAllowed(Node.Type srcType, Node.Type dstType) { + return allowed[srcType.ordinal()][dstType.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 @@ -10,10 +10,10 @@ import io.javalin.http.Context; import io.javalin.plugin.json.JavalinJackson; +import org.softwareheritage.graph.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.algo.Stats; -import org.softwareheritage.graph.algo.Traversal; public class App { public static void main(String[] args) throws IOException { @@ -55,8 +55,8 @@ String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); - Traversal traversal = new Traversal(graph, direction, edgesFmt); - ctx.json(traversal.leavesEndpoint(src)); + Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); + ctx.json(endpoint.leaves(src)); }); app.get("/neighbors/:src", ctx -> { @@ -64,8 +64,8 @@ String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); - Traversal traversal = new Traversal(graph, direction, edgesFmt); - ctx.json(traversal.neighborsEndpoint(src)); + Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); + ctx.json(endpoint.neighbors(src)); }); // TODO: anonymous class to return both nodes/paths? (waiting on node types map merged/refactor) @@ -83,8 +83,8 @@ String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); - Traversal traversal = new Traversal(graph, direction, edgesFmt); - ctx.json(traversal.visitNodesEndpoint(src)); + Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); + ctx.json(endpoint.visitNodes(src)); }); app.get("/visit/paths/:src", ctx -> { @@ -92,8 +92,8 @@ String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); - Traversal traversal = new Traversal(graph, direction, edgesFmt); - ctx.json(traversal.visitPathsEndpoint(src)); + Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); + ctx.json(endpoint.visitPaths(src)); }); app.get("/walk/:src/:dst", ctx -> { @@ -103,8 +103,8 @@ String edgesFmt = ctx.queryParam("edges", "*"); String algorithm = ctx.queryParam("traversal", "dfs"); - Traversal traversal = new Traversal(graph, direction, edgesFmt); - ctx.json(traversal.walkEndpoint(src, dstFmt, algorithm)); + Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); + ctx.json(endpoint.walk(src, dstFmt, algorithm)); }); app.exception(IllegalArgumentException.class, (e, ctx) -> { diff --git a/api/server/src/main/java/org/softwareheritage/graph/Endpoint.java b/api/server/src/main/java/org/softwareheritage/graph/Endpoint.java new file mode 100644 --- /dev/null +++ b/api/server/src/main/java/org/softwareheritage/graph/Endpoint.java @@ -0,0 +1,85 @@ +package org.softwareheritage.graph; + +import java.util.ArrayList; + +import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhId; +import org.softwareheritage.graph.SwhPath; +import org.softwareheritage.graph.algo.Traversal; + +public class Endpoint { + Graph graph; + Traversal traversal; + + public Endpoint(Graph graph, String direction, String edgesFmt) { + this.graph = graph; + this.traversal = new Traversal(graph, direction, edgesFmt); + } + + private ArrayList convertNodesToSwhIds(ArrayList nodeIds) { + ArrayList swhIds = new ArrayList<>(); + for (long nodeId : nodeIds) { + swhIds.add(graph.getSwhId(nodeId)); + } + return swhIds; + } + + private SwhPath convertNodesToSwhPath(ArrayList nodeIds) { + SwhPath path = new SwhPath(); + for (long nodeId : nodeIds) { + path.add(graph.getSwhId(nodeId)); + } + return path; + } + + private ArrayList convertPathsToSwhIds(ArrayList> pathsNodeId) { + ArrayList paths = new ArrayList<>(); + for (ArrayList path : pathsNodeId) { + paths.add(convertNodesToSwhPath(path)); + } + return paths; + } + + public ArrayList leaves(SwhId src) { + long srcNodeId = graph.getNodeId(src); + ArrayList nodeIds = traversal.leaves(srcNodeId); + return convertNodesToSwhIds(nodeIds); + } + + public ArrayList neighbors(SwhId src) { + long srcNodeId = graph.getNodeId(src); + ArrayList nodeIds = traversal.neighbors(srcNodeId); + return convertNodesToSwhIds(nodeIds); + } + + public SwhPath walk(SwhId src, String dstFmt, String algorithm) { + long srcNodeId = graph.getNodeId(src); + ArrayList nodeIds = null; + + // Destination is either a SWH ID or a node type + try { + SwhId dstSwhId = new SwhId(dstFmt); + long dstNodeId = graph.getNodeId(dstSwhId); + nodeIds = traversal.walk(srcNodeId, dstNodeId, algorithm); + } catch (IllegalArgumentException ignored1) { + try { + Node.Type dstType = Node.Type.fromStr(dstFmt); + nodeIds = traversal.walk(srcNodeId, dstType, algorithm); + } catch (IllegalArgumentException ignored2) { } + } + + return convertNodesToSwhPath(nodeIds); + } + + public ArrayList visitNodes(SwhId src) { + long srcNodeId = graph.getNodeId(src); + ArrayList nodeIds = traversal.visitNodes(srcNodeId); + return convertNodesToSwhIds(nodeIds); + } + + public ArrayList visitPaths(SwhId src) { + long srcNodeId = graph.getNodeId(src); + ArrayList> paths = traversal.visitPaths(srcNodeId); + return convertPathsToSwhIds(paths); + } +} diff --git a/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java b/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java --- a/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java +++ b/api/server/src/main/java/org/softwareheritage/graph/Neighbors.java @@ -6,19 +6,18 @@ import org.softwareheritage.graph.AllowedEdges; import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.SwhId; public class Neighbors implements Iterable { Graph graph; boolean useTransposed; AllowedEdges edges; - SwhId src; + long srcNodeId; - public Neighbors(Graph graph, boolean useTransposed, AllowedEdges edges, SwhId src) { + public Neighbors(Graph graph, boolean useTransposed, AllowedEdges edges, long srcNodeId) { this.graph = graph; this.useTransposed = useTransposed; this.edges = edges; - this.src = src; + this.srcNodeId = srcNodeId; } @Override @@ -32,8 +31,6 @@ long[][] neighbors; public NeighborsIterator() { - long srcNodeId = graph.getNodeId(src); - this.nextNeighborIdx = -1; this.nbNeighbors = graph.degree(srcNodeId, useTransposed); this.neighbors = graph.neighbors(srcNodeId, useTransposed); @@ -43,8 +40,7 @@ public boolean hasNext() { for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) { long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx); - SwhId nextSwhId = graph.getSwhId(nextNodeId); - if (edges.isAllowed(src.getType(), nextSwhId.getType())) { + if (edges.isAllowed(srcNodeId, nextNodeId)) { nextNeighborIdx = lookAheadIdx; return true; } 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,7 +1,6 @@ package org.softwareheritage.graph; import java.util.ArrayList; -import java.util.Collections; import com.fasterxml.jackson.annotation.JsonValue; @@ -45,10 +44,6 @@ 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/Traversal.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java --- a/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java @@ -13,7 +13,6 @@ import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Neighbors; import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.SwhId; public class Traversal { Graph graph; @@ -32,82 +31,26 @@ this.graph = graph; this.useTransposed = (direction.equals("backward")); - this.edges = new AllowedEdges(edgesFmt); + this.edges = new AllowedEdges(graph, edgesFmt); long nbNodes = graph.getNbNodes(); this.visited = LongArrayBitVector.ofLength(nbNodes); this.nodeParent = LongBigArrays.newBigArray(nbNodes); } - // TODO: better separation between internal/external ids (waiting on node types map to be merged) - private ArrayList convertToSwhIds(ArrayList nodeIds) { - ArrayList swhIds = new ArrayList(); - for (long nodeId : nodeIds) { - swhIds.add(graph.getSwhId(nodeId)); - } - return swhIds; - } - - public ArrayList leavesEndpoint(SwhId src) { - long nodeId = graph.getNodeId(src); - ArrayList leavesNodeIds = leavesInternalEndpoint(nodeId); - return convertToSwhIds(leavesNodeIds); - } - - public ArrayList neighborsEndpoint(SwhId src) { - long nodeId = graph.getNodeId(src); - ArrayList neighborsNodeIds = neighborsInternalEndpoint(nodeId); - return convertToSwhIds(neighborsNodeIds); - } - - public ArrayList walkEndpoint(SwhId src, String dstFmt, String traversal) { - if (!traversal.matches("dfs|bfs")) { - throw new IllegalArgumentException("Unknown traversal algorithm: " + traversal); - } - - long srcNodeId = graph.getNodeId(src); - long dstNodeId = (traversal.equals("dfs")) ? dfs(srcNodeId, dstFmt) : bfs(srcNodeId, dstFmt); - if (dstNodeId == -1) { - throw new IllegalArgumentException("Unable to find destination point: " + dstFmt); - } - - ArrayList path = backtracking(srcNodeId, dstNodeId); - return convertToSwhIds(path); - } - - public ArrayList visitNodesEndpoint(SwhId src) { - long nodeId = graph.getNodeId(src); - ArrayList nodes = visitNodesInternalEndpoint(nodeId); - return convertToSwhIds(nodes); - } - - public ArrayList> visitPathsEndpoint(SwhId src) { - long nodeId = graph.getNodeId(src); - ArrayList> pathNodeIds = new ArrayList<>(); - Stack currentPath = new Stack(); - visitPathsInternalEndpoint(nodeId, pathNodeIds, currentPath); - - ArrayList> paths = new ArrayList<>(); - for (ArrayList nodeIds : pathNodeIds) { - paths.add(convertToSwhIds(nodeIds)); - } - return paths; - } - - private ArrayList leavesInternalEndpoint(long srcNodeId) { - ArrayList leaves = new ArrayList(); + public ArrayList leaves(long srcNodeId) { + ArrayList nodeIds = new ArrayList(); Stack stack = new Stack(); - this.visited.clear(); + this.visited.fill(false); stack.push(srcNodeId); visited.set(srcNodeId); while (!stack.isEmpty()) { long currentNodeId = stack.pop(); - SwhId currentSwhId = graph.getSwhId(currentNodeId); long neighborsCnt = 0; - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) { + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { neighborsCnt++; if (!visited.getBoolean(neighborNodeId)) { stack.push(neighborNodeId); @@ -116,44 +59,58 @@ } if (neighborsCnt == 0) { - leaves.add(currentNodeId); + nodeIds.add(currentNodeId); } } - return leaves; + return nodeIds; } - private ArrayList neighborsInternalEndpoint(long srcNodeId) { - SwhId srcSwhId = graph.getSwhId(srcNodeId); - ArrayList neighbors = new ArrayList(); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcSwhId)) { - neighbors.add(neighborNodeId); + public ArrayList neighbors(long srcNodeId) { + ArrayList nodeIds = new ArrayList(); + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) { + nodeIds.add(neighborNodeId); } - return neighbors; + return nodeIds; } - private ArrayList visitNodesInternalEndpoint(long srcNodeId) { - // No specific destination point - String dstFmt = null; - dfs(srcNodeId, dstFmt); + public ArrayList visitNodes(long srcNodeId) { + ArrayList nodeIds = new ArrayList(); + Stack stack = new Stack(); + this.visited.fill(false); + + stack.push(srcNodeId); + visited.set(srcNodeId); + + while (!stack.isEmpty()) { + long currentNodeId = stack.pop(); + nodeIds.add(currentNodeId); - ArrayList nodes = new ArrayList(); - for (long nodeId = 0; nodeId < graph.getNbNodes(); nodeId++) { - if (this.visited.getBoolean(nodeId)) { - nodes.add(nodeId); + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + if (!visited.getBoolean(neighborNodeId)) { + stack.push(neighborNodeId); + visited.set(neighborNodeId); + } } } - return nodes; + + return nodeIds; + } + + public ArrayList> visitPaths(long srcNodeId) { + ArrayList> paths = new ArrayList<>(); + Stack currentPath = new Stack(); + visitPathsInternal(srcNodeId, paths, currentPath); + return paths; } - private void visitPathsInternalEndpoint( + private void visitPathsInternal( long currentNodeId, ArrayList> paths, Stack currentPath) { - SwhId currentSwhId = graph.getSwhId(currentNodeId); currentPath.push(currentNodeId); long visitedNeighbors = 0; - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) { - visitPathsInternalEndpoint(neighborNodeId, paths, currentPath); + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + visitPathsInternal(neighborNodeId, paths, currentPath); visitedNeighbors++; } @@ -168,33 +125,38 @@ currentPath.pop(); } - private ArrayList backtracking(long srcNodeId, long dstNodeId) { - ArrayList path = new ArrayList(); - long currentNodeId = dstNodeId; - while (currentNodeId != srcNodeId) { - path.add(currentNodeId); - currentNodeId = LongBigArrays.get(nodeParent, currentNodeId); + public ArrayList walk(long srcNodeId, T dst, String algorithm) { + long dstNodeId = -1; + if (algorithm.equals("dfs")) { + dstNodeId = walkInternalDfs(srcNodeId, dst); + } else if (algorithm.equals("bfs")) { + dstNodeId = walkInternalBfs(srcNodeId, dst); + } else { + throw new IllegalArgumentException("Unknown traversal algorithm: " + algorithm); } - path.add(srcNodeId); - Collections.reverse(path); - return path; + + if (dstNodeId == -1) { + throw new IllegalArgumentException("Unable to find destination point: " + dst); + } + + ArrayList nodeIds = backtracking(srcNodeId, dstNodeId); + return nodeIds; } - private long dfs(long srcNodeId, String dstFmt) { + private long walkInternalDfs(long srcNodeId, T dst) { Stack stack = new Stack(); - this.visited.clear(); + this.visited.fill(false); stack.push(srcNodeId); visited.set(srcNodeId); while (!stack.isEmpty()) { long currentNodeId = stack.pop(); - SwhId currentSwhId = graph.getSwhId(currentNodeId); - if (isDestinationNode(currentSwhId, dstFmt)) { + if (isDstNode(currentNodeId, dst)) { return currentNodeId; } - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) { + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { if (!visited.getBoolean(neighborNodeId)) { stack.push(neighborNodeId); visited.set(neighborNodeId); @@ -206,21 +168,20 @@ return -1; } - private long bfs(long srcNodeId, String dstFmt) { + private long walkInternalBfs(long srcNodeId, T dst) { Queue queue = new LinkedList(); - this.visited.clear(); + this.visited.fill(false); queue.add(srcNodeId); visited.set(srcNodeId); while (!queue.isEmpty()) { long currentNodeId = queue.poll(); - SwhId currentSwhId = graph.getSwhId(currentNodeId); - if (isDestinationNode(currentSwhId, dstFmt)) { + if (isDstNode(currentNodeId, dst)) { return currentNodeId; } - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentSwhId)) { + for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { if (!visited.getBoolean(neighborNodeId)) { queue.add(neighborNodeId); visited.set(neighborNodeId); @@ -232,23 +193,27 @@ return -1; } - private boolean isDestinationNode(SwhId swhId, String dstFmt) { - // No destination node, early exit - if (dstFmt == null) { + private boolean isDstNode(long nodeId, T dst) { + if (dst instanceof Long) { + long dstNodeId = (Long) dst; + return nodeId == dstNodeId; + } else if (dst instanceof Node.Type) { + Node.Type dstType = (Node.Type) dst; + return graph.getNodeType(nodeId) == dstType; + } else { return false; } + } - // SwhId as destination node - if (swhId.toString().equals(dstFmt)) { - return true; - } - - // Node.Type as destination node - try { - Node.Type dstType = Node.Type.fromStr(dstFmt); - return (swhId.getType().equals(dstType)); - } catch (IllegalArgumentException e) { - return false; + private ArrayList backtracking(long srcNodeId, long dstNodeId) { + ArrayList path = new ArrayList(); + long currentNodeId = dstNodeId; + while (currentNodeId != srcNodeId) { + path.add(currentNodeId); + currentNodeId = LongBigArrays.get(nodeParent, currentNodeId); } + path.add(srcNodeId); + Collections.reverse(path); + return path; } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java b/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java --- a/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java +++ b/api/server/src/main/java/org/softwareheritage/graph/backend/Setup.java @@ -67,9 +67,8 @@ FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(nodesStream, "UTF-8")); LineIterator swhIdIterator = new LineIterator(buffer); - try ( - Writer swhToNodeMap = new BufferedWriter(new FileWriter(graphPath + Graph.PID_TO_NODE)); - Writer nodeToSwhMap = new BufferedWriter(new FileWriter(graphPath + Graph.NODE_TO_PID))) { + try (Writer swhToNodeMap = new BufferedWriter(new FileWriter(graphPath + Graph.PID_TO_NODE)); + Writer nodeToSwhMap = new BufferedWriter(new FileWriter(graphPath + Graph.NODE_TO_PID))) { // nodeToSwhMap needs to write SWH id in order of node id, so use a temporary array Object[][] nodeToSwhId = ObjectBigArrays.newBigArray(nbIds); @@ -77,7 +76,8 @@ // type map. This is represented as a bitmap using minimum number of bits per Node.Type. final int log2NbTypes = (int) Math.ceil(Math.log(Node.Type.values().length) / Math.log(2)); final int nbBitsPerNodeType = log2NbTypes; - LongArrayBitVector nodeTypesBitVector = LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds); + LongArrayBitVector nodeTypesBitVector = + LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds); LongBigList nodeTypesMap = nodeTypesBitVector.asLongBigList(nbBitsPerNodeType); for (long iNode = 0; iNode < nbIds && swhIdIterator.hasNext(); iNode++) { diff --git a/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java b/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java --- a/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java +++ b/api/server/src/main/java/org/softwareheritage/graph/benchmark/LinuxLog.java @@ -2,9 +2,9 @@ import java.io.IOException; +import org.softwareheritage.graph.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; -import org.softwareheritage.graph.algo.Traversal; public class LinuxLog { public static void main(String[] args) throws IOException { @@ -18,8 +18,8 @@ System.out.println("Expecting " + expectedCount + " commits"); long startTime = System.nanoTime(); - Traversal traversal = new Traversal(graph, "forward", "rev:rev"); - long count = traversal.visitNodesEndpoint(commit).size(); + Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev"); + long count = endpoint.visitNodes(commit).size(); if (count != expectedCount) { throw new IllegalArgumentException("Counted " + count + " commits"); } diff --git a/api/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java b/api/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java --- a/api/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java @@ -6,9 +6,10 @@ import static org.junit.Assert.assertTrue; import org.softwareheritage.graph.AllowedEdges; +import org.softwareheritage.graph.GraphTest; import org.softwareheritage.graph.Node; -public class AllowedEdgesTest { +public class AllowedEdgesTest extends GraphTest { class EdgeType { Node.Type src; Node.Type dst; @@ -49,7 +50,8 @@ @Test public void dirToDirDirToCntEdges() { - AllowedEdges edges = new AllowedEdges("dir:dir,dir:cnt"); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, "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)); @@ -58,7 +60,8 @@ @Test public void relToRevRevToRevRevToDirEdges() { - AllowedEdges edges = new AllowedEdges("rel:rev,rev:rev,rev:dir"); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, "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)); @@ -68,7 +71,8 @@ @Test public void revToAllDirToDirEdges() { - AllowedEdges edges = new AllowedEdges("rev:*,dir:dir"); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, "rev:*,dir:dir"); ArrayList expected = new ArrayList<>(); for (Node.Type dst : Node.Type.values()) { expected.add(new EdgeType(Node.Type.REV, dst)); @@ -79,7 +83,8 @@ @Test public void allToCntEdges() { - AllowedEdges edges = new AllowedEdges("*:cnt"); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, "*:cnt"); ArrayList expected = new ArrayList<>(); for (Node.Type src : Node.Type.values()) { expected.add(new EdgeType(src, Node.Type.CNT)); @@ -89,8 +94,9 @@ @Test public void allEdges() { - AllowedEdges edges = new AllowedEdges("*:*"); - AllowedEdges edges2 = new AllowedEdges("*"); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, "*:*"); + AllowedEdges edges2 = new AllowedEdges(graph, "*"); ArrayList expected = new ArrayList<>(); for (Node.Type src : Node.Type.values()) { for (Node.Type dst : Node.Type.values()) { @@ -103,8 +109,9 @@ @Test public void noEdges() { - AllowedEdges edges = new AllowedEdges(""); - AllowedEdges edges2 = new AllowedEdges(null); + Graph graph = getGraph(); + AllowedEdges edges = new AllowedEdges(graph, ""); + AllowedEdges edges2 = new AllowedEdges(graph, null); ArrayList expected = new ArrayList<>(); assertEdgeRestriction(edges, expected); assertEdgeRestriction(edges2, expected); diff --git a/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java --- a/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/LeavesTest.java @@ -4,17 +4,17 @@ import org.junit.Test; +import org.softwareheritage.graph.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.GraphTest; import org.softwareheritage.graph.SwhId; -import org.softwareheritage.graph.algo.Traversal; public class LeavesTest extends GraphTest { @Test public void forwardFromSnp() { Graph graph = getGraph(); SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", "*"); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); ArrayList expectedLeaves = new ArrayList<>(); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); @@ -22,14 +22,14 @@ expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000005")); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); - assertEquals(expectedLeaves, traversal.leavesEndpoint(src)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, endpoint.leaves(src)); } @Test public void forwardFromRel() { Graph graph = getGraph(); SwhId src = new SwhId("swh:1:rel:0000000000000000000000000000000000000019"); - Traversal traversal = new Traversal(graph, "forward", "*"); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); ArrayList expectedLeaves = new ArrayList<>(); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000015")); @@ -40,43 +40,43 @@ expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000011")); - assertEquals(expectedLeaves, traversal.leavesEndpoint(src)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, endpoint.leaves(src)); } @Test public void backwardFromLeaf() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "backward", "*"); + Endpoint endpoint = new Endpoint(graph, "backward", "*"); SwhId src1 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015"); ArrayList expectedLeaves1 = new ArrayList<>(); expectedLeaves1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019")); - assertEquals(expectedLeaves1, traversal.leavesEndpoint(src1)); + GraphTest.assertEqualsAnyOrder(expectedLeaves1, endpoint.leaves(src1)); SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); ArrayList expectedLeaves2 = new ArrayList<>(); expectedLeaves2.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); expectedLeaves2.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000019")); - assertEquals(expectedLeaves2, traversal.leavesEndpoint(src2)); + GraphTest.assertEqualsAnyOrder(expectedLeaves2, endpoint.leaves(src2)); } @Test public void forwardRevToRevOnly() { Graph graph = getGraph(); SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018"); - Traversal traversal = new Traversal(graph, "forward", "rev:rev"); + Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev"); ArrayList expectedLeaves = new ArrayList<>(); expectedLeaves.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003")); - assertEquals(expectedLeaves, traversal.leavesEndpoint(src)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, endpoint.leaves(src)); } @Test public void forwardDirToAll() { Graph graph = getGraph(); SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); - Traversal traversal = new Traversal(graph, "forward", "dir:*"); + Endpoint endpoint = new Endpoint(graph, "forward", "dir:*"); ArrayList expectedLeaves = new ArrayList<>(); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000004")); @@ -84,18 +84,18 @@ expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); expectedLeaves.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); - assertEquals(expectedLeaves, traversal.leavesEndpoint(src)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, endpoint.leaves(src)); } @Test public void backwardCntToDirDirToDir() { Graph graph = getGraph(); SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000005"); - Traversal traversal = new Traversal(graph, "backward", "cnt:dir,dir:dir"); + Endpoint endpoint = new Endpoint(graph, "backward", "cnt:dir,dir:dir"); ArrayList expectedLeaves = new ArrayList<>(); expectedLeaves.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000012")); - assertEquals(expectedLeaves, traversal.leavesEndpoint(src)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, endpoint.leaves(src)); } } diff --git a/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java --- a/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/NeighborsTest.java @@ -4,10 +4,10 @@ import org.junit.Test; +import org.softwareheritage.graph.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.GraphTest; import org.softwareheritage.graph.SwhId; -import org.softwareheritage.graph.algo.Traversal; public class NeighborsTest extends GraphTest { @Test @@ -16,24 +16,24 @@ ArrayList expectedNodes = new ArrayList<>(); SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal1 = new Traversal(graph, "backward", "*"); - GraphTest.assertEqualsAnyOrder(expectedNodes, traversal1.neighborsEndpoint(src1)); + Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); + GraphTest.assertEqualsAnyOrder(expectedNodes, endpoint1.neighbors(src1)); SwhId src2 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Traversal traversal2 = new Traversal(graph, "forward", "*"); - GraphTest.assertEqualsAnyOrder(expectedNodes, traversal2.neighborsEndpoint(src2)); + Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); + GraphTest.assertEqualsAnyOrder(expectedNodes, endpoint2.neighbors(src2)); SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000015"); - Traversal traversal3 = new Traversal(graph, "forward", "*"); - GraphTest.assertEqualsAnyOrder(expectedNodes, traversal3.neighborsEndpoint(src3)); + Endpoint endpoint3 = new Endpoint(graph, "forward", "*"); + GraphTest.assertEqualsAnyOrder(expectedNodes, endpoint3.neighbors(src3)); SwhId src4 = new SwhId("swh:1:rel:0000000000000000000000000000000000000019"); - Traversal traversal4 = new Traversal(graph, "backward", "*"); - GraphTest.assertEqualsAnyOrder(expectedNodes, traversal4.neighborsEndpoint(src4)); + Endpoint endpoint4 = new Endpoint(graph, "backward", "*"); + GraphTest.assertEqualsAnyOrder(expectedNodes, endpoint4.neighbors(src4)); SwhId src5 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); - Traversal traversal5 = new Traversal(graph, "forward", "snp:*,rev:*,rel:*"); - GraphTest.assertEqualsAnyOrder(expectedNodes, traversal5.neighborsEndpoint(src5)); + Endpoint endpoint5 = new Endpoint(graph, "forward", "snp:*,rev:*,rel:*"); + GraphTest.assertEqualsAnyOrder(expectedNodes, endpoint5.neighbors(src5)); } @Test @@ -41,28 +41,28 @@ Graph graph = getGraph(); SwhId src1 = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); - Traversal traversal1 = new Traversal(graph, "forward", "*"); + Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); ArrayList expectedNodes1 = new ArrayList<>(); expectedNodes1.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002")); - GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1)); + GraphTest.assertEqualsAnyOrder(expectedNodes1, endpoint1.neighbors(src1)); SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000017"); - Traversal traversal2 = new Traversal(graph, "forward", "dir:cnt"); + Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt"); ArrayList expectedNodes2 = new ArrayList<>(); expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000014")); - GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2)); + GraphTest.assertEqualsAnyOrder(expectedNodes2, endpoint2.neighbors(src2)); SwhId src3 = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); - Traversal traversal3 = new Traversal(graph, "backward", "*"); + Endpoint endpoint3 = new Endpoint(graph, "backward", "*"); ArrayList expectedNodes3 = new ArrayList<>(); expectedNodes3.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); - GraphTest.assertEqualsAnyOrder(expectedNodes3, traversal3.neighborsEndpoint(src3)); + GraphTest.assertEqualsAnyOrder(expectedNodes3, endpoint3.neighbors(src3)); SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); - Traversal traversal4 = new Traversal(graph, "backward", "rev:rev"); + Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:rev"); ArrayList expectedNodes4 = new ArrayList<>(); expectedNodes4.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000013")); - GraphTest.assertEqualsAnyOrder(expectedNodes4, traversal4.neighborsEndpoint(src4)); + GraphTest.assertEqualsAnyOrder(expectedNodes4, endpoint4.neighbors(src4)); } @Test @@ -70,32 +70,32 @@ Graph graph = getGraph(); SwhId src1 = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal1 = new Traversal(graph, "forward", "*"); + Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); ArrayList expectedNodes1 = new ArrayList<>(); expectedNodes1.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); expectedNodes1.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000009")); - GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1)); + GraphTest.assertEqualsAnyOrder(expectedNodes1, endpoint1.neighbors(src1)); SwhId src2 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); - Traversal traversal2 = new Traversal(graph, "forward", "dir:cnt"); + Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt"); ArrayList expectedNodes2 = new ArrayList<>(); expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000001")); expectedNodes2.add(new SwhId("swh:1:cnt:0000000000000000000000000000000000000007")); - GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2)); + GraphTest.assertEqualsAnyOrder(expectedNodes2, endpoint2.neighbors(src2)); SwhId src3 = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"); - Traversal traversal3 = new Traversal(graph, "backward", "*"); + Endpoint endpoint3 = new Endpoint(graph, "backward", "*"); ArrayList expectedNodes3 = new ArrayList<>(); expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000008")); expectedNodes3.add(new SwhId("swh:1:dir:0000000000000000000000000000000000000002")); - GraphTest.assertEqualsAnyOrder(expectedNodes3, traversal3.neighborsEndpoint(src3)); + GraphTest.assertEqualsAnyOrder(expectedNodes3, endpoint3.neighbors(src3)); SwhId src4 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); - Traversal traversal4 = new Traversal(graph, "backward", "rev:snp,rev:rel"); + Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:snp,rev:rel"); ArrayList expectedNodes4 = new ArrayList<>(); expectedNodes4.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); expectedNodes4.add(new SwhId("swh:1:rel:0000000000000000000000000000000000000010")); - GraphTest.assertEqualsAnyOrder(expectedNodes4, traversal4.neighborsEndpoint(src4)); + GraphTest.assertEqualsAnyOrder(expectedNodes4, endpoint4.neighbors(src4)); } @Test @@ -103,19 +103,19 @@ Graph graph = getGraph(); SwhId src1 = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); - Traversal traversal1 = new Traversal(graph, "forward", "*"); + Endpoint endpoint1 = new Endpoint(graph, "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")); - GraphTest.assertEqualsAnyOrder(expectedNodes1, traversal1.neighborsEndpoint(src1)); + GraphTest.assertEqualsAnyOrder(expectedNodes1, endpoint1.neighbors(src1)); SwhId src2 = new SwhId("swh:1:rev:0000000000000000000000000000000000000009"); - Traversal traversal2 = new Traversal(graph, "backward", "*"); + Endpoint endpoint2 = new Endpoint(graph, "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")); - GraphTest.assertEqualsAnyOrder(expectedNodes2, traversal2.neighborsEndpoint(src2)); + GraphTest.assertEqualsAnyOrder(expectedNodes2, endpoint2.neighbors(src2)); } } 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,19 +1,20 @@ package org.softwareheritage.graph; import java.util.ArrayList; -import java.util.LinkedHashSet; +import java.util.Set; +import java.util.HashSet; import org.junit.Test; +import org.softwareheritage.graph.Endpoint; 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.Traversal; public class VisitTest extends GraphTest { - private void assertSameNodesFromPaths(ArrayList paths, LinkedHashSet nodes) { - LinkedHashSet expectedNodes = new LinkedHashSet(); + private void assertSameNodesFromPaths(ArrayList paths, ArrayList nodes) { + Set expectedNodes = new HashSet(); for (SwhPath path : paths) { for (SwhId node : path.getPath()) { expectedNodes.add(node); @@ -26,9 +27,9 @@ public void forwardFromRoot() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -121,9 +122,9 @@ public void forwardFromMiddle() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); - Traversal traversal = new Traversal(graph, "forward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -166,9 +167,9 @@ public void forwardFromLeaf() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Traversal traversal = new Traversal(graph, "forward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -184,9 +185,9 @@ public void backwardFromRoot() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "backward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "backward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -202,9 +203,9 @@ public void backwardFromMiddle() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000012"); - Traversal traversal = new Traversal(graph, "backward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "backward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -223,9 +224,9 @@ public void backwardFromLeaf() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000004"); - Traversal traversal = new Traversal(graph, "backward", "*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "backward", "*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -274,9 +275,9 @@ public void forwardSnpToRev() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", "snp:rev"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "snp:rev"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -293,9 +294,9 @@ public void forwardRelToRevRevToRev() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rel:0000000000000000000000000000000000000010"); - Traversal traversal = new Traversal(graph, "forward", "rel:rev,rev:rev"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "rel:rev,rev:rev"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -313,9 +314,9 @@ public void forwardRevToAllDirToAll() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000013"); - Traversal traversal = new Traversal(graph, "forward", "rev:*,dir:*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "rev:*,dir:*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -401,9 +402,9 @@ public void forwardSnpToAllRevToAll() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", "snp:*,rev:*"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "snp:*,rev:*"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -433,9 +434,9 @@ public void forwardNoEdges() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", ""); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", ""); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -451,9 +452,9 @@ public void backwardRevToRevRevToRel() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); - Traversal traversal = new Traversal(graph, "backward", "rev:rev,rev:rel"); - ArrayList paths = traversal.visitPathsEndpoint(swhId); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "backward", "rev:rev,rev:rel"); + ArrayList paths = endpoint.visitPaths(swhId); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( @@ -479,8 +480,8 @@ public void forwardFromRootNodesOnly() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); - Traversal traversal = new Traversal(graph, "forward", "*"); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedNodes = new ArrayList(); expectedNodes.add(new SwhId("swh:1:snp:0000000000000000000000000000000000000020")); @@ -502,8 +503,8 @@ public void backwardRevToAllNodesOnly() { Graph graph = getGraph(); SwhId swhId = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); - Traversal traversal = new Traversal(graph, "backward", "rev:*"); - ArrayList nodes = traversal.visitNodesEndpoint(swhId); + Endpoint endpoint = new Endpoint(graph, "backward", "rev:*"); + ArrayList nodes = endpoint.visitNodes(swhId); ArrayList expectedNodes = new ArrayList(); expectedNodes.add(new SwhId("swh:1:rev:0000000000000000000000000000000000000003")); diff --git a/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java --- a/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/WalkTest.java @@ -7,21 +7,21 @@ import org.junit.Test; import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder; +import org.softwareheritage.graph.Endpoint; 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.Traversal; public class WalkTest extends GraphTest { @Test public void forwardRootToLeaf() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "forward", "*"); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); SwhId src = new SwhId("swh:1:snp:0000000000000000000000000000000000000020"); String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", @@ -32,37 +32,37 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - // Most of DFS and BFS traversal outputs are the same because it is a small test graph - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + // Most of DFS and BFS endpoint outputs are the same because it is a small test graph + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } @Test public void forwardLeafToLeaf() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "forward", "*"); + Endpoint endpoint = new Endpoint(graph, "forward", "*"); SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000007"); String dstFmt = "cnt"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000007" ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } @Test public void forwardRevToRev() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "forward", "rev:rev"); + Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev"); SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000018"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000018", @@ -72,18 +72,18 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } @Test public void backwardRevToRev() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "backward", "rev:rev"); + Endpoint endpoint = new Endpoint(graph, "backward", "rev:rev"); SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000003"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000003", @@ -93,18 +93,18 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } @Test public void backwardCntToFirstSnp() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "backward", "*"); + Endpoint endpoint = new Endpoint(graph, "backward", "*"); SwhId src = new SwhId("swh:1:cnt:0000000000000000000000000000000000000001"); String dstFmt = "snp"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", @@ -115,7 +115,7 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); SwhPath bfsExpectedPath = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", @@ -129,11 +129,11 @@ @Test public void forwardRevToFirstCnt() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "forward", "rev:*,dir:*"); + Endpoint endpoint = new Endpoint(graph, "forward", "rev:*,dir:*"); SwhId src = new SwhId("swh:1:rev:0000000000000000000000000000000000000013"); String dstFmt = "cnt"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", @@ -142,18 +142,18 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } @Test public void backwardDirToFirstRel() { Graph graph = getGraph(); - Traversal traversal = new Traversal(graph, "backward", "dir:dir,dir:rev,rev:*"); + Endpoint endpoint = new Endpoint(graph, "backward", "dir:dir,dir:rev,rev:*"); SwhId src = new SwhId("swh:1:dir:0000000000000000000000000000000000000016"); String dstFmt = "rel"; - SwhPath dfsPath = traversal.walkEndpoint(src, dstFmt, "dfs"); + SwhPath dfsPath = endpoint.walk(src, dstFmt, "dfs"); SwhPath dfsExpectedPath = new SwhPath( "swh:1:dir:0000000000000000000000000000000000000016", @@ -163,7 +163,7 @@ ); Assert.assertEquals(dfsExpectedPath, dfsPath); - SwhPath bfsPath = traversal.walkEndpoint(src, dstFmt, "bfs"); + SwhPath bfsPath = endpoint.walk(src, dstFmt, "bfs"); Assert.assertEquals(dfsExpectedPath, bfsPath); } }