We need a compare-and-swap in update because it is possible, update(v1,d) and update(v2,d) to be called in parallel in EDGEMAP (the case when two vertices in the frontier, v1 and v2, are adjacent to the same vertex, d, not in the frontier). We use CAS here simply to decide a winner of the race.
We need a compare-and-swap in update because it is possible, update(v1,d) and update(v2,d) to be called in parallel in EDGEMAP (the case when two vertices in the frontier, v1 and v2, are adjacent to the same vertex, d, not in the frontier). We use CAS here simply to decide a winner of the race.
This comment was marked helpful 0 times.