  In this paper, we propose an efficient concurrent wait-free algorithm to
construct an unbounded directed graph for shared memory architecture. To the
best of our knowledge that this is the first wait-free algorithm for an
unbounded directed graph where insertion and deletion of vertices and/or edges
can happen concurrently. To achieve wait-freedom in a dynamic setting, threads
help each other to perform the desired tasks using operator descriptors by
other threads. To enhance performance, we also developed an optimized wait-free
graph based on the principle of fast-path-slow-path. We also prove that all
graph operations are wait-free and linearizable. We implemented our algorithms
in C++ and tested its performance through several micro-benchmarks. Our
experimental results show an average of 9x improvement over the global
lock-based implementation.
