1 | #include <iostream>
|
---|
2 | #include <sstream>
|
---|
3 | #include <iomanip>
|
---|
4 |
|
---|
5 | #include <boost/graph/adjacency_list.hpp>
|
---|
6 | #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
|
---|
7 | #include <boost/graph/graphviz.hpp>
|
---|
8 |
|
---|
9 |
|
---|
10 | using namespace boost;
|
---|
11 |
|
---|
12 | typedef float EdgeWeightType;
|
---|
13 |
|
---|
14 | typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
|
---|
15 | typedef adjacency_list < vecS, vecS, directedS,
|
---|
16 | property < vertex_name_t, std::string,
|
---|
17 | property < vertex_index_t, int,
|
---|
18 | property < vertex_color_t, boost::default_color_type,
|
---|
19 | property < vertex_distance_t, float,
|
---|
20 | property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
|
---|
21 |
|
---|
22 | property < edge_capacity_t, EdgeWeightType,
|
---|
23 | property < edge_residual_capacity_t, EdgeWeightType,
|
---|
24 | property < edge_reverse_t, Traits::edge_descriptor,
|
---|
25 | property< edge_name_t, std::string> > > > > Graph;
|
---|
26 |
|
---|
27 | Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1,
|
---|
28 | Traits::vertex_descriptor &v2,
|
---|
29 | property_map < Graph, edge_reverse_t >::type &rev,
|
---|
30 | const double capacity,
|
---|
31 | Graph &g,
|
---|
32 | const double reverseCapacity= 0.0);
|
---|
33 |
|
---|
34 | int main(int, char*[])
|
---|
35 | {
|
---|
36 | // 1. Build graph.
|
---|
37 | Graph g;
|
---|
38 | property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
|
---|
39 | property_map<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g);
|
---|
40 | property_map<Graph, edge_residual_capacity_t>::type residual_capacity = get(edge_residual_capacity, g);
|
---|
41 | property_map< Graph, vertex_name_t>::type vertexNames= get( vertex_name, g);
|
---|
42 | property_map< Graph, edge_name_t>::type edgeNames= get(edge_name, g);
|
---|
43 |
|
---|
44 | // Add source and sink vertices.
|
---|
45 | Traits::vertex_descriptor source= add_vertex( g);
|
---|
46 | Traits::vertex_descriptor sink= add_vertex( g);
|
---|
47 |
|
---|
48 | // Add other in-between vertices.
|
---|
49 | Traits::vertex_descriptor v0= add_vertex( g);
|
---|
50 | Traits::vertex_descriptor v1= add_vertex( g);
|
---|
51 | Traits::vertex_descriptor v2= add_vertex( g);
|
---|
52 | Traits::vertex_descriptor v3= add_vertex( g);
|
---|
53 |
|
---|
54 | // Add edges.
|
---|
55 | AddEdge( source, v0, rev, 100.0, g, 0.0);
|
---|
56 | AddEdge( v0, v2, rev, 1.0, g, 100.0);
|
---|
57 | AddEdge( v2, sink, rev, 1.0, g, 0.0);
|
---|
58 |
|
---|
59 | AddEdge( source, v1, rev, 100.0, g, 0.0);
|
---|
60 | AddEdge( v1, v3, rev, 1.0, g, 100.0);
|
---|
61 | AddEdge( v3, sink, rev, 1.0, g, 0.0);
|
---|
62 |
|
---|
63 | // 2. Run B-K max flow.
|
---|
64 | EdgeWeightType flow = boykov_kolmogorov_max_flow(g, source, sink);
|
---|
65 |
|
---|
66 | // 3. Set labels.
|
---|
67 | vertexNames[ source]= "Source";
|
---|
68 | vertexNames[ sink]= "Sink";
|
---|
69 | vertexNames[ v0]= "V0";
|
---|
70 | vertexNames[ v1]= "V1";
|
---|
71 | vertexNames[ v2]= "V2";
|
---|
72 | vertexNames[ v3]= "V3";
|
---|
73 |
|
---|
74 | graph_traits<Graph>::vertex_iterator u_iter, u_end;
|
---|
75 | graph_traits<Graph>::out_edge_iterator ei, e_end;
|
---|
76 | for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
|
---|
77 | {
|
---|
78 | for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
|
---|
79 | {
|
---|
80 | //double usedCapacity= capacity[*ei] - residual_capacity[*ei];
|
---|
81 | std::ostringstream sstream;
|
---|
82 | //sstream<< usedCapacity<< "/"<< capacity[ *ei];
|
---|
83 | sstream<< residual_capacity[ *ei]<< "/"<< capacity[ *ei];
|
---|
84 | edgeNames[ *ei]= sstream.str();
|
---|
85 | }
|
---|
86 | }
|
---|
87 |
|
---|
88 | // 4. Output .dot file.
|
---|
89 | std::ofstream fout( "b-k_example_graph.dot");
|
---|
90 | write_graphviz( fout, g,
|
---|
91 | boost::make_label_writer( boost::get( vertex_name, g)),
|
---|
92 | boost::make_label_writer( boost::get(edge_name, g))
|
---|
93 | );
|
---|
94 | fout.close();
|
---|
95 | }
|
---|
96 |
|
---|
97 | Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1, Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type &rev, const double capacity, Graph &g, const double reverseCapacity)
|
---|
98 | {
|
---|
99 | Traits::edge_descriptor e1 = add_edge(v1, v2, g).first;
|
---|
100 | Traits::edge_descriptor e2 = add_edge(v2, v1, g).first;
|
---|
101 | put(edge_capacity, g, e1, capacity);
|
---|
102 | put(edge_capacity, g, e2, reverseCapacity);
|
---|
103 |
|
---|
104 | rev[e1] = e2;
|
---|
105 | rev[e2] = e1;
|
---|
106 | }
|
---|
107 |
|
---|