diff --git a/api/server/.clang-format b/api/server/.clang-format new file mode 100644 index 0000000..8985e96 --- /dev/null +++ b/api/server/.clang-format @@ -0,0 +1,4 @@ +--- +BasedOnStyle: Google +--- +Language: Java 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 5fe688e..23b2ca7 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/App.java +++ b/api/server/src/main/java/org/softwareheritage/graph/App.java @@ -1,38 +1,34 @@ package org.softwareheritage.graph; import java.io.FileNotFoundException; import java.io.IOException; import java.nio.file.Path; import java.nio.file.Paths; import io.javalin.Javalin; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.algo.Stats; -public class App -{ - public static void main(String[] args) throws IOException, Exception - { - Path path = Paths.get(args[0]); - Graph graph = new Graph(path.toString()); - Stats stats = new Stats(graph); +public class App { + public static void main(String[] args) throws IOException, Exception { + Path path = Paths.get(args[0]); + Graph graph = new Graph(path.toString()); + Stats stats = new Stats(graph); - Javalin app = Javalin.create().start(5010); + Javalin app = Javalin.create().start(5010); - app.get("/stats/", ctx -> { - try { - ctx.json(stats); - } catch (IllegalArgumentException e) { - ctx.status(404); - } catch (Exception e) { - ctx.status(400); - ctx.result(e.toString()); - } - }); + app.get("/stats/", ctx -> { + try { + ctx.json(stats); + } catch (IllegalArgumentException e) { + ctx.status(404); + } catch (Exception e) { + ctx.status(400); + ctx.result(e.toString()); + } + }); - app.error(404, ctx -> { - ctx.result("Not found"); - }); - } + 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 fdf2b47..49a9a11 100644 --- a/api/server/src/main/java/org/softwareheritage/graph/Graph.java +++ b/api/server/src/main/java/org/softwareheritage/graph/Graph.java @@ -1,110 +1,97 @@ package org.softwareheritage.graph; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Collection; import java.util.HashMap; import java.util.zip.GZIPInputStream; import it.unimi.dsi.big.webgraph.BVGraph; import it.unimi.dsi.big.webgraph.LazyLongIterator; 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.io.FastBufferedReader; import it.unimi.dsi.io.LineIterator; import it.unimi.dsi.lang.MutableString; -public class Graph -{ - BVGraph graph; - String path; - HashMap hashToNode; - HashMap nodeToHash; - - public Graph(String graphPath) throws Exception - { - this.graph = BVGraph.load(graphPath); - this.path = graphPath; - this.hashToNode = new HashMap(); - this.nodeToHash = new HashMap(); - setupNodesMapping(); +public class Graph { + BVGraph graph; + String path; + HashMap hashToNode; + HashMap nodeToHash; + + public Graph(String graphPath) throws Exception { + this.graph = BVGraph.load(graphPath); + this.path = graphPath; + this.hashToNode = new HashMap(); + this.nodeToHash = new HashMap(); + setupNodesMapping(); + } + + private void setupNodesMapping() throws IOException, ClassNotFoundException { + // First mapping: SWH hexhash (strings) <=> WebGraph MPH (longs) + HashMap mphToHash = new HashMap(); + @SuppressWarnings("unchecked") + Object2LongFunction mphMap = + (Object2LongFunction) BinIO.loadObject(path + ".mph"); + + InputStream nodeFile = new GZIPInputStream(new FileInputStream(path + ".nodes.csv.gz")); + Collection hashes = + new LineIterator(new FastBufferedReader(new InputStreamReader(nodeFile, "UTF-8"))) + .allLines(); + + for (MutableString h : hashes) { + String hash = new String(h.toString()); + long mph = mphMap.getLong(hash); + mphToHash.put(mph, hash); } - private void setupNodesMapping() throws IOException, ClassNotFoundException - { - // First mapping: SWH hexhash (strings) <=> WebGraph MPH (longs) - HashMap mphToHash = new HashMap(); - @SuppressWarnings("unchecked") - Object2LongFunction mphMap = - (Object2LongFunction) BinIO.loadObject(path + ".mph"); - - InputStream nodeFile = new FileInputStream(path + ".nodes.csv.gz"); - Collection hashes = - new LineIterator( - new FastBufferedReader( - new InputStreamReader( - new GZIPInputStream(nodeFile), "UTF-8"))).allLines(); - - for (MutableString h : hashes) - { - String hash = new String(h.toString()); - long mph = mphMap.getLong(hash); - mphToHash.put(mph, hash); - } - - // Second mapping: WebGraph MPH (longs) <=> BFS ordering (longs) - long n = mphMap.size(); - long[][] bfsMap = LongBigArrays.newBigArray(n); - long loaded = BinIO.loadLongs(path + ".order", bfsMap); - if (loaded != n) - throw new IllegalArgumentException("Graph contains " + n + " nodes, but read " + loaded); - - // Create final mapping: SWH hexhash (strings) <=> BFS ordering (longs) - for (long id = 0; id < n; id++) - { - String hash = mphToHash.get(id); - long node = LongBigArrays.get(bfsMap, id); - - hashToNode.put(hash, node); - nodeToHash.put(node, hash); - } + // Second mapping: WebGraph MPH (longs) <=> BFS ordering (longs) + long n = mphMap.size(); + long[][] bfsMap = LongBigArrays.newBigArray(n); + long loaded = BinIO.loadLongs(path + ".order", bfsMap); + if (loaded != n) { + throw new IllegalArgumentException("Graph contains " + n + " nodes, but read " + loaded); } - public String getPath() - { - return path; - } + // Create final mapping: SWH hexhash (strings) <=> BFS ordering (longs) + for (long id = 0; id < n; id++) { + String hash = mphToHash.get(id); + long node = LongBigArrays.get(bfsMap, id); - public long getNode(String hash) - { - return hashToNode.get(hash); + hashToNode.put(hash, node); + nodeToHash.put(node, hash); } + } - public String getHash(long node) - { - return nodeToHash.get(node); - } + public String getPath() { + return path; + } - public long getNbNodes() - { - return graph.numNodes(); - } + public long getNode(String hash) { + return hashToNode.get(hash); + } - public long getNbEdges() - { - return graph.numArcs(); - } + public String getHash(long node) { + return nodeToHash.get(node); + } - public LazyLongIterator successors(long node) - { - return graph.successors(node); - } + public long getNbNodes() { + return graph.numNodes(); + } - public long outdegree(long node) - { - return graph.outdegree(node); - } + public long getNbEdges() { + return graph.numArcs(); + } + + public LazyLongIterator successors(long node) { + return graph.successors(node); + } + + public long outdegree(long node) { + return graph.outdegree(node); + } } 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 59b0061..10d296c 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,55 +1,54 @@ package org.softwareheritage.graph.algo; 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; -public class Stats -{ - public long nbNodes; - public long nbEdges; - public double compressionRatio; - public double bitsPerNode; - public double bitsPerEdge; - public double avgLocality; - public long minIndegree; - public long maxIndegree; - public double avgIndegree; - public long minOutdegree; - public long maxOutdegree; - public double avgOutdegree; +public class Stats { + public long nbNodes; + public long nbEdges; + public double compressionRatio; + public double bitsPerNode; + public double bitsPerEdge; + public double avgLocality; + public long minIndegree; + public long maxIndegree; + public double avgIndegree; + public long minOutdegree; + public long maxOutdegree; + public double avgOutdegree; - public Stats(Graph graph) throws IOException - { - HashMap statsMap = new HashMap<>(); + public Stats(Graph graph) throws IOException { + HashMap statsMap = new HashMap<>(); - // Parse statistics from generated files - Path dotProperties = Paths.get(graph.getPath() + ".properties"); - Path dotStats = Paths.get(graph.getPath() + ".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]); - } - - this.nbNodes = Long.parseLong(statsMap.get("nodes")); - this.nbEdges = Long.parseLong(statsMap.get("arcs")); - this.compressionRatio = Double.parseDouble(statsMap.get("compratio")); - this.bitsPerNode = Double.parseDouble(statsMap.get("bitspernode")); - this.bitsPerEdge = Double.parseDouble(statsMap.get("bitsperlink")); - this.avgLocality = Double.parseDouble(statsMap.get("avglocality")); - this.minIndegree = Long.parseLong(statsMap.get("minindegree")); - this.maxIndegree = Long.parseLong(statsMap.get("maxindegree")); - this.avgIndegree = Double.parseDouble(statsMap.get("avgindegree")); - this.minOutdegree = Long.parseLong(statsMap.get("minoutdegree")); - this.maxOutdegree = Long.parseLong(statsMap.get("maxoutdegree")); - this.avgOutdegree = Double.parseDouble(statsMap.get("avgoutdegree")); + // Parse statistics from generated files + Path dotProperties = Paths.get(graph.getPath() + ".properties"); + Path dotStats = Paths.get(graph.getPath() + ".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]); + } } + + this.nbNodes = Long.parseLong(statsMap.get("nodes")); + this.nbEdges = Long.parseLong(statsMap.get("arcs")); + this.compressionRatio = Double.parseDouble(statsMap.get("compratio")); + this.bitsPerNode = Double.parseDouble(statsMap.get("bitspernode")); + this.bitsPerEdge = Double.parseDouble(statsMap.get("bitsperlink")); + this.avgLocality = Double.parseDouble(statsMap.get("avglocality")); + this.minIndegree = Long.parseLong(statsMap.get("minindegree")); + this.maxIndegree = Long.parseLong(statsMap.get("maxindegree")); + this.avgIndegree = Double.parseDouble(statsMap.get("avgindegree")); + this.minOutdegree = Long.parseLong(statsMap.get("minoutdegree")); + this.maxOutdegree = Long.parseLong(statsMap.get("maxoutdegree")); + this.avgOutdegree = Double.parseDouble(statsMap.get("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 fe37002..eb39642 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,73 +1,68 @@ 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; -public class Visit -{ - public class Path extends ArrayList {} +public class Visit { + public class Path extends ArrayList {} - Graph graphFwd; - Graph graphBwd; + Graph graphFwd; + Graph graphBwd; - private Graph graph; - private LongArrayBitVector visited; - private ArrayList extraEdges; - private Stack currentPath; - private ArrayList paths; + private Graph graph; + private LongArrayBitVector visited; + private ArrayList extraEdges; + private Stack currentPath; + private ArrayList paths; - public Visit(Graph graph, Graph graphSym) - { - this.graphFwd = graph; - this.graphBwd = graphSym; - } - - public ArrayList visit(String start, ArrayList extraEdges, boolean backward) - { - this.graph = (backward) ? this.graphBwd : this.graphFwd; - this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); - this.extraEdges = extraEdges; - this.paths = new ArrayList(); - this.currentPath = new Stack(); - - _recursiveVisit(graph.getNode(start)); + public Visit(Graph graph, Graph graphSym) { + this.graphFwd = graph; + this.graphBwd = graphSym; + } - return paths; - } + public ArrayList visit(String start, ArrayList extraEdges, boolean backward) { + this.graph = (backward) ? this.graphBwd : this.graphFwd; + this.visited = LongArrayBitVector.ofLength(graph.getNbNodes()); + this.extraEdges = extraEdges; + this.paths = new ArrayList(); + this.currentPath = new Stack(); - private void _recursiveVisit(long current) - { - visited.set(current); - currentPath.push(current); + recursiveVisit(graph.getNode(start)); - long degree = graph.outdegree(current); - if (degree == 0) - { - Path path = new Path(); - for (long node : currentPath) - path.add(graph.getHash(node)); - paths.add(path); - } + return paths; + } - LazyLongIterator successors = graph.successors(current); - while (degree-- > 0) - { - long next = successors.nextLong(); - if (_traversalAllowed(current, next) && !visited.getBoolean(next)) - _recursiveVisit(next); - } + private void recursiveVisit(long current) { + visited.set(current); + currentPath.push(current); - currentPath.pop(); + long degree = graph.outdegree(current); + if (degree == 0) { + Path path = new Path(); + for (long node : currentPath) { + path.add(graph.getHash(node)); + } + paths.add(path); } - private boolean _traversalAllowed(long current, long next) - { - // TODO - return true; + LazyLongIterator successors = graph.successors(current); + while (degree-- > 0) { + long next = successors.nextLong(); + if (traversalAllowed(current, next) && !visited.getBoolean(next)) { + recursiveVisit(next); + } } + + currentPath.pop(); + } + + private boolean traversalAllowed(long current, long next) { + // TODO + return true; + } } diff --git a/api/server/src/test/java/org/softwareheritage/graph/GraphTest.java b/api/server/src/test/java/org/softwareheritage/graph/GraphTest.java index e56f8ae..6322153 100644 --- a/api/server/src/test/java/org/softwareheritage/graph/GraphTest.java +++ b/api/server/src/test/java/org/softwareheritage/graph/GraphTest.java @@ -1,22 +1,19 @@ package org.softwareheritage.graph; import org.junit.BeforeClass; import org.softwareheritage.graph.Graph; -public class GraphTest -{ - static Graph graph; +public class GraphTest { + static Graph graph; - @BeforeClass - public static void setUp() - { - String graphPath = System.getProperty("graphPath"); - graph = new Graph(graphPath); - } + @BeforeClass + public static void setUp() { + String graphPath = System.getProperty("graphPath"); + graph = new Graph(graphPath); + } - public Graph getGraph() - { - return graph; - } + public Graph getGraph() { + return graph; + } }