I was assigned an university project where I had to parse directed graph files coming from SNAP and then convert them into CSR (Compressed Sparse Row) format. Then the client must have the ability to perform connection queries between any 2 vertices by using Bidirectional BFS.
Here is my implementation:
Main.java
public class Main
{
public static void main(String[] args)
{
InputInterface input = null;
switch (args.length)
{
case 1:
input = new KeyboardHandler();
break;
case 3:
if(args[1].equalsIgnoreCase("-f"))
input = new QueryFileHandler(args[2]);
else
{
System.out.println("Usage: program <graphPath> [-f <queriesFile> ] ");
System.exit(1);
}
break;
default:
System.out.println("Usage: program <graphPath> [-f <queriesFile> ] ");
System.exit(1);
break;
}
try
{
AdjacencyListGraph s = new AdjacencyListGraph(args[0]);
CSRGraph normalCSR = new CSRGraph(s,GraphType.NORMAL);
CSRGraph invertedCSR = new CSRGraph(s,GraphType.INVERTED);
BidirectionalBFS bfs = new BidirectionalBFS(normalCSR,invertedCSR);
input.processQueries(bfs);
}
catch(AdjacencyListGraphNotCompletedException ex)
{
System.out.println(ex.getMessage() + "\nTerminating application...");
System.exit(2);
}
catch(CSRGraphNotCompletedException ex)
{
System.out.println(ex.getMessage() + "\nTerminating application...");
System.exit(3);
}
}
}
AdjacencyListGraph.java
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.time.Duration;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.regex.Pattern;
public class AdjacencyListGraph
{
private final HashMap<Long, LinkedList<Long>> normalGraph = new HashMap<>();
private final HashMap<Long, LinkedList<Long>> invertedGraph = new HashMap<>();
private int totalEdges;
//Constructor
public AdjacencyListGraph(String path) throws AdjacencyListGraphNotCompletedException
{
System.out.println("Parsing file " + path);
long tStart = System.nanoTime();
try
{
File file = new File(path);
FileInputStream fis = new FileInputStream(file);
InputStreamReader isr = new InputStreamReader(fis, StandardCharsets.US_ASCII);
BufferedReader br = new BufferedReader(isr);
Pattern pattern = Pattern.compile("\\s");
int lineCounter = 0;
String line;
while ((line = br.readLine()) != null)
{
lineCounter++;
if (line.charAt(0) != '#') //Discarding any comments
{
try
{
//Tokenize the line
final String[] tokens = pattern.split(line);
final long source = Long.parseLong(tokens[0]);
final long target = Long.parseLong(tokens[1]);
//Add the edge to the 2 Maps
addTargetToSource(normalGraph,source,target);
addTargetToSource(invertedGraph,target,source);
this.totalEdges++;
}
catch(NumberFormatException ex)
{
System.out.println("Error at line " + lineCounter + " : Could not parse. String was: " + line + ". Skipping line ");
}
}
}
br.close();
long tEnd = System.nanoTime();
System.out.println("Loaded " + totalEdges + " edges in " + Duration.ofNanos(tEnd - tStart).toMillis() + "ms");
}
catch (FileNotFoundException ex)
{
throw new AdjacencyListGraphNotCompletedException("Invalid file path given.");
}
catch (IOException ex)
{
throw new AdjacencyListGraphNotCompletedException("I/0 error occurred.");
}
}
//Getters
public HashMap<Long, LinkedList<Long>> getNormalGraph()
{
return this.normalGraph;
}
public HashMap<Long, LinkedList<Long>> getInvertedGraph()
{
return invertedGraph;
}
public int getTotalEdges()
{
return this.totalEdges;
}
private void addTargetToSource(HashMap<Long, LinkedList<Long>> map, Long source, Long target)
{
map.putIfAbsent(source, new LinkedList<>());
map.get(source).add(target);
}
}
AdjacencyListGraphNotCompletedException.java
public class AdjacencyListGraphNotCompletedException extends Exception
{
public AdjacencyListGraphNotCompletedException(String message)
{
super(message);
}
}
CSRGraph.java
import java.time.Duration;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
enum GraphType
{
NORMAL("Normal"),
INVERTED("Inverted");
final String name;
GraphType(String name)
{
this.name = name;
}
}
public class CSRGraph
{
private HashMap<Long, Integer> idMap ;
private int[] IA;
private long[] JA;
public CSRGraph(AdjacencyListGraph graph, GraphType type) throws CSRGraphNotCompletedException
{
long tStart = System.nanoTime();
HashMap<Long, LinkedList<Long>> graphMap;
switch (type)
{
case NORMAL:
graphMap = graph.getNormalGraph();
break;
case INVERTED:
graphMap = graph.getInvertedGraph();
break;
default:
throw new CSRGraphNotCompletedException("Implementation error.");
}
if(graphMap.isEmpty())
throw new CSRGraphNotCompletedException("Error in the creation of CSR: No edges exist.");
this.idMap = new HashMap<>(graphMap.size());
this.IA = new int[graphMap.size()+1];
this.IA[0] = 0;
this.JA = new long[graph.getTotalEdges()];
int IA_Index = 0;
int JA_Index = 0;
//Iterate through every HashMap entry
for(Map.Entry<Long, LinkedList<Long>> entry : graphMap.entrySet())
{
long key = entry.getKey();
LinkedList<Long> values = entry.getValue();
for (long target : values)
this.JA[JA_Index++] = target;
this.idMap.put(key, IA_Index);
this.IA[IA_Index + 1] = IA[IA_Index] + values.size();
IA_Index++;
}
long tEnd = System.nanoTime();
System.out.println(type.name + " graph conversion to CSR took " + Duration.ofNanos(tEnd - tStart).toMillis() + "ms");
}
public LinkedList<Long> getNeighbors(long id)
{
LinkedList<Long> children = new LinkedList<>();
if(!idMap.containsKey(id))
return children;
int id_Index = idMap.get(id);
long [] children_arr = Arrays.copyOfRange(JA,IA[id_Index],IA[id_Index+1]);
for(long target : children_arr)
children.add(target);
return children;
}
public boolean vertexExists(long id)
{
return idMap.containsKey(id);
}
}
CSRGraphNotCompletedException.java
public class CSRGraphNotCompletedException extends Exception
{
public CSRGraphNotCompletedException(String message)
{
super(message);
}
}
BidirectionalBFS.java
import java.time.Duration;
import java.util.HashMap;
import java.util.LinkedList;
public class BidirectionalBFS
{
private final CSRGraph normalGraph;
private final CSRGraph invertedGraph;
public BidirectionalBFS(CSRGraph normalGraph, CSRGraph invertedGraph)
{
this.normalGraph = normalGraph;
this.invertedGraph = invertedGraph;
}
public BFSResult connectionQuery(VertexPair query)
{
long tStart = System.nanoTime();
long source = query.getSourceNode();
long target = query.getTargetNode();
/*We then check if the source and target nodes even exist in the graph.
We earn a lot of time if we skip doomed BFS queries.
*/
boolean source_exists = normalGraph.vertexExists(source);
boolean target_exists = invertedGraph.vertexExists(target);
if(!source_exists || !target_exists)
return new BFSResult(source,source_exists,target,target_exists,false,null,Duration.ofNanos(System.nanoTime() - tStart));
else if(source == target)
return new BFSResult(source, true, target, true,true, 0, Duration.ofNanos(System.nanoTime() - tStart));
LinkedList<Long> queueNormal = new LinkedList<>();
LinkedList<Long> queueInverted = new LinkedList<>();
HashMap<Long,Integer> nodeInfoNormal = new HashMap<>();
HashMap<Long,Integer> nodeInfoInverted = new HashMap<>();
nodeInfoNormal.put(source,0);
nodeInfoInverted.put(target,0);
queueNormal.add(source);
queueInverted.add(target);
while (!queueNormal.isEmpty() || !queueInverted.isEmpty())
{
Intersection intersection;
if ((intersection = graphBFS(normalGraph,queueNormal, nodeInfoNormal, nodeInfoInverted)).intersectionExists() ||
(intersection = graphBFS(invertedGraph,queueInverted, nodeInfoInverted, nodeInfoNormal)).intersectionExists())
{
int normalDistance = nodeInfoNormal.get(intersection.getIntersectNode());
int invertedDistance = nodeInfoInverted.get(intersection.getIntersectNode());
int totalDistance = normalDistance + invertedDistance;
return new BFSResult(source, true, target, true, true, totalDistance, Duration.ofNanos(System.nanoTime() - tStart));
}
}
return new BFSResult(source,true,target,true,false,null,Duration.ofNanos(System.nanoTime() - tStart));
}
private Intersection graphBFS(CSRGraph graph,
LinkedList<Long> queue,
HashMap<Long,Integer> nodeInfoThisGraph,
HashMap<Long,Integer> nodeInfoOtherGraph)
{
if (!queue.isEmpty())
{
long current_node = queue.remove();
LinkedList<Long> adjacentNodes = graph.getNeighbors(current_node);
while (!adjacentNodes.isEmpty())
{
long adjacent = adjacentNodes.poll();
if (nodeInfoOtherGraph.containsKey(adjacent))
{
nodeInfoThisGraph.put(adjacent,nodeInfoThisGraph.get(current_node)+1);
return new Intersection(true,adjacent);
}
else if(!nodeInfoThisGraph.containsKey(adjacent))
{
nodeInfoThisGraph.put(adjacent,nodeInfoThisGraph.get(current_node)+1);
queue.add(adjacent);
}
}
}
return new Intersection(false,null);
}
public void areConnected(VertexPair query)
{
BFSResult res = connectionQuery(query);
System.out.println(res.toString());
}
}
final class BFSResult {
private final long source_id;
private final boolean source_exists;
private final long target_id;
private final boolean target_exists;
private final boolean areConnected;
private final Integer distance;
private final Duration timeElapsed;
public BFSResult(long source_id, boolean source_exists, long target_id, boolean target_exists, boolean areConnected, Integer distance, Duration timeElapsed) {
this.source_id = source_id;
this.source_exists = source_exists;
this.target_id = target_id;
this.target_exists = target_exists;
this.areConnected = areConnected;
this.distance = distance;
this.timeElapsed = timeElapsed;
}
public long getSource_id()
{
return source_id;
}
public boolean isSource_exists()
{
return source_exists;
}
public long getTarget_id()
{
return target_id;
}
public boolean isTarget_exists()
{
return target_exists;
}
public boolean isAreConnected()
{
return areConnected;
}
public Integer getDistance()
{
return distance;
}
public Duration getTimeElapsed()
{
return timeElapsed;
}
@Override
public String toString() {
return "BFSResult{" +
"source_id=" + source_id +
", source_exists=" + source_exists +
", target_id=" + target_id +
", target_exists=" + target_exists +
", areConnected=" + areConnected +
", distance=" + distance +
", timeElapsed=" + timeElapsed.toMillis() + "ms" +
'}';
}
}
final class Intersection
{
private final boolean intersectionExists;
private final Long intersectNode;
public Intersection(boolean intersectionExists,Long intersectNode)
{
this.intersectionExists = intersectionExists;
this.intersectNode = intersectNode;
}
public boolean intersectionExists()
{
return intersectionExists;
}
public Long getIntersectNode()
{
return intersectNode;
}
}
InputInterface.java
public interface InputInterface
{
void processQueries(BidirectionalBFS bfs);
}
KeyboardHandler.java
import java.util.Scanner;
public class KeyboardHandler implements InputInterface
{
private Scanner scan = new Scanner(System.in);
public void processQueries(BidirectionalBFS bfs)
{
System.out.println("Using keyboard input.");
while(true)
{
System.out.println("Give a node pair (source,target)");
VertexPair query = new VertexPair(longPositiveZero(),longPositiveZero());
bfs.areConnected(query);
System.out.println("Would you like an another query? (Yes/No)");
String answer = stringEqualsIgnoreCase(new String[]{"Yes","No"});
if(answer.equalsIgnoreCase("No"))
{
System.out.println("Thank you for using our software!");
System.exit(0);
}
}
}
public long longPositiveZero()
{
long value;
while(true)
{
while (!scan.hasNextLong())
{
System.out.println("Expected an Integer. Please type again.");
scan.next();
}
value = scan.nextLong();
if(value >= 0)
return value;
else
System.out.println("Field cannot be negative. Please type again.");
}
}
public String stringEqualsIgnoreCase(String[] args)
{
while(true)
{
String value = scan.next();
for(String i : args)
{
if(value.equalsIgnoreCase(i))
return i;
}
System.out.println("Invalid value. Please type again.");
}
}
}
QueryFileHandler.java
import java.io.*;
import java.nio.charset.StandardCharsets;
import java.time.Duration;
import java.util.LinkedList;
import java.util.regex.Pattern;
public class QueryFileHandler implements InputInterface
{
private String path;
public QueryFileHandler(String path)
{
this.path = path;
}
public void processQueries(BidirectionalBFS bfs)
{
System.out.println("Using file input mode.");
LinkedList<VertexPair> queries = null;
try
{
queries = parseQueries();
}
catch (QueryFileHandlerException ex)
{
System.out.println(ex.getMessage() + "\nTerminating application...");
System.exit(3);
}
while(queries.size() != 0)
{
VertexPair query = queries.poll();
bfs.areConnected(query);
}
System.out.println("Thank you for using our software!");
}
private LinkedList<VertexPair> parseQueries() throws QueryFileHandlerException
{
long totalQueries = 0;
LinkedList<VertexPair> queries = new LinkedList<>();
System.out.println("Parsing query file " + path);
long tStart = System.nanoTime();
try
{
File file = new File(path);
FileInputStream fis = new FileInputStream(file);
InputStreamReader isr = new InputStreamReader(fis, StandardCharsets.US_ASCII);
BufferedReader br = new BufferedReader(isr);
Pattern pattern = Pattern.compile("\\s");
int lineCounter = 0;
String line;
while ((line = br.readLine()) != null)
{
lineCounter++;
if (line.charAt(0) != '#') //Discarding any comments
{
try
{
//Tokenize the line
final String[] tokens = pattern.split(line);
final long source = Long.parseLong(tokens[0]);
final long target = Long.parseLong(tokens[1]);
queries.add(new VertexPair(source,target));
totalQueries++;
}
catch(NumberFormatException ex)
{
System.out.println("Error at line " + lineCounter + " : Could not parse. String was: " + line + ". Skipping line ");
}
}
}
br.close();
long tEnd = System.nanoTime();
System.out.println("Loaded " + totalQueries + " queries in " + Duration.ofNanos(tEnd - tStart).toMillis() + "ms");
if(totalQueries == 0)
throw new QueryFileHandlerException("File does not contain any pair of nodes.");
return queries;
}
catch (FileNotFoundException ex)
{
throw new QueryFileHandlerException("Invalid file path given.");
}
catch (IOException ex)
{
throw new QueryFileHandlerException("I/0 error occurred.");
}
}
QueryFileHandlerException.java
public class QueryFileHandlerException extends Exception
{
public QueryFileHandlerException(String message)
{
super(message);
}
}
VertexPair.java
public class VertexPair
{
private long sourceNode;
private long targetNode;
public VertexPair(long sourceNode, long targetNode)
{
this.sourceNode = sourceNode;
this.targetNode = targetNode;
}
public long getSourceNode()
{
return sourceNode;
}
public long getTargetNode()
{
return targetNode;
}
}
Part from a sample file soc-epinions1.txt
# Directed graph (each unordered pair of nodes is saved once): soc-Epinions1.txt
# Directed Epinions social network
# Nodes: 75879 Edges: 508837
# FromNodeId ToNodeId
0 4
0 5
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
What is your opinion about this implementation ? Please suggest any enhancements that can be made.
