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