  Graph algorithms applied in many applications, including social networks,
communication networks, VLSI design, graphics, and several others, require
dynamic modifications -- addition and removal of vertices and/or edges -- in
the graph. This paper presents a novel concurrent non-blocking algorithm to
implement a dynamic unbounded directed graph in a shared-memory machine. The
addition and removal operations of vertices and edges are lock-free. For a
finite sized graph, the lookup operations are wait-free. Most significant
component of the presented algorithm is the reachability query in a concurrent
graph. The reachability queries in our algorithm are obstruction-free and thus
impose minimal additional synchronization cost over other operations. We prove
that each of the data structure operations are linearizable. We extensively
evaluate a sample C/C++ implementation of the algorithm through a number of
micro-benchmarks. The experimental results show that the proposed algorithm
scales well with the number of threads and on an average provides 5 to 7x
performance improvement over a concurrent graph implementation using
coarse-grained locking.
