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 
18 namespace boost {
19 struct SampleGraph {
20     typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
21 
22     typedef adjacency_list < vecS, vecS, directedS, no_property,
23             property < edge_capacity_t, long,
24                 property < edge_residual_capacity_t, long,
25                     property < edge_reverse_t, Traits::edge_descriptor,
26                         property <edge_weight_t, long>
27                              >
28                         >
29                      > > Graph;
30     typedef property_map < Graph, edge_capacity_t >::type Capacity;
31     typedef property_map < Graph, edge_residual_capacity_t >::type 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     class EdgeAdder {
38     public:
EdgeAdder(Graph & g,Weight & w,Capacity & c,Reversed & rev,ResidualCapacity & residualCapacity)39         EdgeAdder(Graph & g, Weight & w, Capacity & c, Reversed & rev, ResidualCapacity & residualCapacity)
40             : m_g(g), m_w(w), m_cap(c), m_resCap(residualCapacity), m_rev(rev) {}
addEdge(vertex_descriptor v,vertex_descriptor w,long weight,long capacity)41         void addEdge(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
42             Traits::edge_descriptor e,f;
43             e = add(v, w, weight, capacity);
44             f = add(w, v, -weight, 0);
45             m_rev[e] = f;
46             m_rev[f] = e;
47         }
48     private:
add(vertex_descriptor v,vertex_descriptor w,long weight,long capacity)49         Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
50             bool b;
51             Traits::edge_descriptor e;
52             boost::tie(e, b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g);
53             if (!b) {
54               std::cerr << "Edge between " << v << " and " << w << " already exists." << std::endl;
55               std::abort();
56             }
57             m_cap[e] = capacity;
58             m_w[e] = weight;
59             return e;
60         }
61         Graph & m_g;
62         Weight & m_w;
63         Capacity & m_cap;
64         ResidualCapacity & m_resCap;
65         Reversed & m_rev;
66     };
67 
68 
getSampleGraphboost::SampleGraph69     static void getSampleGraph(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
70         size_type N(6);
71         typedef property_map < Graph, edge_reverse_t >::type Reversed;
72 
73         for(size_type i = 0; i < N; ++i){
74             add_vertex(g);
75         }
76         Capacity  capacity = get(edge_capacity, g);
77         Reversed rev = get(edge_reverse, g);
78         ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
79         Weight weight = get(edge_weight, g);
80 
81         s = 0;
82         t = 5;
83 
84         EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
85 
86         ea.addEdge(0, 1, 4 ,2);
87         ea.addEdge(0, 2, 2 ,2);
88 
89         ea.addEdge(1, 3, 2 ,2);
90         ea.addEdge(1, 4, 1 ,1);
91         ea.addEdge(2, 3, 1 ,1);
92         ea.addEdge(2, 4, 1 ,1);
93 
94         ea.addEdge(3, 5, 4 ,20);
95         ea.addEdge(4, 5, 2 ,20);
96     }
97 
getSampleGraph2boost::SampleGraph98     static void getSampleGraph2(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
99 
100         const boost::graph_traits<Graph>::vertices_size_type N(5);
101         typedef property_map < Graph, edge_reverse_t >::type Reversed;
102 
103         for(size_type i = 0; i < N; ++i){
104             add_vertex(g);
105         }
106 
107         Capacity  capacity = get(edge_capacity, g);
108         Reversed rev = get(edge_reverse, g);
109         ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
110         Weight weight = get(edge_weight, g);
111 
112         s = 0;
113         t = 4;
114 
115         EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
116 
117         ea.addEdge(0, 1, 4 ,2);
118         ea.addEdge(0, 2, 2 ,2);
119         ea.addEdge(1, 2, 2 ,2);
120         ea.addEdge(2, 3, 1 ,1);
121         ea.addEdge(2, 4, 1 ,1);
122         ea.addEdge(3, 4, 1 ,1);
123 
124 
125         ea.addEdge(1, 0, 2 ,2);
126         ea.addEdge(2, 0, 1 ,1);
127         ea.addEdge(2, 1, 5 ,2);
128         ea.addEdge(3, 2, 1 ,1);
129         ea.addEdge(4, 2, 2 ,2);
130         ea.addEdge(4, 3, 1 ,3);
131     }
132 };
133 } //boost
134 
135 #endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */
136 
137