ceph/src/boost/libs/graph/example/exterior_property_map.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
  10 #include <boost/config.hpp>
  11 #include <iostream>
  12 #include <algorithm>
  13 #include <string>
  14 #include <boost/graph/adjacency_list.hpp>
  15 #include <boost/property_map/property_map.hpp>
  16
  17 using namespace std;
  18 using namespace boost;
  19
  20 /*
  21   Exterior Decorator Basics
  22
  23   An exterior decorator is a way of associating properties with the
  24   vertices or edges of a graph. The "exterior" part means that the
  25   properties are not stored inside the graph object (see
  26   internal_decorator_basics.cc). Instead they are stored
  27   separately, and passed as an extra argument to any
  28   algorithm they are needed in. There are several standard
  29   decorator types such a color and weight that are used
  30   in the GGCL algorithms.
  31
  32   The main responsibility of a decorator is to provide an operator[]
  33   that maps a vertex (or vertex ID) to the property value for that
  34   vertex. It just so happens that a normal array provides this.  In
  35   addition, a decorator must provide access to the property type
  36   through the decorator_traits class. For convenience, GGCL
  37   already defines a decorator_triats class for pointer and
  38   array types.
  39
  40   Sample Output
  41
  42   Jeremy owes Rich some money
  43   Jeremy owes Andrew some money
  44   Jeremy owes Jeff some money
  45   Jeremy owes Kinis some money
  46   Andrew owes Jeremy some money
  47   Andrew owes Kinis some money
  48   Jeff owes Jeremy some money
  49   Jeff owes Rich some money
  50   Jeff owes Kinis some money
  51   Kinis owes Jeremy some money
  52   Kinis owes Rich some money
  53
  54  */
  55
  56 template <class EdgeIter, class Graph, class Name>
  57 void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G,
  58                   Name name)
  59 {
  60   while (first != last) {
  61
  62     cout << name[source(*first,G)] << " owes "
  63          << name[target(*first,G)] << " some money" << endl;
  64     ++first;
  65   }
  66 }
  67
  68 int
  69 main(int, char*[])
  70 {
  71   /* The property will be "names" attached to the vertices */
  72
  73   string* names = new string[5];
  74   names[0] = "Jeremy";
  75   names[1] = "Rich";
  76   names[2] = "Andrew";
  77   names[3] = "Jeff";
  78   names[4] = "Kinis";
  79
  80   typedef adjacency_list<> MyGraphType;
  81
  82   typedef pair<int,int> Pair;
  83   Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3), Pair(0,4),
  84                           Pair(2,0), Pair(3,0), Pair(2,4), Pair(3,1),
  85                           Pair(3,4), Pair(4,0), Pair(4,1) };
  86
  87     MyGraphType G(5);
  88     for (int i=0; i<11; ++i)
  89       add_edge(edge_array[i].first, edge_array[i].second, G);
  90
  91   who_owes_who(edges(G).first, edges(G).second, G, names);
  92
  93   return 0;
  94 }