12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/config.hpp>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/property_map/property_map.hpp>
- using namespace std;
- using namespace boost;
- /*
- Exterior Decorator Basics
- An exterior decorator is a way of associating properties with the
- vertices or edges of a graph. The "exterior" part means that the
- properties are not stored inside the graph object (see
- internal_decorator_basics.cc). Instead they are stored
- separately, and passed as an extra argument to any
- algorithm they are needed in. There are several standard
- decorator types such a color and weight that are used
- in the GGCL algorithms.
- The main responsibility of a decorator is to provide an operator[]
- that maps a vertex (or vertex ID) to the property value for that
- vertex. It just so happens that a normal array provides this. In
- addition, a decorator must provide access to the property type
- through the decorator_traits class. For convenience, GGCL
- already defines a decorator_triats class for pointer and
- array types.
- Sample Output
- Jeremy owes Rich some money
- Jeremy owes Andrew some money
- Jeremy owes Jeff some money
- Jeremy owes Kinis some money
- Andrew owes Jeremy some money
- Andrew owes Kinis some money
- Jeff owes Jeremy some money
- Jeff owes Rich some money
- Jeff owes Kinis some money
- Kinis owes Jeremy some money
- Kinis owes Rich some money
- */
- template <class EdgeIter, class Graph, class Name>
- void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G,
- Name name)
- {
- while (first != last) {
- cout << name[source(*first,G)] << " owes "
- << name[target(*first,G)] << " some money" << endl;
- ++first;
- }
- }
- int
- main(int, char*[])
- {
- /* The property will be "names" attached to the vertices */
- string* names = new string[5];
- names[0] = "Jeremy";
- names[1] = "Rich";
- names[2] = "Andrew";
- names[3] = "Jeff";
- names[4] = "Kinis";
-
- typedef adjacency_list<> MyGraphType;
- typedef pair<int,int> Pair;
- Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3), Pair(0,4),
- Pair(2,0), Pair(3,0), Pair(2,4), Pair(3,1),
- Pair(3,4), Pair(4,0), Pair(4,1) };
- MyGraphType G(5);
- for (int i=0; i<11; ++i)
- add_edge(edge_array[i].first, edge_array[i].second, G);
- who_owes_who(edges(G).first, edges(G).second, G, names);
- return 0;
- }
|