@@ -0,0 +1,2799 @@
+/*%0A * Copyright 2015 Delft University of Technology%0A *%0A * Licensed under the Apache License, Version 2.0 (the %22License%22);%0A * you may not use this file except in compliance with the License.%0A * You may obtain a copy of the License at%0A *%0A *         http://www.apache.org/licenses/LICENSE-2.0%0A *%0A * Unless required by applicable law or agreed to in writing, software%0A * distributed under the License is distributed on an %22AS IS%22 BASIS,%0A * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A * See the License for the specific language governing permissions and%0A * limitations under the License.%0A */%0Apackage nl.tudelft.graphalytics.sequentialjava.algorithms.bfs;%0A%0Aimport it.unimi.dsi.fastutil.longs.*;%0Aimport nl.tudelft.graphalytics.domain.algorithms.BreadthFirstSearchParameters;%0Aimport org.apache.logging.log4j.LogManager;%0Aimport org.apache.logging.log4j.Logger;%0A%0A/**%0A * Sequential Java implementation of the Breadth First Search algorithm.%0A *%0A * @author Tim Hegeman%0A */%0Apublic class BreadthFirstSearchJob %7B%0A%0A%09private static final Logger LOG = LogManager.getLogger();%0A%0A%09private static final long MAX_DISTANCE = Long.MAX_VALUE;%0A%0A%09private final Long2ObjectMap%3CLongList%3E graphData;%0A%09private final BreadthFirstSearchParameters parameters;%0A%0A%09public BreadthFirstSearchJob(Long2ObjectMap%3CLongList%3E graphData, BreadthFirstSearchParameters parameters) %7B%0A%09%09this.graphData = graphData;%0A%09%09this.parameters = parameters;%0A%09%7D%0A%0A%09public Long2LongMap run() %7B%0A%09%09LOG.debug(%22- Starting Breadth First Search algorithm%22);%0A%0A%09%09// Initialize distances%0A%09%09Long2LongMap distances = new Long2LongOpenHashMap(graphData.size());%0A%09%09for (Long2ObjectMap.Entry%3CLongList%3E entry : graphData.long2ObjectEntrySet()) %7B%0A%09%09%09distances.put(entry.getLongKey(), MAX_DISTANCE);%0A%09%09%7D%0A%09%09distances.put(parameters.getSourceVertex(), 0L);%0A%0A%09%09// Define visited set%0A%09%09LongSet visited = new LongOpenHashSet();%0A%09%09visited.add(parameters.getSourceVertex());%0A%0A%09%09// Define traversal queue%0A%09%09AbstractLongPriorityQueue queue = new LongArrayFIFOQueue();%0A%09%09queue.enqueue(parameters.getSourceVertex());%0A%0A%09%09// Traverse the graph%0A%09%09while (!queue.isEmpty()) %7B%0A%09%09%09long currentVertexId = queue.dequeueLong();%0A%09%09%09long currentVertexDistance = distances.get(currentVertexId);%0A%09%09%09// Iterate over all outgoing edges of this vertex%0A%09%09%09for (LongIterator neighbourIterator = graphData.get(currentVertexId).iterator(); neighbourIterator.hasNext(); ) %7B%0A%09%09%09%09long neighbour = neighbourIterator.nextLong();%0A%09%09%09%09// If a neighbour has not been visited, add it to the queue and set its distance from the root%0A%09%09%09%09if (!visited.contains(neighbour)) %7B%0A%09%09%09%09%09visited.add(neighbour);%0A%09%09%09%09%09queue.enqueue(neighbour);%0A%09%09%09%09%09distances.put(neighbour, currentVertexDistance + 1);%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09LOG.debug(%22- Finished Breadth First Search algorithm%22);%0A%0A%09%09return distances;%0A%09%7D%0A%0A%7D%0A

Add BFS implementation