Graph algorithms have several diverse applications, including social
networks, communication networks, VLSI design, graphics, etc. Many of
these applications require dynamic modifications -- addition and
removal of vertices and/or edges -- in the graph. Our team has
recently developed algorithms for Concurrent Graphs which I will
explain in this talk. In this work, we developed 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. In addition to these point operations, we
then considered a set method which is the most significant component
of the presented algorithm: reachability query in a concurrent graph
which identifies if there is a path between two vertices in such a
dynamic network. The solution to the reachability query in our
algorithm is obstruction-free and thus impose minimal additional
synchronization cost over other operations. We showed that each of the
data structure operations is linearizable. We did some extensive
evaluations on the C++ implementation of the algorithm through various
micro-benchmarks. Our implementation results have also been very good.
On average, we perform around 5x times better than a sequential graph
implementation.