Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
Show All 13 Lines | |||||
import it.unimi.dsi.logging.ProgressLogger; | import it.unimi.dsi.logging.ProgressLogger; | ||||
import it.unimi.dsi.fastutil.Arrays; | import it.unimi.dsi.fastutil.Arrays; | ||||
import java.io.File; | import java.io.File; | ||||
import java.io.IOException; | import java.io.IOException; | ||||
public class BFS { | public class BFS { | ||||
private Graph graph; | private final ImmutableGraph graph; | ||||
private void load_graph(String graphBasename) throws IOException { | |||||
System.err.println("Loading graph " + graphBasename + " ..."); | |||||
this.graph = new Graph(graphBasename); | |||||
System.err.println("Graph loaded."); | |||||
} | |||||
private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class); | private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class); | ||||
public BFS(ImmutableGraph graph) { | |||||
this.graph = graph; | |||||
} | |||||
// Partly inlined from it.unimi.dsi.law.big.graph.BFS | // Partly inlined from it.unimi.dsi.law.big.graph.BFS | ||||
private static void bfsperm(final ImmutableGraph graph) throws IOException { | private void bfsperm() throws IOException { | ||||
final long n = graph.numNodes(); | final long n = graph.numNodes(); | ||||
// Allow enough memory to behave like in-memory queue | // Allow enough memory to behave like in-memory queue | ||||
int bufferSize = (int)Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n); | int bufferSize = (int)Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n); | ||||
// Use a disk based queue to store BFS frontier | // Use a disk based queue to store BFS frontier | ||||
final File queueFile = File.createTempFile(BFS.class.getSimpleName(), "queue"); | final File queueFile = File.createTempFile(BFS.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]; | ||||
// WARNING: no 64-bit version of this data-structure, but it can support | // WARNING: no 64-bit version of this data-structure, but it can support | ||||
// 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..."); | ||||
long pos = 0; | |||||
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); | ||||
Show All 36 Lines | private static JSAPResult parse_args(String[] args) { | ||||
System.exit(1); | System.exit(1); | ||||
} | } | ||||
} catch (JSAPException e) { | } catch (JSAPException e) { | ||||
e.printStackTrace(); | e.printStackTrace(); | ||||
} | } | ||||
return config; | return config; | ||||
} | } | ||||
public static void main(String[] args) { | public static void main(String[] args) throws IOException { | ||||
JSAPResult config = parse_args(args); | JSAPResult config = parse_args(args); | ||||
String graphPath = config.getString("graphPath"); | String graphPath = config.getString("graphPath"); | ||||
boolean useTransposed = config.getBoolean("useTransposed"); | boolean useTransposed = config.getBoolean("useTransposed"); | ||||
ProgressLogger logger = new ProgressLogger(); | System.err.println("Loading graph " + graphPath + " ..."); | ||||
long startTime; | Graph graph = new Graph(graphPath); | ||||
double totalTime; | System.err.println("Graph loaded."); | ||||
BFS bfs = new BFS(); | if (useTransposed) | ||||
try { | graph = graph.transpose(); | ||||
bfs.load_graph(graphPath); | |||||
} catch (IOException e) { | |||||
System.out.println("Could not load graph: " + e); | |||||
System.exit(2); | |||||
} | |||||
logger.start("Parallel BFS visit..."); | BFS bfs = new BFS(graph); | ||||
try { | bfs.bfsperm(); | ||||
BFS.bfsperm(bfs.graph.getBVGraph(useTransposed)); | |||||
} catch (IOException e) { | |||||
e.printStackTrace(); | |||||
} | |||||
logger.done(); | |||||
} | } | ||||
} | } |