Naive IStructure BFS works!  It's a little slower than naive Data.Set version, but it gets a parallel speedup.