Example of How to Use MAX_FLOW()
The following program shows how the function MAX_FLOW()
can be used to compute a maximum flow in a directed graph.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
In main() we first create a simple graph G
with four nodes and six edges. We use an edge_array<double>
cap to store the capacities of the edges of G. .
The variant of MAX_FLOW() for int can be used
in exactly the same way. You only need to replace double by
int in cap and flow.
#include <LEDA/graph/graph.h>
#include <LEDA/graph/max_flow.h>
using namespace leda;
int main()
{
graph G;
node n0=G.new_node(); node n1=G.new_node();
node n2=G.new_node(); node n3=G.new_node();
edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n3);
edge e2=G.new_edge(n1,n2); edge e3=G.new_edge(n1,n3);
edge e4=G.new_edge(n3,n1); edge e5=G.new_edge(n3,n2);
edge_array<double> cap(G);
cap[e0]=1.731; cap[e1]=5.341; cap[e2]=1.459;
cap[e3]=2.222; cap[e4]=2.389; cap[e5]=1.499;
In order to avoid that MAX_FLOW() modifies the edge capacities
internally, we call MAX_FLOW_SCALE_CAPS() explicitely. In
this small example the capacities are, of course, unchanged and MAX_FLOW_SCALE_CAPS()
returns true. We only want to demonstrate the usage here.
The edge_array<double> flow is used for the result
of MAX_FLOW(). flow[e] will contain the flow
over edge e in the computed maximum flow from s
to t. MAX_FLOW() returns the value of the maximum
flow.
After calling MAX_FLOW() we use the function CHECK_MAX_FLOW()
to check the result of the computation.
If the result is correct CHECK_MAX_FLOW() returns true
and we output the flow value and the flow on the edges of G.
Of course, in our example CHECK_MAX_FLOW() returns true and we output
the flow value and the flow on the edges of G.
edge_array<double> cap1=cap; //archive original capacities
node s=n0, t=n2;
bool caps_unchanged=MAX_FLOW_SCALE_CAPS(G,s,cap);
edge_array<double> flow(G);
double flow_value=MAX_FLOW(G,s,t,cap,flow);
bool is_maximum_flow=CHECK_MAX_FLOW(G,s,t,cap,flow);
if (is_maximum_flow) {
std::cout << "The maximum flow has value: "
<< flow_value << std::endl;
edge e;
forall_edges(e,G) {
if (flow[e]>0) {
G.print_edge(e);
std::cout << " flow = " << flow[e] << std::endl;
}
}
}
else std::cout << "Error: MAX_FLOW_T() "
<< "did not compute a maximum flow!" << std::endl;
return 0;
}
|