1
$\begingroup$

I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my original graph, I need to find all of the vertices which are reachable from the source vertex in the residual graph.

I was planning to use BFS or DFS to traverse the residual graph, but I was wondering if there was any more efficient algorithms that anyone can suggest, as the size of my graphs are pretty large.

I plan on implementing my own, modified version of the push relabel algorithm eventually, and then I can probably label them as I go. But for now I would like to just run it with the boost library, so that I have something for comparison - but unfortunately that requires labelling the vertices separately.

Any suggestions would be greatly appreciated

Improve this question
$\endgroup$
2
  • $\begingroup$ How big is your graph? $\endgroup$
    – adrianN
    Jun 21, 2016 at 6:58
  • $\begingroup$ potentially in the millions of vertices $\endgroup$
    – guskenny83
    Jun 21, 2016 at 6:59

3 Answers 3

Reset to default
1
$\begingroup$

For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.

Improve this answer
$\endgroup$
1
$\begingroup$

It's quite clear that you can't be better in terms of asymptotic bounds, at least not without further knowledge of the graph.

There may be some margin of improvement in the implementation, though, in particular if the graph is huge: parallelisation, considering memory hierarchy, and so on.

Also, note that there may be ways in the max-flow algorithm to get around computing everything anew in every step. You may want to check out Dinic's algorithm.

Improve this answer
$\endgroup$
0
$\begingroup$

The running time of BFS and DFS are asymptotically optimal (they can find all reachable vertices in linear time, i.e., linear in the number of reachable vertices), so you can't hope to do better by more than a constant factor.

Constant factors tend to depend heavily on platform-specific details (e.g., cache effects, the memory hierarchy) more than on algorithmics, so if you're looking for constant-factor speedups, that's probably off-topic here and more a matter of optimizing your code.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Okay, thanks for that. So between DFS and BFS, if the graph is very large with a lot of edges, I would probably be better off using DFS, as it has O(bd) space complexity as opposed to O(b^d), but both have the same time complexity? $\endgroup$
    – guskenny83
    Jun 21, 2016 at 6:58
  • $\begingroup$ @guskenny83, what's $b$ and what's $d$? Space complexity is not easy to compare. You might want to ask a new question about space complexity, after doing some research into it. $\endgroup$
    – D.W. ♦
    Jun 21, 2016 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.