Maximum flow algorithms for interactive application
Hello fellow Boost users, I have been using the boost.graph library in an interactive application for solving the maximum flow problem using the push_relabel algorith. The application consists of the user building the graph network interactively, node by node and edge by edge. Currently the maximum flow for the whole system is recalculated after each change. In addition to the total maximum flow the individual flows in all edges are used by the application. The problem is that interactivity is lost when the amount of nodes approaches 10k with the number of edges varying between 20k-40k. My question is: Is there an algorithm that would let me quickly calculate the changed maxium flow solution after each change without needing to do the global calculations again? The idea here would be to amortize the running time over each interactive change and thus keep response times acceptable (<200ms). My intuition tells me something like this should be possible, but I don't want to reinvent the wheel. Thank you in advance. If someone replies by email I will summarize to the group. Have a nice summer. -- Kai-Peter Bäckman, kai-peter.backman@mistaril.com http://www.mistaril.com - Space Station Manager - PC strategy game
participants (1)
-
Kai-Peter B�ckman