Differential D4028 Diff 14692 java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java
Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java
Show All 13 Lines | |||||
import org.softwareheritage.graph.Graph; | import org.softwareheritage.graph.Graph; | ||||
import org.softwareheritage.graph.Node; | import org.softwareheritage.graph.Node; | ||||
import org.softwareheritage.graph.experiments.forks.ForkCC; | import org.softwareheritage.graph.experiments.forks.ForkCC; | ||||
import java.io.*; | import java.io.*; | ||||
public class SubdatasetSizeFunction { | public class SubdatasetSizeFunction { | ||||
private SubdatasetSizeFunction() {} | private SubdatasetSizeFunction() { | ||||
} | |||||
public static void run(final Graph graph) throws IOException { | public static void run(final Graph graph) throws IOException { | ||||
final ProgressLogger pl = new ProgressLogger(); | final ProgressLogger pl = new ProgressLogger(); | ||||
pl.itemsName = "nodes"; | pl.itemsName = "nodes"; | ||||
pl.expectedUpdates = graph.numNodes(); | pl.expectedUpdates = graph.numNodes(); | ||||
long n = graph.numNodes(); | long n = graph.numNodes(); | ||||
LongArrayBitVector visited = LongArrayBitVector.ofLength(n); | LongArrayBitVector visited = LongArrayBitVector.ofLength(n); | ||||
int bufferSize = (int) Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n); | int bufferSize = (int) Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n); | ||||
final File queueFile = File.createTempFile(ForkCC.class.getSimpleName(), "queue"); | final File queueFile = File.createTempFile(ForkCC.class.getSimpleName(), "queue"); | ||||
final ByteDiskQueue queue = ByteDiskQueue.createNew(queueFile, bufferSize, true); | final ByteDiskQueue queue = ByteDiskQueue.createNew(queueFile, bufferSize, true); | ||||
final byte[] byteBuf = new byte[Long.BYTES]; | final byte[] byteBuf = new byte[Long.BYTES]; | ||||
long[][] randomPerm = Util.identity(graph.numNodes()); | long[][] randomPerm = Util.identity(graph.numNodes()); | ||||
LongBigArrays.shuffle(randomPerm, new XoRoShiRo128PlusRandom()); | LongBigArrays.shuffle(randomPerm, new XoRoShiRo128PlusRandom()); | ||||
long visitedSize = 0; | long visitedSize = 0; | ||||
pl.start("Running traversal starting from origins..."); | pl.start("Running traversal starting from origins..."); | ||||
for (long j = 0; j < n; ++j) { | for (long j = 0; j < n; ++j) { | ||||
long i = BigArrays.get(randomPerm, j); | long i = BigArrays.get(randomPerm, j); | ||||
if (visited.getBoolean(i) || graph.getNodeType(i) != Node.Type.ORI) { | if (visited.getBoolean(i) || graph.getNodeType(i) != Node.Type.ORI) { | ||||
continue; | continue; | ||||
} | } | ||||
queue.enqueue(Longs.toByteArray(i)); | queue.enqueue(Longs.toByteArray(i)); | ||||
visited.set(i); | visited.set(i); | ||||
while (!queue.isEmpty()) { | while (!queue.isEmpty()) { | ||||
queue.dequeue(byteBuf); | queue.dequeue(byteBuf); | ||||
final long currentNode = Longs.fromByteArray(byteBuf); | final long currentNode = Longs.fromByteArray(byteBuf); | ||||
visitedSize++; | visitedSize++; | ||||
final LazyLongIterator iterator = graph.successors(currentNode); | final LazyLongIterator iterator = graph.successors(currentNode); | ||||
long succ; | long succ; | ||||
while ((succ = iterator.nextLong()) != -1) { | while ((succ = iterator.nextLong()) != -1) { | ||||
if (visited.getBoolean(succ)) | if (visited.getBoolean(succ)) | ||||
continue; | continue; | ||||
visited.set(succ); | visited.set(succ); | ||||
queue.enqueue(Longs.toByteArray(succ)); | queue.enqueue(Longs.toByteArray(succ)); | ||||
} | } | ||||
pl.update(); | pl.update(); | ||||
} | } | ||||
System.out.println(visitedSize); | System.out.println(visitedSize); | ||||
} | } | ||||
pl.done(); | pl.done(); | ||||
} | } | ||||
static public void main(final String[] arg) throws IllegalArgumentException, SecurityException, JSAPException, IOException { | static public void main(final String[] arg) | ||||
final SimpleJSAP jsap = new SimpleJSAP(SubdatasetSizeFunction.class.getName(), "Computes in and out degrees of the given SWHGraph", | throws IllegalArgumentException, SecurityException, JSAPException, IOException { | ||||
new Parameter[] { | final SimpleJSAP jsap = new SimpleJSAP(SubdatasetSizeFunction.class.getName(), | ||||
new UnflaggedOption("basename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The basename of the graph."), | "Computes in and out degrees of the given SWHGraph", | ||||
} | new Parameter[]{new UnflaggedOption("basename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, | ||||
); | JSAP.NOT_GREEDY, "The basename of the graph."),}); | ||||
final JSAPResult jsapResult = jsap.parse(arg); | final JSAPResult jsapResult = jsap.parse(arg); | ||||
if (jsap.messagePrinted()) System.exit(1); | if (jsap.messagePrinted()) | ||||
System.exit(1); | |||||
final String basename = jsapResult.getString("basename"); | final String basename = jsapResult.getString("basename"); | ||||
Graph graph = new Graph(basename); | Graph graph = new Graph(basename); | ||||
run(graph); | run(graph); | ||||
} | } | ||||
} | } |