Differential D4028 Diff 14692 java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java

Changeset View

Standalone View

java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java

Show All 9 Lines
import it.unimi.dsi.logging.ProgressLogger;		import it.unimi.dsi.logging.ProgressLogger;
import org.slf4j.Logger;		import org.slf4j.Logger;
import org.slf4j.LoggerFactory;		import org.slf4j.LoggerFactory;
import org.softwareheritage.graph.Graph;		import org.softwareheritage.graph.Graph;

import java.io.File;		import java.io.File;
import java.io.IOException;		import java.io.IOException;


public class BFS {		public class BFS {
private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class);		private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class);
private final ImmutableGraph graph;		private final ImmutableGraph graph;

public BFS(ImmutableGraph graph) {		public BFS(ImmutableGraph graph) {
this.graph = graph;		this.graph = graph;
}		}

private static JSAPResult parse_args(String[] args) {		private static JSAPResult parse_args(String[] args) {
JSAPResult config = null;		JSAPResult config = null;
try {		try {
SimpleJSAP jsap = new SimpleJSAP(		SimpleJSAP jsap = new SimpleJSAP(BFS.class.getName(), "",
BFS.class.getName(),
"",
new Parameter[]{		new Parameter[]{
new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED,		new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
'g', "graph", "Basename of the compressed graph"),		"graph", "Basename of the compressed graph"),

new FlaggedOption("useTransposed", JSAP.BOOLEAN_PARSER, "false", JSAP.NOT_REQUIRED,		new FlaggedOption("useTransposed", JSAP.BOOLEAN_PARSER, "false", JSAP.NOT_REQUIRED, 'T',
'T', "transposed", "Use transposed graph (default: false)"),		"transposed", "Use transposed graph (default: false)"),});
}
);

config = jsap.parse(args);		config = jsap.parse(args);
if (jsap.messagePrinted()) {		if (jsap.messagePrinted()) {
System.exit(1);		System.exit(1);
}		}
} catch (JSAPException e) {		} catch (JSAPException e) {
e.printStackTrace();		e.printStackTrace();
}		}
Show All 30 Lines	private void bfsperm() throws IOException {
// indices up to 2^37		// indices up to 2^37
final LongArrayBitVector visited = LongArrayBitVector.ofLength(n);		final LongArrayBitVector visited = LongArrayBitVector.ofLength(n);
final ProgressLogger pl = new ProgressLogger(LOGGER);		final ProgressLogger pl = new ProgressLogger(LOGGER);
pl.expectedUpdates = n;		pl.expectedUpdates = n;
pl.itemsName = "nodes";		pl.itemsName = "nodes";
pl.start("Starting breadth-first visit...");		pl.start("Starting breadth-first visit...");

for (long i = 0; i < n; i++) {		for (long i = 0; i < n; i++) {
if (visited.getBoolean(i)) continue;		if (visited.getBoolean(i))
		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);

final LazyLongIterator iterator = graph.successors(currentNode);		final LazyLongIterator iterator = graph.successors(currentNode);
Show All 16 Lines