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 >
who_owes_who(EdgeIter first,EdgeIter last,const Graph & G,Name name)57 void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G, Name name)
58 {
59 while (first != last)
60 {
61
62 cout << name[source(*first, G)] << " owes " << name[target(*first, G)]
63 << " some money" << endl;
64 ++first;
65 }
66 }
67
main(int,char * [])68 int main(int, char*[])
69 {
70 /* The property will be "names" attached to the vertices */
71
72 string* names = new string[5];
73 names[0] = "Jeremy";
74 names[1] = "Rich";
75 names[2] = "Andrew";
76 names[3] = "Jeff";
77 names[4] = "Kinis";
78
79 typedef adjacency_list<> MyGraphType;
80
81 typedef pair< int, int > Pair;
82 Pair edge_array[11] = { Pair(0, 1), Pair(0, 2), Pair(0, 3), Pair(0, 4),
83 Pair(2, 0), Pair(3, 0), Pair(2, 4), Pair(3, 1), Pair(3, 4), Pair(4, 0),
84 Pair(4, 1) };
85
86 MyGraphType G(5);
87 for (int i = 0; i < 11; ++i)
88 add_edge(edge_array[i].first, edge_array[i].second, G);
89
90 who_owes_who(edges(G).first, edges(G).second, G, names);
91
92 return 0;
93 }
94