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: EdgeAdder(Graph & g,Weight & w,Capacity & c,Reversed & rev,ResidualCapacity &)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 } addEdge(vertex_descriptor v,vertex_descriptor w,long weight,long capacity)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(w, v, -weight, 0); 53 m_rev[e] = f; 54 m_rev[f] = e; 55 } 56 57 private: add(vertex_descriptor v,vertex_descriptor w,long weight,long capacity)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(e, 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 getSampleGraphboost::SampleGraph80 static void getSampleGraph( 81 Graph& g, vertex_descriptor& s, vertex_descriptor& t) 82 { 83 Capacity capacity = get(edge_capacity, g); 84 Reversed rev = get(edge_reverse, g); 85 ResidualCapacity residual_capacity = get(edge_residual_capacity, g); 86 Weight weight = get(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 > getSampleGraphboost::SampleGraph92 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 getSampleGraph2boost::SampleGraph121 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); 131 } 132 133 Capacity capacity = get(edge_capacity, g); 134 Reversed rev = get(edge_reverse, g); 135 ResidualCapacity residual_capacity = get(edge_residual_capacity, g); 136 Weight weight = get(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(0, 1, 4, 2); 145 ea.addEdge(0, 2, 2, 2); 146 ea.addEdge(1, 2, 2, 2); 147 ea.addEdge(2, 3, 1, 1); 148 ea.addEdge(2, 4, 1, 1); 149 ea.addEdge(3, 4, 1, 1); 150 151 ea.addEdge(1, 0, 2, 2); 152 ea.addEdge(2, 0, 1, 1); 153 ea.addEdge(2, 1, 5, 2); 154 ea.addEdge(3, 2, 1, 1); 155 ea.addEdge(4, 2, 2, 2); 156 ea.addEdge(4, 3, 1, 3); 157 } 158 }; 159 } // boost 160 161 #endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */ 162