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 {
operator ()order_by_name37 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
main()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 boost::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 boost::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 }
124