1 | //======================================================================= |
2 | // Copyright 2013 University of Warsaw. |
3 | // Authors: Piotr Wygocki |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #ifndef SAMPLE_GRAPH_UNDIRECTED_HPP |
11 | #define SAMPLE_GRAPH_UNDIRECTED_HPP |
12 | |
13 | #include <iostream> |
14 | #include <cstdlib> |
15 | #include <boost/graph/adjacency_list.hpp> |
16 | |
17 | namespace boost |
18 | { |
19 | struct SampleGraph |
20 | { |
21 | typedef adjacency_list_traits< vecS, vecS, directedS > Traits; |
22 | |
23 | typedef adjacency_list< vecS, vecS, directedS, no_property, |
24 | property< edge_capacity_t, long, |
25 | property< edge_residual_capacity_t, long, |
26 | property< edge_reverse_t, Traits::edge_descriptor, |
27 | property< edge_weight_t, long > > > > > |
28 | Graph; |
29 | typedef property_map< Graph, edge_capacity_t >::type Capacity; |
30 | typedef property_map< Graph, edge_residual_capacity_t >::type |
31 | ResidualCapacity; |
32 | typedef property_map< Graph, edge_weight_t >::type Weight; |
33 | typedef property_map< Graph, edge_reverse_t >::type Reversed; |
34 | typedef boost::graph_traits< Graph >::vertices_size_type size_type; |
35 | typedef Traits::vertex_descriptor vertex_descriptor; |
36 | |
37 | template < class Graph, class Weight, class Capacity, class Reversed, |
38 | class ResidualCapacity > |
39 | class EdgeAdder |
40 | { |
41 | public: |
42 | EdgeAdder( |
43 | Graph& g, Weight& w, Capacity& c, Reversed& rev, ResidualCapacity&) |
44 | : m_g(g), m_w(w), m_cap(c), m_rev(rev) |
45 | { |
46 | } |
47 | void addEdge(vertex_descriptor v, vertex_descriptor w, long weight, |
48 | long capacity) |
49 | { |
50 | Traits::edge_descriptor e, f; |
51 | e = add(v, w, weight, capacity); |
52 | f = add(v: w, w: v, weight: -weight, capacity: 0); |
53 | m_rev[e] = f; |
54 | m_rev[f] = e; |
55 | } |
56 | |
57 | private: |
58 | Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w, |
59 | long weight, long capacity) |
60 | { |
61 | bool b; |
62 | Traits::edge_descriptor e; |
63 | boost::tie(t0&: e, t1&: b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g); |
64 | if (!b) |
65 | { |
66 | std::cerr << "Edge between " << v << " and " << w |
67 | << " already exists." << std::endl; |
68 | std::abort(); |
69 | } |
70 | m_cap[e] = capacity; |
71 | m_w[e] = weight; |
72 | return e; |
73 | } |
74 | Graph& m_g; |
75 | Weight& m_w; |
76 | Capacity& m_cap; |
77 | Reversed& m_rev; |
78 | }; |
79 | |
80 | static void getSampleGraph( |
81 | Graph& g, vertex_descriptor& s, vertex_descriptor& t) |
82 | { |
83 | Capacity capacity = get(p: edge_capacity, g); |
84 | Reversed rev = get(p: edge_reverse, g); |
85 | ResidualCapacity residual_capacity = get(p: edge_residual_capacity, g); |
86 | Weight weight = get(p: edge_weight, g); |
87 | getSampleGraph(g, s, t, capacity, residual_capacity, weight, rev); |
88 | } |
89 | |
90 | template < class Graph, class Weight, class Capacity, class Reversed, |
91 | class ResidualCapacity > |
92 | static void getSampleGraph(Graph& g, vertex_descriptor& s, |
93 | vertex_descriptor& t, Capacity capacity, |
94 | ResidualCapacity residual_capacity, Weight weight, Reversed rev) |
95 | { |
96 | size_type N(6); |
97 | |
98 | for (size_type i = 0; i < N; ++i) |
99 | { |
100 | add_vertex(g); |
101 | } |
102 | |
103 | s = 0; |
104 | t = 5; |
105 | |
106 | EdgeAdder< Graph, Weight, Capacity, Reversed, ResidualCapacity > ea( |
107 | g, weight, capacity, rev, residual_capacity); |
108 | |
109 | ea.addEdge(0, 1, 4, 2); |
110 | ea.addEdge(0, 2, 2, 2); |
111 | |
112 | ea.addEdge(1, 3, 2, 2); |
113 | ea.addEdge(1, 4, 1, 1); |
114 | ea.addEdge(2, 3, 1, 1); |
115 | ea.addEdge(2, 4, 1, 1); |
116 | |
117 | ea.addEdge(3, 5, 4, 20); |
118 | ea.addEdge(4, 5, 2, 20); |
119 | } |
120 | |
121 | static void getSampleGraph2( |
122 | Graph& g, vertex_descriptor& s, vertex_descriptor& t) |
123 | { |
124 | |
125 | const boost::graph_traits< Graph >::vertices_size_type N(5); |
126 | typedef property_map< Graph, edge_reverse_t >::type Reversed; |
127 | |
128 | for (size_type i = 0; i < N; ++i) |
129 | { |
130 | add_vertex(g_&: g); |
131 | } |
132 | |
133 | Capacity capacity = get(p: edge_capacity, g); |
134 | Reversed rev = get(p: edge_reverse, g); |
135 | ResidualCapacity residual_capacity = get(p: edge_residual_capacity, g); |
136 | Weight weight = get(p: edge_weight, g); |
137 | |
138 | s = 0; |
139 | t = 4; |
140 | |
141 | EdgeAdder< Graph, Weight, Capacity, Reversed, ResidualCapacity > ea( |
142 | g, weight, capacity, rev, residual_capacity); |
143 | |
144 | ea.addEdge(v: 0, w: 1, weight: 4, capacity: 2); |
145 | ea.addEdge(v: 0, w: 2, weight: 2, capacity: 2); |
146 | ea.addEdge(v: 1, w: 2, weight: 2, capacity: 2); |
147 | ea.addEdge(v: 2, w: 3, weight: 1, capacity: 1); |
148 | ea.addEdge(v: 2, w: 4, weight: 1, capacity: 1); |
149 | ea.addEdge(v: 3, w: 4, weight: 1, capacity: 1); |
150 | |
151 | ea.addEdge(v: 1, w: 0, weight: 2, capacity: 2); |
152 | ea.addEdge(v: 2, w: 0, weight: 1, capacity: 1); |
153 | ea.addEdge(v: 2, w: 1, weight: 5, capacity: 2); |
154 | ea.addEdge(v: 3, w: 2, weight: 1, capacity: 1); |
155 | ea.addEdge(v: 4, w: 2, weight: 2, capacity: 2); |
156 | ea.addEdge(v: 4, w: 3, weight: 1, capacity: 3); |
157 | } |
158 | }; |
159 | } // boost |
160 | |
161 | #endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */ |
162 | |