ceph/src/boost/libs/graph/test/bundled_properties.cpp

   1 // Boost Graph library
   2
   3 //  Copyright Douglas Gregor 2004. Use, modification and
   4 //  distribution is subject to the Boost Software License, Version
   5 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 //  http://www.boost.org/LICENSE_1_0.txt)
   7
   8 #include <boost/test/minimal.hpp>
   9 #include <boost/graph/adjacency_list.hpp>
  10 #include <boost/graph/adjacency_matrix.hpp>
  11 #include <boost/graph/filtered_graph.hpp>
  12 #include <boost/graph/subgraph.hpp>
  13 #include <string>
  14 #include <vector>
  15 #include <boost/graph/adjacency_list_io.hpp>
  16 #include <sstream>
  17 #include <boost/graph/iteration_macros.hpp>
  18 #include <algorithm>
  19 #include <iterator>
  20
  21 using namespace std;
  22 using namespace boost;
  23
  24 struct City
  25 {
  26   City() {}
  27   City(const std::string& name, int pop, int zipcode) : name(name), population(pop)
  28   {
  29     zipcodes.push_back(zipcode);
  30   }
  31
  32   string name;
  33   int population;
  34   vector<int> zipcodes;
  35 };
  36
  37 std::ostream& operator<<(std::ostream& out, const City& city)
  38 {
  39   out << city.name << ' ' << city.population << ' ';
  40   copy(city.zipcodes.begin(), city.zipcodes.end(),
  41        ostream_iterator<int>(out, " "));
  42   out << -1;
  43   return out;
  44 }
  45
  46 std::istream& operator>>(std::istream& in, City& city)
  47 {
  48   if (in >> city.name >> city.population) {
  49     int zip;
  50     city.zipcodes.clear();
  51     while (in >> zip && zip != -1)
  52       city.zipcodes.push_back(zip);
  53   }
  54   return in;
  55 }
  56
  57 bool operator==(const City& c1, const City& c2)
  58 {
  59   return (c1.name == c2.name && c1.population == c2.population
  60           && c1.zipcodes == c2.zipcodes);
  61 }
  62
  63 struct Highway
  64 {
  65   Highway() {}
  66   Highway(const string& name, double miles, int speed_limit = 65, int lanes = 4, bool divided = true)
  67     : name(name), miles(miles), speed_limit(speed_limit), lanes(lanes), divided(divided) {}
  68
  69   string name;
  70   double miles;
  71   int speed_limit;
  72   int lanes;
  73   bool divided;
  74 };
  75
  76 std::ostream& operator<<(std::ostream& out, const Highway& highway)
  77 {
  78   return out << highway.name << ' ' << highway.miles << ' ' << highway.miles
  79              << ' ' << highway.speed_limit << ' ' << highway.lanes
  80              << ' ' << highway.divided;
  81 }
  82
  83 std::istream& operator>>(std::istream& in, Highway& highway)
  84 {
  85   return in >> highway.name >> highway.miles >> highway.miles
  86             >> highway.speed_limit  >> highway.lanes
  87             >> highway.divided;
  88 }
  89
  90 bool operator==(const Highway& h1, const Highway& h2)
  91 {
  92   return (h1.name == h2.name && h1.miles == h2.miles
  93           && h1.speed_limit == h2.speed_limit && h1.lanes == h2.lanes
  94           && h1.divided == h2.divided);
  95 }
  96
  97 template<bool> struct truth {};
  98
  99 template<typename Map, typename VertexIterator, typename Bundle>
 100 typename boost::graph_traits<Map>::vertex_descriptor
 101 do_add_vertex(Map& map, VertexIterator, const Bundle& bundle, truth<true>)
 102 {
 103   return add_vertex(bundle, map);
 104 }
 105
 106 template<typename Map, typename VertexIterator, typename Bundle>
 107 typename boost::graph_traits<Map>::vertex_descriptor
 108 do_add_vertex(Map& map, VertexIterator& vi, const Bundle& bundle, truth<false>)
 109 {
 110   get(boost::vertex_bundle, map)[*vi] = bundle;
 111   return *vi++;
 112 }
 113
 114 template<class EL, class VL, class D, class VP, class EP, class GP>
 115 void test_io(adjacency_list<EL,VL,D,VP,EP,GP>& map, int)
 116 {
 117   typedef adjacency_list<EL,VL,D,VP,EP,GP> Map;
 118
 119   ostringstream out;
 120   cout << write(map);
 121   out << write(map);
 122
 123   istringstream in(out.str());
 124   adjacency_list<EL,VL,D,VP,EP,GP> map2;
 125   in >> read(map2);
 126   typename graph_traits<adjacency_list<EL,VL,D,VP,EP,GP> >::vertex_iterator
 127     v2 = vertices(map2).first;
 128   BGL_FORALL_VERTICES_T(v, map, Map) {
 129     BOOST_CHECK(map[v] == map2[*v2]);
 130     typename graph_traits<adjacency_list<EL,VL,D,VP,EP,GP> >::out_edge_iterator
 131       e2 = out_edges(*v2, map2).first;
 132     BGL_FORALL_OUTEDGES_T(v, e, map, Map) {
 133       BOOST_CHECK(map[e] == map[*e2]);
 134       ++e2;
 135     }
 136     ++v2;
 137   }
 138 }
 139
 140 template<typename Map>
 141 void test_io(const Map&, long)
 142 {
 143   // Nothing to test
 144 }
 145
 146 template<typename Map, bool CanAddVertex>
 147 void test_bundled_properties(Map*, truth<CanAddVertex> can_add_vertex)
 148 {
 149   typedef typename boost::graph_traits<Map>::vertex_iterator   vertex_iterator;
 150   typedef typename boost::graph_traits<Map>::vertex_descriptor vertex_descriptor;
 151   typedef typename boost::graph_traits<Map>::edge_descriptor   edge_descriptor;
 152
 153   Map map(CanAddVertex? 2 : 3);
 154
 155   vertex_iterator vi = vertices(map).first;
 156   vertex_descriptor v = *vi;
 157   map[v].name = "Troy";
 158   map[v].population = 49170;
 159   map[v].zipcodes.push_back(12180);
 160
 161   ++vi;
 162   vertex_descriptor u = *vi++;
 163   map[u].name = "Albany";
 164   map[u].population = 95658;
 165   map[u].zipcodes.push_back(12201);
 166
 167   // Try adding a vertex with a property value
 168   vertex_descriptor bloomington = do_add_vertex(map, vi, City("Bloomington", 39000, 47401),
 169                                                 can_add_vertex);
 170   BOOST_CHECK(get(boost::vertex_bundle, map)[bloomington].zipcodes[0] == 47401);
 171
 172   edge_descriptor e = add_edge(v, u, map).first;
 173   map[e].name = "I-87";
 174   map[e].miles = 10;
 175   map[e].speed_limit = 65;
 176   map[e].lanes = 4;
 177   map[e].divided = true;
 178
 179   edge_descriptor our_trip = add_edge(v, bloomington, Highway("Long", 1000), map).first;
 180   BOOST_CHECK(get(boost::edge_bundle, map, our_trip).miles == 1000);
 181
 182   BOOST_CHECK(get(get(&City::name, map), v) == "Troy");
 183   BOOST_CHECK(get(get(&Highway::name, map), e) == "I-87");
 184   BOOST_CHECK(get(&City::name, map, u) == "Albany");
 185   BOOST_CHECK(get(&Highway::name, map, e) == "I-87");
 186   put(&City::population, map, v, 49168);
 187   BOOST_CHECK(get(&City::population, map)[v] == 49168);
 188
 189   boost::filtered_graph<Map, boost::keep_all> fmap(map, boost::keep_all());
 190   BOOST_CHECK(get(boost::edge_bundle, map, our_trip).miles == 1000);
 191
 192   BOOST_CHECK(get(get(&City::name, fmap), v) == "Troy");
 193   BOOST_CHECK(get(get(&Highway::name, fmap), e) == "I-87");
 194   BOOST_CHECK(get(&City::name, fmap, u) == "Albany");
 195   BOOST_CHECK(get(&Highway::name, fmap, e) == "I-87");
 196   put(&City::population, fmap, v, 49169);
 197   BOOST_CHECK(get(&City::population, fmap)[v] == 49169);
 198
 199   test_io(map, 0);
 200 }
 201
 202 void test_subgraph_bundled_properties()
 203 {
 204   typedef boost::subgraph<
 205             boost::adjacency_list<boost::vecS, boost::vecS,
 206                                   boost::bidirectionalS, City,
 207                                   boost::property<boost::edge_index_t, int,
 208                                                   Highway> > > SubMap;
 209   typedef boost::graph_traits<SubMap>::vertex_descriptor Vertex;
 210   typedef boost::graph_traits<SubMap>::vertex_iterator vertex_iterator;
 211
 212   SubMap map(3);
 213   vertex_iterator vi = vertices(map).first;
 214   Vertex troy = *vi++;
 215   map[troy].name = "Troy";
 216   map[*vi++].name = "Bloomington";
 217   map[*vi++].name = "Endicott";
 218
 219   SubMap& g1 = map.create_subgraph();
 220   Vertex troy1 = add_vertex(*vertices(map).first, g1);
 221   BOOST_CHECK(map[troy1].name == g1[troy1].name);
 222 }
 223
 224 int test_main(int, char*[])
 225 {
 226   typedef boost::adjacency_list<
 227     boost::listS, boost::vecS, boost::bidirectionalS,
 228     City, Highway> Map1;
 229   typedef boost::adjacency_matrix<boost::directedS,
 230     City, Highway> Map2;
 231
 232   test_bundled_properties(static_cast<Map1*>(0), truth<true>());
 233   test_bundled_properties(static_cast<Map2*>(0), truth<false>());
 234   test_subgraph_bundled_properties();
 235   return 0;
 236 }