A parallel implementation of DFS for Directed Acyclic Graphs (https://research.nvidia.com/publication/parallel-depth-first-search-directed-acyclic-graphs)
This is a C++ implementation of a parallel algorithm of the DFS traversal, according to this paper. The idea under this algorithm is overcoming the problems of parallel implementations of the standard DFS-based labelling approach. That's because DFS requires a strict ordering in edges visitation and the usage of some global variables, which represent a great limitation whenever there is the need to go parallel.
This algorithm provides an efficient solution for the DFS traversal of directed acyclic graph (DAG) with no more than 3 BFS visits, which allow to find as result the pre-order, post-order and the parent relationship between the nodes of the DAG.
Note that this implementation has an additional BFS visit on the DAG (Figure F), aimed to compute outer and inner rank, respectively defined as
More info (except regarding ranks) in the paper.
For building the project use the provided CMakeLists.txt
, with the following
commands
$ mkdir -p build && cd build && cmake .. && make && cp parallel-dfs-dag .. && cd ..
The program receive a file containing the initial dag with the following format
<number of nodes>
0: <node1> <node2> ... #
...
<nodeId>: <nodeN> <nodeM> ... #
...
The initial line contains the number of nodes while all the next lines have the same format, starting with the (numeric) node identifier (must be incremental) followed by a colon and the the list of the nodes to which the current node points to.
For example the DAG of the previous example is represented as
7
0: 1 2 #
1: 3 4 #
2: 4 5 #
3: #
4: 6 #
5: 6 #
6: #
The third argument of the executable is the name of the file into which the ranks are going to be saved, with format:
node_number sv ev
The following is the content of the output file of the previous example:
0 1 7
1 1 4
2 2 6
3 1 1
4 2 3
5 2 5
6 2 2