EDGEMAP_SPARSE and EDGEMAP_DENSE correspond to bfs_bottom_up and bfs_top_down that we have implemented in Asst 3 Part 2.
This comment was marked helpful 0 times.
yanzhan2
@taegyunk, I think it is the other way around. bfs_bottom_up would deal with all the vertices in parallel, so it is EDGEMAP_DENSE. bfs_top_down deals with frontier elements in parallel, so it is EDGEMAP_SPARSE.
This comment was marked helpful 0 times.
aew
I agree with @yanshan2, EDGEMAP_DENSE would correspond to bfs_bottom_up, because we iterate over every vertex. EDGEMAP_SPARSE would correspond to bfs_top_down because we only consider the frontier. As we noted in the assignment, bottom up was more efficient when we had a large frontier. Therefore, when the graph is more dense, it makes more sense to use a bottom up step, where we check every vertex.
EDGEMAP_SPARSE
andEDGEMAP_DENSE
correspond tobfs_bottom_up
andbfs_top_down
that we have implemented in Asst 3 Part 2.This comment was marked helpful 0 times.
@taegyunk, I think it is the other way around. bfs_bottom_up would deal with all the vertices in parallel, so it is EDGEMAP_DENSE. bfs_top_down deals with frontier elements in parallel, so it is EDGEMAP_SPARSE.
This comment was marked helpful 0 times.
I agree with @yanshan2,
EDGEMAP_DENSE
would correspond tobfs_bottom_up
, because we iterate over every vertex.EDGEMAP_SPARSE
would correspond tobfs_top_down
because we only consider the frontier. As we noted in the assignment, bottom up was more efficient when we had a large frontier. Therefore, when the graph is more dense, it makes more sense to use a bottom up step, where we check every vertex.This comment was marked helpful 0 times.