Page MenuHomeSoftware Heritage
Files F9696374

D1831.id.diff
No OneTemporary
Actions

D1831.id.diff
View Options

diff --git a/java/server/src/main/java/org/softwareheritage/graph/Graph.java b/java/server/src/main/java/org/softwareheritage/graph/Graph.java
--- a/java/server/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/Graph.java
@@ -3,6 +3,7 @@
import java.io.IOException;
import it.unimi.dsi.big.webgraph.BVGraph;
+import it.unimi.dsi.big.webgraph.LazyLongIterator;
import org.softwareheritage.graph.Node;
import org.softwareheritage.graph.SwhId;
@@ -140,6 +141,17 @@
}
/**
+ * Returns lazy iterator of successors of a node.
+ *
+ * @param nodeId node specified as a long id
+ * @return lazy iterator of successors of the node, specified as a <a
+ * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+ */
+ public LazyLongIterator lazySuccessors(long nodeId) {
+ return graph.successors(nodeId);
+ }
+
+ /**
* Returns the outdegree of a node.
*
* @param nodeId node specified as a long id
@@ -153,7 +165,7 @@
* Returns list of predecessors of a node.
*
* @param nodeId node specified as a long id
- * @return list of successors of the node, specified as a <a
+ * @return list of predecessors of the node, specified as a <a
* href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays
*/
public long[][] predecessors(long nodeId) {
@@ -161,6 +173,17 @@
}
/**
+ * Returns lazy iterator of predecessors of a node.
+ *
+ * @param nodeId node specified as a long id
+ * @return lazy iterator of predecessors of the node, specified as a <a
+ * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+ */
+ public LazyLongIterator lazyPredecessors(long nodeId) {
+ return graphTransposed.successors(nodeId);
+ }
+
+ /**
* Returns the indegree of a node.
*
* @param nodeId node specified as a long id
@@ -182,14 +205,26 @@
}
/**
- * Returns the neighbors of a node, depending on graph orientation.
+ * Returns the neighbors of a node (as a list), depending on graph orientation.
*
* @param nodeId node specified as a long id
* @param useTransposed boolean value to use transposed graph
- * @return list of successors of the node, specified as a <a
+ * @return list of neighbors of the node, specified as a <a
* href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays
*/
public long[][] neighbors(long nodeId, boolean useTransposed) {
return (useTransposed) ? predecessors(nodeId) : successors(nodeId);
}
+
+ /**
+ * Returns the neighbors of a node (as a lazy iterator), depending on graph orientation.
+ *
+ * @param nodeId node specified as a long id
+ * @param useTransposed boolean value to use transposed graph
+ * @return lazy iterator of neighbors of the node, specified as a <a
+ * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+ */
+ public LazyLongIterator lazyNeighbors(long nodeId, boolean useTransposed) {
+ return (useTransposed) ? lazyPredecessors(nodeId) : lazySuccessors(nodeId);
+ }
}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java b/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
@@ -0,0 +1,49 @@
+package org.softwareheritage.graph.benchmark;
+
+import java.io.IOException;
+import java.util.ArrayList;
+
+import it.unimi.dsi.big.webgraph.LazyLongIterator;
+
+import org.softwareheritage.graph.Graph;
+import org.softwareheritage.graph.utils.Random;
+import org.softwareheritage.graph.utils.Statistics;
+import org.softwareheritage.graph.utils.Timing;
+
+/**
+ * Benchmark to time edge access time.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class AccessEdge {
+ /**
+ * Main entrypoint.
+ *
+ * @param args command line arguments
+ */
+ public static void main(String[] args) throws IOException {
+ String path = args[0];
+ Graph graph = new Graph(path);
+
+ final long seed = 42;
+ final long nbNodes = 1_000_000;
+ Random random = new Random(seed);
+ long[] nodeIds = random.generateNodeIds(graph, nbNodes);
+
+ ArrayList<Double> timings = new ArrayList<>();
+ for (long nodeId : nodeIds) {
+ long startTime = Timing.start();
+ LazyLongIterator neighbors = graph.lazySuccessors(nodeId);
+ long firstNeighbor = neighbors.nextLong();
+ double duration = (double) Timing.stop(startTime);
+ timings.add(duration);
+ }
+
+ System.out.println("Used " + nbNodes + " random edges (results are in seconds):");
+ Statistics stats = new Statistics(timings);
+ stats.printAll();
+ }
+}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java b/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java
@@ -0,0 +1,43 @@
+package org.softwareheritage.graph.utils;
+
+import org.softwareheritage.graph.Graph;
+
+/**
+ * Random related utility class.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class Random {
+ /** Internal pseudorandom generator */
+ java.util.Random random;
+
+ /**
+ * Constructor.
+ */
+ public Random() {
+ this.random = new java.util.Random();
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param seed random generator seed
+ */
+ public Random(long seed) {
+ this.random = new java.util.Random(seed);
+ }
+
+ /**
+ * Generates random node ids.
+ *
+ * @param graph graph from which node ids will be picked
+ * @param nbNodes number of node ids to generate
+ * @return an array of random node ids
+ */
+ public long[] generateNodeIds(Graph graph, long nbNodes) {
+ return random.longs(nbNodes, 0, graph.getNbNodes()).toArray();
+ }
+}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java b/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java
@@ -0,0 +1,89 @@
+package org.softwareheritage.graph.utils;
+
+import java.util.ArrayList;
+
+/**
+ * Compute various statistics on a list of values.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class Statistics {
+ /** Input values */
+ ArrayList<Double> values;
+
+ /**
+ * Constructor.
+ *
+ * @param values input values
+ */
+ public Statistics(ArrayList<Double> values) {
+ this.values = values;
+ }
+
+ /**
+ * Returns the minimum value.
+ *
+ * @return minimum value
+ */
+ public double getMin() {
+ double min = Double.POSITIVE_INFINITY;
+ for (double v : values) {
+ min = Math.min(min, v);
+ }
+ return min;
+ }
+
+ /**
+ * Returns the maximum value.
+ *
+ * @return maximum value
+ */
+ public double getMax() {
+ double max = Double.NEGATIVE_INFINITY;
+ for (double v : values) {
+ max = Math.max(max, v);
+ }
+ return max;
+ }
+
+ /**
+ * Computes the average.
+ *
+ * @return average value
+ */
+ public double getAverage() {
+ double sum = 0;
+ for (double v : values) {
+ sum += v;
+ }
+ return sum / (double) values.size();
+ }
+
+ /**
+ * Computes the standard deviation.
+ *
+ * @return standard deviation value
+ */
+ public double getStandardDeviation() {
+ double average = getAverage();
+ double variance = 0;
+ for (double v : values) {
+ variance += (v - average) * (v - average);
+ }
+ variance /= (double) values.size();
+ return Math.sqrt(variance);
+ }
+
+ /**
+ * Computes and prints all statistical values.
+ */
+ public void printAll() {
+ System.out.println("min value: " + getMin());
+ System.out.println("max value: " + getMax());
+ System.out.println("average: " + getAverage());
+ System.out.println("standard deviation: " + getStandardDeviation());
+ }
+}

File Metadata

Mime Type
text/plain
Expires
Sun, Aug 17, 7:57 PM (2 w, 1 d ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
3219239

Event Timeline

About · Developer information · Legal