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 /*
11 IMPORTANT:
12 ~~~~~~~~~~
13
14 This example appears to be broken and crashes at runtime, see
15 https://github.com/boostorg/graph/issues/149
16
17 */
18
19 #include <boost/config.hpp>
20 #include <iostream>
21 #include <functional>
22 #include <string>
23
24 #include <boost/graph/adjacency_list.hpp>
25 #include <boost/graph/properties.hpp>
26
27 /*
28 Sample output:
29
30 0 --chandler--> 1 --joe--> 1
31 1 --chandler--> 0 --joe--> 0 --curly--> 2 --dick--> 3 --dick--> 3
32 2 --curly--> 1 --tom--> 4
33 3 --dick--> 1 --dick--> 1 --harry--> 4
34 4 --tom--> 2 --harry--> 3
35
36 name(0,1) = chandler
37
38 name(0,1) = chandler
39 name(0,1) = joe
40
41 */
42
43 template < class StoredEdge > struct order_by_name
44 {
45 typedef StoredEdge first_argument_type;
46 typedef StoredEdge second_argument_type;
47 typedef bool result_type;
operator ()order_by_name48 bool operator()(const StoredEdge& e1, const StoredEdge& e2) const
49 {
50 // Order by target vertex, then by name.
51 // std::pair's operator< does a nice job of implementing
52 // lexicographical compare on tuples.
53 return std::make_pair(e1.get_target(), boost::get(boost::edge_name, e1))
54 < std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
55 }
56 };
57
58 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
59 struct ordered_set_by_nameS
60 {
61 };
62 namespace boost
63 {
64 template < class ValueType >
65 struct container_gen< ordered_set_by_nameS, ValueType >
66 {
67 typedef std::multiset< ValueType, order_by_name< ValueType > > type;
68 };
69 }
70 #else
71 struct ordered_set_by_nameS
72 {
73 template < class T > struct bind_
74 {
75 typedef std::multiset< T, order_by_name< T > > type;
76 };
77 };
78 namespace boost
79 {
80 template <> struct container_selector< ordered_set_by_nameS >
81 {
82 typedef ordered_set_by_nameS type;
83 };
84 }
85 #endif
86
87 namespace boost
88 {
89 template <> struct parallel_edge_traits< ordered_set_by_nameS >
90 {
91 typedef allow_parallel_edge_tag type;
92 };
93 }
94
main()95 int main()
96 {
97 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
98 std::cout << "This program requires partial specialization" << std::endl;
99 #else
100 using namespace boost;
101 typedef property< edge_name_t, std::string > EdgeProperty;
102 typedef adjacency_list< ordered_set_by_nameS, vecS, undirectedS,
103 no_property, EdgeProperty >
104 graph_type;
105 graph_type g;
106
107 add_edge(0, 1, EdgeProperty("joe"), g);
108 add_edge(1, 2, EdgeProperty("curly"), g);
109 add_edge(1, 3, EdgeProperty("dick"), g);
110 add_edge(1, 3, EdgeProperty("dick"), g);
111 add_edge(2, 4, EdgeProperty("tom"), g);
112 add_edge(3, 4, EdgeProperty("harry"), g);
113 add_edge(0, 1, EdgeProperty("chandler"), g);
114
115 property_map< graph_type, vertex_index_t >::type id = get(vertex_index, g);
116 property_map< graph_type, edge_name_t >::type name = get(edge_name, g);
117
118 graph_traits< graph_type >::vertex_iterator i, end;
119 graph_traits< graph_type >::out_edge_iterator ei, edge_end;
120 for (boost::tie(i, end) = vertices(g); i != end; ++i)
121 {
122 std::cout << id[*i] << " ";
123 for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
124 std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)]
125 << " ";
126 std::cout << std::endl;
127 }
128 std::cout << std::endl;
129
130 bool found;
131 typedef graph_traits< graph_type > Traits;
132 Traits::edge_descriptor e;
133 Traits::out_edge_iterator e_first, e_last;
134
135 boost::tie(e, found) = edge(0, 1, g);
136 if (found)
137 std::cout << "name(0,1) = " << name[e] << std::endl;
138 else
139 std::cout << "not found" << std::endl;
140 std::cout << std::endl;
141
142 boost::tie(e_first, e_last) = edge_range(0, 1, g);
143 while (e_first != e_last)
144 std::cout << "name(0,1) = " << name[*e_first++] << std::endl;
145 #endif
146 return 0;
147 }
148