Pseudo-parallel depth-first search

Question

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it.

How can I make the dfs part faster, because now it seems to be doing a lot of nothing (each thread just sets the nodes parent and marks it as visited)?

Is this implementation even ok?

I'm open to any implementation changes and ideas.

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.apache.commons.cli.CommandLine;
import org.apache.commons.cli.CommandLineParser;
import org.apache.commons.cli.DefaultParser;
import org.apache.commons.cli.Options;
import org.apache.commons.cli.ParseException;
public class Graph {
/**
 * A map containing the node number and a boolean to decide if it is visited.
 */
private ConcurrentHashMap<Integer, AtomicBoolean> visited = new ConcurrentHashMap<>();
/**
 * A map containing a list of neighbors for each node. 
 */
private ConcurrentHashMap<Integer, List<Integer>> adjacencyList = new ConcurrentHashMap<>();
/**
 * A map containing a node number and a node object.
 */
private ConcurrentHashMap<Integer,Node> treeNodes = new ConcurrentHashMap<>();
public static void main(String[] args) {
 Options options = new Options();
 setOptions(options); 
 CommandLineParser parser = new DefaultParser();
 CommandLine cmd = null;
 try {
 cmd = parser.parse( options, args);
 } catch (ParseException e) {
 System.exit(-1);
 }
 determinePrintLocation(cmd);
 PrintStream originalStream = System.out;
 Graph graph = new Graph();
 determineGraphCreation(cmd, graph);
 doExecution(cmd, graph);
 shouldWriteTreeToFile(cmd, graph);
}
/**
 * Determines if the tree information from the program execution should be written to a file.
 * @param cmd
 * @param graph
 */
protected static void shouldWriteTreeToFile(CommandLine cmd, Graph graph) {
 if(cmd.hasOption("gf")) {
 String outputFileName = cmd.getOptionValue("gf");
 graph.writeToFile(outputFileName);
 }
}
/**
 * Determines with how many threads should the algorithm be executed.
 * @param cmd
 * @param graph
 */
protected static void doExecution(CommandLine cmd, Graph graph) {
 if(cmd.hasOption("t")) {
 String threadCountString = cmd.getOptionValue("t");
 Integer threadCount = Integer.valueOf(threadCountString);
 graph.execute(threadCount);
 } else {
 graph.execute(1);
 }
}
/**
 * Determines if the graph should be created from a file or on the go.
 * @param cmd
 * @param graph
 */
protected static void determineGraphCreation(CommandLine cmd, Graph graph) {
 if(cmd.hasOption("n")) {
 String nodeCountString = cmd.getOptionValue("n", "1");
 Integer nodeCount = Integer.valueOf(nodeCountString);
 graph.generateGraph(nodeCount);
 } else if (cmd.hasOption("i")) {
 String fileName = cmd.getOptionValue("i");
 graph.constructGraphFromFile(fileName);
 }
}
/**
 * Determines the location of the print file in which the 
 * thread execution time and data should be written.
 * @param cmd
 */
protected static void determinePrintLocation(CommandLine cmd) {
 if(cmd.hasOption("q")) {
 System.setOut(new NullPrintStream());
 } else if(cmd.hasOption("o")) {
 String fileName = cmd.getOptionValue("o", "output_file.txt");
 try {
 System.setOut(new PrintStream(new BufferedOutputStream(new FileOutputStream(fileName)), true));
 } catch (FileNotFoundException e) {
 Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, "Failed to create output stream.", e);
 }
 }
}
/**
 * Sets the command line options.
 * @param options
 */
protected static void setOptions(Options options) {
 options.addOption("n", true, "The number of nodes of the graph.");
 options.addOption("i", true, "The input file for the graph.");
 options.addOption("o", true, "The output file for the application");
 options.addOption("t", true, "The amount of threads to be used");
 options.addOption("q", false, "Determine if there should be output");
 options.addOption("gf",true, "File to which to write the graph information");
}
/**
 * Executes the parallel DFS.
 */
private void execute(int threadCount) { 
 ForkJoinPool pool = new ForkJoinPool(threadCount);
 // check each node, because the graph may not be connected
 System.out.println("Algorithm execution started with " + threadCount + " threads");
 long startTime = System.nanoTime();
 for(Integer node : visited.keySet()) {
 if(visited.get(node).get()) {
 continue;
 }
 DFS dfs = new DFS(node);
 pool.invoke(dfs);
 }
 long endTime = System.nanoTime();
 long elapsedTime = endTime - startTime;
 System.out.println("Algorithm execution took " + elapsedTime + " nanoseconds");
}
/**
 * Writes the graph data to a file.
 * @param fileName
 */
public void writeToFile(String fileName) {
 File file = new File(fileName);
 try(BufferedWriter bwr = new BufferedWriter(new FileWriter(file))) {
 for(Node node : treeNodes.values()) {
 bwr.write("Node number: " + node.getNode());
 bwr.newLine();
 if(node.getParent() != null){
 bwr.write("Node parent: " + node.getParent().getNode());
 bwr.newLine();
 } 
 }
 } catch (IOException ex) {
 Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, "Failed to create output stream for the graph data.", ex);
 }
}
/**
 * Generates a graph in memory.
 * @param nodeCount
 */
