Boost_1_39_0/libs/graph/example/ordered_out_edges.cpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   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 #include <boost/config.hpp>
  10 #include <iostream>
  11 #include <functional>
  12 #include <string>
  13
  14 #include <boost/graph/adjacency_list.hpp>
  15 #include <boost/graph/properties.hpp>
  16
  17 /*
  18   Sample output:
  19
  20   0  --chandler--> 1   --joe--> 1
  21   1  --chandler--> 0   --joe--> 0   --curly--> 2   --dick--> 3   --dick--> 3
  22   2  --curly--> 1   --tom--> 4
  23   3  --dick--> 1   --dick--> 1   --harry--> 4
  24   4  --tom--> 2   --harry--> 3
  25
  26   name(0,1) = chandler
  27
  28   name(0,1) = chandler
  29   name(0,1) = joe
  30
  31  */
  32
  33 template <class StoredEdge>
  34 struct order_by_name
  35   : public std::binary_function<StoredEdge,StoredEdge,bool>
  36 {
  37   bool operator()(const StoredEdge& e1, const StoredEdge& e2) const {
  38     // Order by target vertex, then by name.
  39     // std::pair's operator< does a nice job of implementing
  40     // lexicographical compare on tuples.
  41     return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
  42       < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
  43   }
  44 };
  45
  46 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  47 struct ordered_set_by_nameS { };
  48 namespace boost {
  49   template <class ValueType>
  50   struct container_gen<ordered_set_by_nameS, ValueType> {
  51     typedef std::multiset<ValueType, order_by_name<ValueType> > type;
  52   };
  53 }
  54 #else
  55 struct ordered_set_by_nameS {
  56   template <class T>
  57   struct bind_ { typedef std::multiset<T, order_by_name<T> > type; };
  58 };
  59 namespace boost {
  60   template <> struct container_selector<ordered_set_by_nameS>  {
  61     typedef ordered_set_by_nameS type;
  62   };
  63 }
  64 #endif
  65
  66 namespace boost {
  67   template <>
  68   struct parallel_edge_traits<ordered_set_by_nameS> {
  69     typedef allow_parallel_edge_tag type;
  70   };
  71 }
  72
  73 int
  74 main()
  75 {
  76 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  77   std::cout << "This program requires partial specialization" << std::endl;
  78 #else
  79   using namespace boost;
  80   typedef property<edge_name_t, std::string> EdgeProperty;
  81   typedef adjacency_list<ordered_set_by_nameS, vecS, undirectedS,
  82     no_property, EdgeProperty> graph_type;
  83   graph_type g;
  84
  85   add_edge(0, 1, EdgeProperty("joe"), g);
  86   add_edge(1, 2, EdgeProperty("curly"), g);
  87   add_edge(1, 3, EdgeProperty("dick"), g);
  88   add_edge(1, 3, EdgeProperty("dick"), g);
  89   add_edge(2, 4, EdgeProperty("tom"), g);
  90   add_edge(3, 4, EdgeProperty("harry"), g);
  91   add_edge(0, 1, EdgeProperty("chandler"), g);
  92
  93   property_map<graph_type, vertex_index_t>::type id = get(vertex_index, g);
  94   property_map<graph_type, edge_name_t>::type name = get(edge_name, g);
  95
  96   graph_traits<graph_type>::vertex_iterator i, end;
  97   graph_traits<graph_type>::out_edge_iterator ei, edge_end;
  98   for (boost::tie(i, end) = vertices(g); i != end; ++i) {
  99     std::cout << id[*i] << " ";
 100     for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
 101       std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << "  ";
 102     std::cout << std::endl;
 103   }
 104   std::cout << std::endl;
 105
 106   bool found;
 107   typedef graph_traits<graph_type> Traits;
 108   Traits::edge_descriptor e;
 109   Traits::out_edge_iterator e_first, e_last;
 110
 111   tie(e, found) = edge(0, 1, g);
 112   if (found)
 113     std::cout << "name(0,1) = " << name[e] << std::endl;
 114   else
 115     std::cout << "not found" << std::endl;
 116   std::cout << std::endl;
 117
 118   tie(e_first, e_last) = edge_range(0, 1, g);
 119   while (e_first != e_last)
 120     std::cout << "name(0,1) = " << name[*e_first++] << std::endl;
 121 #endif
 122   return 0;
 123 }