Effectively, the parallel to PA4 here is that EDGEMAP_SPARSE is top-down and EDGEMAP_DENSE is bottom-up BFS; they are efficient in different scenarios (and Ligra provides a heuristic for switching between them). However, Ligra is even more powerful than that, because you can implement any F and C to get hugely varied algorithms.

Already mentioned in class, but digesting this slide really helps for Assignment 4!!

As we have seen in assignment 4, with EDGEMAP_DENSE, when the unvisited vertex set becomes a larger fraction of the overall vertex set, many edge visits are wasteful and do not lead to a successful update since another node has already checked that edge. This is when it is more efficient to use EDGEMAP_SPARSE since the unvisited vertex set is small and it is faster to loop over the entire set of unvisited vertices. As @mziv pointed out, EDGEMAP_SPARSE is the top down BFS approach and EDGEMAP_DENSE is bottom up.

Like what others have already discussed, EDGEMAP_DENSE (bottom-up) works better when the target graph is denser. Such input means that there can be a lot of accesses to nodes that have been visited. In this case, we can perform parallel_for for each target node instead. Since we are only looking for unvisited target nodes, and we're able to stop as soon as the first source node is identified, there is also no synchronization needed.