private void generateGraph(int nodeCount) {
 ThreadLocalRandom random = ThreadLocalRandom.current();
 visited = new ConcurrentHashMap<>(nodeCount);
 System.out.println("Started graph creation.");
 for(int i=0 ; i < nodeCount ; i++) {
 List<Integer> neighbours = new LinkedList<>();
 for(int j=0; j < nodeCount ; j++) {
 int choice = random.nextInt(2);
 if(choice == 1) {
 neighbours.add(j);
 } 
 }
 adjacencyList.put(i, neighbours);
 visited.put(i, new AtomicBoolean(false));
 treeNodes.put(i, new Node(i));
 }
 System.out.println("Graph created.");
}
/**
 * Construct a graph from an adjacency matrix in a file.
 * @param fileName
 */
public void constructGraphFromFile(String fileName) {
 System.out.println("Construction of graph from file started");
 File file = new File(fileName);
 try(BufferedReader br = new BufferedReader(new FileReader(file))) {
 String numberLine = br.readLine();
 int nodeCount = Integer.valueOf(numberLine);
 visited = new ConcurrentHashMap<>(nodeCount);
 int count = 0;
 for(String line; (line = br.readLine()) != null; ) {
 String[] data = line.split("\\s+");
 List<Integer> neighbours = new LinkedList<>();
 for(int i = 0; i < data.length ; i++) {
 if(data[i].equals("1")) {
 neighbours.add(i);
 }
 }
 adjacencyList.put(count, neighbours);
 treeNodes.put(count, new Node(count));
 visited.put(count, new AtomicBoolean(false));
 count++;
 }
 } catch (IOException ex) {
 Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, "Failed to construct graph from file.", ex);
 return;
 }
 System.out.println("Construction of graph from file finished");
}
private void constructGraphFile(String fileName, int size) {
 System.out.println("Construction of graph file started.");
 File file = new File(fileName);
 try {
 file.createNewFile();
 } catch (IOException ex) {
 Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, "Failed to create file with name: " + fileName, ex);
 }
 try(BufferedWriter bwr = new BufferedWriter(new FileWriter(file))){
 bwr.write(String.valueOf(size));
 bwr.newLine();
 ThreadLocalRandom random = ThreadLocalRandom.current();
 for(int i=0; i < size; i++) {
 StringBuilder builder = new StringBuilder();
 for(int j=0; j < size; j++) {
 builder.append(random.nextInt(2));
 builder.append(" ");
 }
 String trimed = builder.toString().trim();
 bwr.write(trimed);
 bwr.newLine(); 
 } 
 } catch (IOException ex) {
 Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, "Failed to construct adjecancy matrix file.", ex);
 return;
 }
 System.out.println("Construction of graph file finished.");
}
/**
 * Class implementing {@link RecursiveAction} which does the actual computation.
 * @author aleksandar
 *
 */
private class DFS extends RecursiveAction{
 int node;
 public DFS(int node) {
 this.node = node;
 }
 @Override
 protected void compute() {
 String threadName = Thread.currentThread().getName(); 
 AtomicBoolean isVisited = visited.get(node); 
 if(isVisited.getAndSet(true)) {
 return;
 }
 //System.out.println("Executing thread " + threadName + ". For node " + node);
 List<Integer> adjList = adjacencyList.get(node);
 Node parent = treeNodes.get(node);
 for(Integer neighbour : adjList) {
 Node child = treeNodes.get(neighbour);
 Integer childNode = child.getNode();
 if(visited.get(childNode).get()) {
 continue;
 }
 child.setParent(parent);
 DFS dfs = new DFS(neighbour);
 dfs.fork();
 }
 // System.out.println("Thread " + threadName + ". Finished work on node " + node + " and returned to thread pool"); 
 }
}
/**
 * Class representing a node in the graph.
 * @author aleksandar
 *
 */
private class Node {
 private Integer node;
 private Node parent;
 public Node(int node) {
 this.node = node;
 } 
 @Override
 public int hashCode() {
 int hash = 5;
 hash = 79 * hash + Objects.hashCode(this.node);
 return hash;
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj) {
 return true;
 }
 if (obj == null) {
 return false;
 }
 if (getClass() != obj.getClass()) {
 return false;
 }
 final Node other = (Node) obj;
 if (!Objects.equals(this.node, other.node)) {
 return false;
 }
 return true;
 } 
 public Integer getNode() {
 return node;
 }
 public Node getParent() {
 return parent;
 }
 public void setParent(Node parent) {
 this.parent = parent;
 }
}
}

PS: Updated with the latest version. It works with command line arguments, but for testing can use the methods directly. The compute method and whole synchonisation idea, I think can be improved.

The helper class if needed.

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.io.PrintStream;
/**
 * Class for redirecting a stream to nowhere.<br>
 * (Something like dev\null on UNIX)
 */
public class NullPrintStream extends PrintStream {
public NullPrintStream() {
 super(new NullByteArrayOutputStream());
}
private static class NullByteArrayOutputStream extends ByteArrayOutputStream {
@Override
public void write(int b) {
 // do nothing
}
@Override
public void write(byte[] b, int off, int len) {
 // do nothing
}
@Override
public void writeTo(OutputStream out) throws IOException {
 // do nothing
}
}
}

• Mast: Is this realisation even ok ? Does it work as intended? If it doesn't, you're asking in the wrong place.
• user3719857: @Mast Yes it works right. When printing the node and it's parent everything is ok. I even tested it with some visualisation. The realisation part was more of in the lines of "Is the idea of doing it like this, stupid or not ?" :D