diff --git a/api/server/src/main/java/org/softwareheritage/graph/App.java b/api/server/src/main/java/org/softwareheritage/graph/App.java index 344a7c9..f54cc39 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/App.java +++ b/api/server/src/main/java/org/softwareheritage/graph/App.java @@ -1,62 +1,62 @@ package org.softwareheritage.graph; import java.io.IOException; import java.util.Optional; import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.PropertyNamingStrategy; import io.javalin.Javalin; import io.javalin.json.JavalinJackson; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.algo.Stats; import org.softwareheritage.graph.algo.Visit; public class App { public static void main(String[] args) throws IOException { String path = args[0]; Graph graph = new Graph(path); Stats stats = new Stats(path); // Clean up on exit Runtime.getRuntime().addShutdownHook(new Thread() { public void run() { try { graph.cleanUp(); } catch (IOException e) { System.out.println("Could not clean up graph on exit: " + e); } } }); - // Configure Jackson JSON properties + // Configure Jackson JSON to use snake case naming style ObjectMapper objectMapper = JavalinJackson.getObjectMapper(); objectMapper.setPropertyNamingStrategy(PropertyNamingStrategy.SNAKE_CASE); JavalinJackson.configure(objectMapper); Javalin app = Javalin.create().start(5010); app.get("/stats", ctx -> { ctx.json(stats); }); app.get("/visit/:swh_id", ctx -> { try { - SwhId start = new SwhId(ctx.pathParam("swh_id")); + SwhId swhId = new SwhId(ctx.pathParam("swh_id")); // By default, traversal is a forward DFS using all edges String algorithm = Optional.ofNullable(ctx.queryParam("traversal")).orElse("dfs"); String direction = Optional.ofNullable(ctx.queryParam("direction")).orElse("forward"); String edges = Optional.ofNullable(ctx.queryParam("edges")).orElse("all"); - ctx.json(new Visit(graph, start, edges, algorithm, direction)); + ctx.json(new Visit(graph, swhId, edges, algorithm, direction)); } catch (IllegalArgumentException e) { ctx.status(400); ctx.result(e.getMessage()); } }); app.error(404, ctx -> { ctx.result("Not found"); }); } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/Graph.java b/api/server/src/main/java/org/softwareheritage/graph/Graph.java index f0eeece..ba34c94 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/Graph.java +++ b/api/server/src/main/java/org/softwareheritage/graph/Graph.java @@ -1,79 +1,71 @@ package org.softwareheritage.graph; import java.io.IOException; import it.unimi.dsi.big.webgraph.BVGraph; import it.unimi.dsi.big.webgraph.LazyLongIterator; import org.softwareheritage.graph.NodeIdMap; import org.softwareheritage.graph.SwhId; public class Graph { BVGraph graph; BVGraph graphTransposed; String path; NodeIdMap nodeIdMap; - public Graph(String graphPath) throws IOException { - this.graph = BVGraph.load(graphPath); - this.graphTransposed = BVGraph.load(graphPath + "-transposed"); - this.path = graphPath; - this.nodeIdMap = new NodeIdMap(graphPath, getNbNodes()); + public Graph(String path) throws IOException { + this.graph = BVGraph.load(path); + this.graphTransposed = BVGraph.load(path + "-transposed"); + this.path = path; + this.nodeIdMap = new NodeIdMap(path, getNbNodes()); } public void cleanUp() throws IOException { nodeIdMap.close(); } public String getPath() { return path; } - public long getNode(SwhId swhId) { - return nodeIdMap.getNode(swhId); + public long getNodeId(SwhId swhId) { + return nodeIdMap.getNodeId(swhId); } - public SwhId getSwhId(long node) { - return nodeIdMap.getSwhId(node); + public SwhId getSwhId(long nodeId) { + return nodeIdMap.getSwhId(nodeId); } public long getNbNodes() { return graph.numNodes(); } public long getNbEdges() { return graph.numArcs(); } - public LazyLongIterator successors(long node) { - return graph.successors(node); + public LazyLongIterator successors(long nodeId) { + return graph.successors(nodeId); } - public long outdegree(long node) { - return graph.outdegree(node); + public long outdegree(long nodeId) { + return graph.outdegree(nodeId); } - public LazyLongIterator predecessors(long node) { - return graphTransposed.successors(node); + public LazyLongIterator predecessors(long nodeId) { + return graphTransposed.successors(nodeId); } - public long indegree(long node) { - return graphTransposed.outdegree(node); + public long indegree(long nodeId) { + return graphTransposed.outdegree(nodeId); } - public long degree(long node, boolean isTransposed) { - if (isTransposed) { - return indegree(node); - } else { - return outdegree(node); - } + public long degree(long nodeId, boolean isTransposed) { + return (isTransposed) ? indegree(nodeId) : outdegree(nodeId); } - public LazyLongIterator neighbors(long node, boolean isTransposed) { - if (isTransposed) { - return predecessors(node); - } else { - return successors(node); - } + public LazyLongIterator neighbors(long nodeId, boolean isTransposed) { + return (isTransposed) ? predecessors(nodeId) : successors(nodeId); } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/NodeIdMap.java b/api/server/src/main/java/org/softwareheritage/graph/NodeIdMap.java index 6291290..b347513 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/NodeIdMap.java +++ b/api/server/src/main/java/org/softwareheritage/graph/NodeIdMap.java @@ -1,142 +1,142 @@ package org.softwareheritage.graph; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.zip.GZIPInputStream; import it.unimi.dsi.fastutil.io.BinIO; import it.unimi.dsi.fastutil.longs.LongBigArrays; import it.unimi.dsi.fastutil.objects.Object2LongFunction; import it.unimi.dsi.fastutil.objects.ObjectBigArrays; import it.unimi.dsi.io.FastBufferedReader; import it.unimi.dsi.io.LineIterator; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.utils.MMapInputFile; import org.softwareheritage.graph.utils.MMapOutputFile; // TODO: // - Add option to dump or not the mapping public class NodeIdMap { private static final int SWH_ID_SIZE = 50; private static final int NODE_ID_SIZE = 20; // +1 are for spaces and end of lines private static final int SWH_TO_NODE_LINE_LENGTH = SWH_ID_SIZE + 1 + NODE_ID_SIZE + 1; private static final int NODE_TO_SWH_LINE_LENGTH = SWH_ID_SIZE + 1; String graphPath; long nbIds; MMapInputFile swhToNodeMap; MMapInputFile nodeToSwhMap; public NodeIdMap(String graphPath, long nbNodes) throws IOException { this.graphPath = graphPath; this.nbIds = nbNodes; dump(); this.swhToNodeMap = new MMapInputFile(graphPath + ".swhToNodeMap.csv", SWH_TO_NODE_LINE_LENGTH); this.nodeToSwhMap = new MMapInputFile(graphPath + ".nodeToSwhMap.csv", NODE_TO_SWH_LINE_LENGTH); } // SWH id (string) -> WebGraph node id (long) // Each line in .swhToNode.csv is formatted as: swhId nodeId // The file is sorted by swhId, hence we can binary search on swhId to get corresponding nodeId - public long getNode(SwhId swhId) { + public long getNodeId(SwhId swhId) { long start = 0; long end = nbIds - 1; while (start <= end) { long lineNumber = (start + end) / 2L; String[] parts = swhToNodeMap.readAtLine(lineNumber).split(" "); if (parts.length != 2) { break; } String currentSwhId = parts[0]; long currentNodeId = Long.parseLong(parts[1]); int cmp = currentSwhId.compareTo(swhId.toString()); if (cmp == 0) { return currentNodeId; } else if (cmp < 0) { start = lineNumber + 1; } else { end = lineNumber - 1; } } throw new IllegalArgumentException("Unknown SWH id: " + swhId); } // WebGraph node id (long) -> SWH id (string) // Each line in .nodeToSwh.csv is formatted as: swhId // The file is ordered by nodeId, meaning node0's swhId is at line 0, hence we can read the // nodeId-th line to get corresponding swhId - public SwhId getSwhId(long node) { - if (node < 0 || node >= nbIds) { - throw new IllegalArgumentException("Node id " + node + " should be between 0 and " + nbIds); + public SwhId getSwhId(long nodeId) { + if (nodeId < 0 || nodeId >= nbIds) { + throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nbIds); } - String swhId = nodeToSwhMap.readAtLine(node); + String swhId = nodeToSwhMap.readAtLine(nodeId); return new SwhId(swhId); } @SuppressWarnings("unchecked") void dump() throws IOException { // First internal mapping: SWH id (string) -> WebGraph MPH (long) Object2LongFunction mphMap = null; try { mphMap = (Object2LongFunction) BinIO.loadObject(graphPath + ".mph"); } catch (ClassNotFoundException e) { throw new IllegalArgumentException("The .mph file contains unknown class object: " + e); } // Second internal mapping: WebGraph MPH (long) -> BFS ordering (long) long[][] bfsMap = LongBigArrays.newBigArray(nbIds); long loaded = BinIO.loadLongs(graphPath + ".order", bfsMap); if (loaded != nbIds) { throw new IllegalArgumentException("Graph contains " + nbIds + " nodes, but read " + loaded); } // Dump complete mapping for all nodes: SWH id (string) <=> WebGraph node id (long) MMapOutputFile swhToNodeMapOut = new MMapOutputFile(graphPath + ".swhToNodeMap.csv", SWH_TO_NODE_LINE_LENGTH, nbIds); MMapOutputFile nodeToSwhMapOut = new MMapOutputFile(graphPath + ".nodeToSwhMap.csv", NODE_TO_SWH_LINE_LENGTH, nbIds); InputStream nodeFile = new GZIPInputStream(new FileInputStream(graphPath + ".nodes.csv.gz")); FastBufferedReader fileBuffer = new FastBufferedReader(new InputStreamReader(nodeFile, "UTF-8")); LineIterator lineIterator = new LineIterator(fileBuffer); for (long iNode = 0; iNode < nbIds && lineIterator.hasNext(); iNode++) { String swhId = lineIterator.next().toString(); long mphId = mphMap.getLong(swhId); long nodeId = LongBigArrays.get(bfsMap, mphId); { String paddedNodeId = String.format("%0" + NODE_ID_SIZE + "d", nodeId); String line = swhId + " " + paddedNodeId + "\n"; long lineIndex = iNode; swhToNodeMapOut.writeAtLine(line, lineIndex); } { String line = swhId + "\n"; long lineIndex = nodeId; nodeToSwhMapOut.writeAtLine(line, lineIndex); } } swhToNodeMapOut.close(); nodeToSwhMapOut.close(); } public void close() throws IOException { swhToNodeMap.close(); nodeToSwhMap.close(); } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java index bcdc23a..b413291 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/SwhId.java +++ b/api/server/src/main/java/org/softwareheritage/graph/SwhId.java @@ -1,49 +1,59 @@ package org.softwareheritage.graph; import com.fasterxml.jackson.annotation.JsonValue; public class SwhId { + public static final int HASH_LENGTH = 40; + String swhId; String type; String hash; + // SWH ID format: 'swh:1:type:hash' + // https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html public SwhId(String swhId) { this.swhId = swhId; + String[] parts = swhId.split(":"); - if (parts.length != 4) { - throw new IllegalArgumentException("Incorrect SWH ID format: " + swhId); + if (parts.length != 4 || !parts[0].equals("swh") || !parts[1].equals("1")) { + throw new IllegalArgumentException("Expected SWH ID format to be 'swh:1:type:hash', got: " + swhId); } - // SWH ID format: 'swh:1:type:hash' - // https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html this.type = parts[2]; + if (!type.matches("cnt|dir|rel|rev|snp")) { + throw new IllegalArgumentException("Unknown SWH ID type in: " + swhId); + } + this.hash = parts[3]; + if (!hash.matches("[0-9a-f]{" + HASH_LENGTH + "}")) { + throw new IllegalArgumentException("Unknown SWH ID hash in: " + swhId); + } } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; - if (! (otherObj instanceof SwhId)) return false; + if (!(otherObj instanceof SwhId)) return false; SwhId other = (SwhId) otherObj; return swhId.equals(other.getSwhId()); } @Override public String toString() { return swhId; } @JsonValue public String getSwhId() { return swhId; } public String getType() { return type; } public String getHash() { return hash; } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java b/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java index 4b529b9..be9c80b 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java +++ b/api/server/src/main/java/org/softwareheritage/graph/SwhPath.java @@ -1,76 +1,76 @@ package org.softwareheritage.graph; import java.util.ArrayList; import com.fasterxml.jackson.annotation.JsonValue; import org.softwareheritage.graph.SwhId; public class SwhPath { ArrayList path; public SwhPath() { this.path = new ArrayList(); } public SwhPath(String ...swhIds) { this(); for (String swhId : swhIds) { add(new SwhId(swhId)); } } public SwhPath(SwhId ...swhIds) { this(); for (SwhId swhId : swhIds) { add(swhId); } } @JsonValue public ArrayList getPath() { return path; } public void add(SwhId swhId) { path.add(swhId); } public SwhId get(int index) { return path.get(index); } public int size() { return path.size(); } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; - if (! (otherObj instanceof SwhPath)) return false; + if (!(otherObj instanceof SwhPath)) return false; SwhPath other = (SwhPath) otherObj; if (size() != other.size()) { return false; } for (int i = 0; i < size(); i++) { - SwhId thisId = get(i); - SwhId otherId = other.get(i); - if (! thisId.equals(otherId)) { + SwhId thisSwhId = get(i); + SwhId otherSwhId = other.get(i); + if (!thisSwhId.equals(otherSwhId)) { return false; } } return true; } @Override public String toString() { String str = new String(); for (SwhId swhId : path) { str += swhId + "/"; } return str; } } diff --git a/api/server/src/main/java/org/softwareheritage/graph/algo/Stats.java b/api/server/src/main/java/org/softwareheritage/graph/algo/Stats.java index ad2a402..e5304f7 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/algo/Stats.java +++ b/api/server/src/main/java/org/softwareheritage/graph/algo/Stats.java @@ -1,74 +1,54 @@ package org.softwareheritage.graph.algo; +import java.io.FileInputStream; import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; -import java.nio.file.Paths; -import java.util.HashMap; -import java.util.List; - -import org.softwareheritage.graph.Graph; - -/* - TODO: - - merge the two stats files (.properties and .stats) into one -*/ +import java.util.Properties; public class Stats { public class Counts { public long nodes; public long edges; } public class Ratios { public double compression; public double bitsPerNode; public double bitsPerEdge; public double avgLocality; } public class Degree { public long min; public long max; public double avg; } public Counts counts; public Ratios ratios; public Degree indegree; public Degree outdegree; public Stats(String graphPath) throws IOException { - HashMap statsMap = new HashMap<>(); - - // Parse statistics from generated files - Path dotProperties = Paths.get(graphPath + ".properties"); - Path dotStats = Paths.get(graphPath + ".stats"); - List lines = Files.readAllLines(dotProperties); - lines.addAll(Files.readAllLines(dotStats)); - for (String line : lines) { - String[] parts = line.split("="); - if (parts.length == 2) { - statsMap.put(parts[0], parts[1]); - } - } + Properties properties = new Properties(); + properties.load(new FileInputStream(graphPath + ".properties")); + properties.load(new FileInputStream(graphPath + ".stats")); this.counts = new Counts(); this.ratios = new Ratios(); this.indegree = new Degree(); this.outdegree = new Degree(); - this.counts.nodes = Long.parseLong(statsMap.get("nodes")); - this.counts.edges = Long.parseLong(statsMap.get("arcs")); - this.ratios.compression = Double.parseDouble(statsMap.get("compratio")); - this.ratios.bitsPerNode = Double.parseDouble(statsMap.get("bitspernode")); - this.ratios.bitsPerEdge = Double.parseDouble(statsMap.get("bitsperlink")); - this.ratios.avgLocality = Double.parseDouble(statsMap.get("avglocality")); - this.indegree.min = Long.parseLong(statsMap.get("minindegree")); - this.indegree.max = Long.parseLong(statsMap.get("maxindegree")); - this.indegree.avg = Double.parseDouble(statsMap.get("avgindegree")); - this.outdegree.min = Long.parseLong(statsMap.get("minoutdegree")); - this.outdegree.max = Long.parseLong(statsMap.get("maxoutdegree")); - this.outdegree.avg = Double.parseDouble(statsMap.get("avgoutdegree")); + this.counts.nodes = Long.parseLong(properties.getProperty("nodes")); + this.counts.edges = Long.parseLong(properties.getProperty("arcs")); + this.ratios.compression = Double.parseDouble(properties.getProperty("compratio")); + this.ratios.bitsPerNode = Double.parseDouble(properties.getProperty("bitspernode")); + this.ratios.bitsPerEdge = Double.parseDouble(properties.getProperty("bitsperlink")); + this.ratios.avgLocality = Double.parseDouble(properties.getProperty("avglocality")); + this.indegree.min = Long.parseLong(properties.getProperty("minindegree")); + this.indegree.max = Long.parseLong(properties.getProperty("maxindegree")); + this.indegree.avg = Double.parseDouble(properties.getProperty("avgindegree")); + this.outdegree.min = Long.parseLong(properties.getProperty("minoutdegree")); + this.outdegree.max = Long.parseLong(properties.getProperty("maxoutdegree")); + this.outdegree.avg = Double.parseDouble(properties.getProperty("avgoutdegree")); } } 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 index 657bb90..993bf68 100644 --- 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,77 +1,75 @@ package org.softwareheritage.graph.algo; import java.util.ArrayList; import java.util.Stack; import it.unimi.dsi.big.webgraph.LazyLongIterator; import it.unimi.dsi.bits.LongArrayBitVector; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhId; import org.softwareheritage.graph.SwhPath; public class Visit { Graph graph; boolean isTransposed; String allowedEdges; Stack currentPath; ArrayList paths; LongArrayBitVector visited; - public Visit(Graph graph, SwhId start, String allowedEdges, String algorithm, String direction) { + public Visit(Graph graph, SwhId swhId, String allowedEdges, String algorithm, String direction) { if (!algorithm.matches("dfs|bfs")) { - throw new IllegalArgumentException( - "Unknown traversal algorithm: " + algorithm + " (should be 'dfs' or 'bfs')"); + throw new IllegalArgumentException("Unknown traversal algorithm: " + algorithm); } if (!direction.matches("forward|backward")) { - throw new IllegalArgumentException( - "Unknown direction: " + direction + " (should be 'forward' or 'backward')"); + throw new IllegalArgumentException("Unknown traversal direction: " + direction); } this.graph = graph; this.isTransposed = (direction.equals("backward")); this.allowedEdges = allowedEdges; this.paths = new ArrayList(); this.currentPath = new Stack(); this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); if (algorithm.equals("dfs")) { - dfs(graph.getNode(start)); + dfs(graph.getNodeId(swhId)); } } // Allow Jackson JSON to only serialize the 'paths' field public ArrayList getPaths() { return paths; } - private void dfs(long currentNode) { - visited.set(currentNode); - currentPath.push(currentNode); + private void dfs(long currentNodeId) { + visited.set(currentNodeId); + currentPath.push(currentNodeId); - long degree = graph.degree(currentNode, isTransposed); - LazyLongIterator neighbors = graph.neighbors(currentNode, isTransposed); + long degree = graph.degree(currentNodeId, isTransposed); + LazyLongIterator neighbors = graph.neighbors(currentNodeId, isTransposed); if (degree == 0) { SwhPath path = new SwhPath(); - for (long node : currentPath) { - path.add(graph.getSwhId(node)); + for (long nodeId : currentPath) { + path.add(graph.getSwhId(nodeId)); } paths.add(path); } while (degree-- > 0) { - long nextNode = neighbors.nextLong(); - if (isEdgeAllowed(currentNode, nextNode) && !visited.getBoolean(nextNode)) { - dfs(nextNode); + long nextNodeId = neighbors.nextLong(); + if (isEdgeAllowed(currentNodeId, nextNodeId) && !visited.getBoolean(nextNodeId)) { + dfs(nextNodeId); } } currentPath.pop(); } - private boolean isEdgeAllowed(long currentNode, long nextNode) { + private boolean isEdgeAllowed(long currentNodeId, long nextNodeId) { // TODO return true; } } diff --git a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java index ad1f5a6..3d97588 100644 --- a/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/VisitTest.java @@ -1,159 +1,159 @@ package org.softwareheritage.graph; import java.util.ArrayList; 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.Visit; public class VisitTest extends GraphTest { - void assertEqualPaths(ArrayList expecteds, ArrayList actuals) { + void assertEqualSwhPaths(ArrayList expecteds, ArrayList actuals) { Assert.assertThat(expecteds, containsInAnyOrder(actuals.toArray())); } @Test public void dfsForwardFromRoot() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:dir:0000000000000000000000000000000000000001"); - Visit visit = new Visit(graph, start, "all", "dfs", "forward"); + SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000001"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000009" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001", "swh:1:cnt:0000000000000000000000000000000000000010" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000005", "swh:1:cnt:0000000000000000000000000000000000000006" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000003", "swh:1:cnt:0000000000000000000000000000000000000004" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } @Test public void dfsForwardFromMiddle() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:dir:0000000000000000000000000000000000000002"); - Visit visit = new Visit(graph, start, "all", "dfs", "forward"); + SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000002"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000005", "swh:1:cnt:0000000000000000000000000000000000000006" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000003", "swh:1:cnt:0000000000000000000000000000000000000004" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } @Test public void dfsForwardFromLeaf() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:cnt:0000000000000000000000000000000000000006"); - Visit visit = new Visit(graph, start, "all", "dfs", "forward"); + SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000006"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "forward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000006" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } @Test public void dfsBackwardFromRoot() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:dir:0000000000000000000000000000000000000001"); - Visit visit = new Visit(graph, start, "all", "dfs", "backward"); + SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000001"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000001" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } @Test public void dfsBackwardFromMiddle() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); - Visit visit = new Visit(graph, start, "all", "dfs", "backward"); + SwhId swhId = new SwhId("swh:1:dir:0000000000000000000000000000000000000008"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000001" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } @Test public void dfsBackwardFromLeaf() { Graph graph = getGraph(); - SwhId start = new SwhId("swh:1:cnt:0000000000000000000000000000000000000006"); - Visit visit = new Visit(graph, start, "all", "dfs", "backward"); + SwhId swhId = new SwhId("swh:1:cnt:0000000000000000000000000000000000000006"); + Visit visit = new Visit(graph, swhId, "all", "dfs", "backward"); ArrayList paths = visit.getPaths(); ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000006", "swh:1:dir:0000000000000000000000000000000000000005", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:dir:0000000000000000000000000000000000000001" )); - assertEqualPaths(expectedPaths, paths); + assertEqualSwhPaths(expectedPaths, paths); } }