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
17namespace boost
18{
19struct 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

source code of boost/libs/graph/test/min_cost_max_flow_utils.hpp