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 <string>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/graph_utility.hpp>
15
16 using namespace boost;
17
18 // Predicate Function for use in remove if
19 template < class NamePropertyMap > struct name_equals_predicate
20 {
name_equals_predicatename_equals_predicate21 name_equals_predicate(const std::string& x, NamePropertyMap name)
22 : m_str(x), m_name(name)
23 {
24 }
25
operator ()name_equals_predicate26 template < class Edge > bool operator()(const Edge& e) const
27 {
28 return m_str == m_name[e];
29 }
30 std::string m_str;
31 NamePropertyMap m_name;
32 };
33 // helper creation function
34 template < class NamePropertyMap >
name_equals(const std::string & str,NamePropertyMap name)35 inline name_equals_predicate< NamePropertyMap > name_equals(
36 const std::string& str, NamePropertyMap name)
37 {
38 return name_equals_predicate< NamePropertyMap >(str, name);
39 }
40
modify_demo(MutableGraph & g)41 template < class MutableGraph > void modify_demo(MutableGraph& g)
42 {
43 typedef graph_traits< MutableGraph > GraphTraits;
44 typedef typename GraphTraits::vertices_size_type size_type;
45 typedef typename GraphTraits::edge_descriptor edge_descriptor;
46 size_type n = 0;
47 typename GraphTraits::edges_size_type m = 0;
48 typename GraphTraits::vertex_descriptor u, v, w;
49 edge_descriptor e, e1, e2;
50 typename property_map< MutableGraph, edge_name_t >::type name_map
51 = get(edge_name, g);
52 bool added;
53 typename GraphTraits::vertex_iterator vi, vi_end;
54
55 {
56 v = add_vertex(g);
57
58 assert(num_vertices(g) == n + 1);
59 assert(size_type(vertices(g).second - vertices(g).first) == n + 1);
60 assert(v == *std::find(vertices(g).first, vertices(g).second, v));
61 }
62 {
63 remove_vertex(v, g);
64
65 assert(num_vertices(g) == n);
66 assert(size_type(vertices(g).second - vertices(g).first) == n);
67 // v is no longer a valid vertex descriptor
68 }
69 {
70 u = add_vertex(g);
71 v = add_vertex(g);
72
73 std::pair< edge_descriptor, bool > p = add_edge(u, v, g);
74
75 assert(num_edges(g) == m + 1);
76 assert(p.second == true); // edge should have been added
77 assert(source(p.first, g) == u);
78 assert(target(p.first, g) == v);
79 assert(p.first
80 == *std::find(
81 out_edges(u, g).first, out_edges(u, g).second, p.first));
82 assert(p.first
83 == *std::find(
84 in_edges(v, g).first, in_edges(v, g).second, p.first));
85 }
86 {
87 // use tie() for convenience, avoid using the std::pair
88
89 u = add_vertex(g);
90 v = add_vertex(g);
91
92 boost::tie(e, added) = add_edge(u, v, g);
93
94 assert(num_edges(g) == m + 2);
95 assert(added == true); // edge should have been added
96 assert(source(e, g) == u);
97 assert(target(e, g) == v);
98 assert(
99 e == *std::find(out_edges(u, g).first, out_edges(u, g).second, e));
100 assert(e == *std::find(in_edges(v, g).first, in_edges(v, g).second, e));
101 }
102 {
103 add_edge(u, v, g); // add a parallel edge
104
105 remove_edge(u, v, g);
106
107 assert(num_edges(g) == m + 1);
108 bool exists;
109 boost::tie(e, exists) = edge(u, v, g);
110 assert(exists == false);
111 assert(out_degree(u, g) == 0);
112 assert(in_degree(v, g) == 0);
113 }
114 {
115 e = *edges(g).first;
116 boost::tie(u, v) = incident(e, g);
117
118 remove_edge(e, g);
119
120 assert(num_edges(g) == m);
121 assert(out_degree(u, g) == 0);
122 assert(in_degree(v, g) == 0);
123 }
124 {
125 add_edge(u, v, g);
126
127 typename GraphTraits::out_edge_iterator iter, iter_end;
128 boost::tie(iter, iter_end) = out_edges(u, g);
129
130 remove_edge(iter, g);
131
132 assert(num_edges(g) == m);
133 assert(out_degree(u, g) == 0);
134 assert(in_degree(v, g) == 0);
135 }
136 {
137 w = add_vertex(g);
138 boost::tie(e1, added) = add_edge(u, v, g);
139 boost::tie(e2, added) = add_edge(v, w, g);
140 name_map[e1] = "I-5";
141 name_map[e2] = "Route 66";
142
143 typename GraphTraits::out_edge_iterator iter, iter_end;
144 boost::tie(iter, iter_end) = out_edges(u, g);
145
146 remove_edge_if(name_equals("Route 66", name_map), g);
147
148 assert(num_edges(g) == m + 1);
149
150 remove_edge_if(name_equals("I-5", name_map), g);
151
152 assert(num_edges(g) == m);
153 assert(out_degree(u, g) == 0);
154 assert(out_degree(v, g) == 0);
155 assert(in_degree(v, g) == 0);
156 assert(in_degree(w, g) == 0);
157 }
158 {
159 boost::tie(e1, added) = add_edge(u, v, g);
160 boost::tie(e2, added) = add_edge(u, w, g);
161 name_map[e1] = "foo";
162 name_map[e2] = "foo";
163
164 remove_out_edge_if(u, name_equals("foo", name_map), g);
165
166 assert(num_edges(g) == m);
167 assert(out_degree(u, g) == 0);
168 }
169 {
170 boost::tie(e1, added) = add_edge(u, v, g);
171 boost::tie(e2, added) = add_edge(w, v, g);
172 name_map[e1] = "bar";
173 name_map[e2] = "bar";
174
175 remove_in_edge_if(v, name_equals("bar", name_map), g);
176
177 assert(num_edges(g) == m);
178 assert(in_degree(v, g) == 0);
179 }
180 {
181 add_edge(u, v, g);
182 add_edge(u, w, g);
183 add_edge(u, v, g);
184 add_edge(v, u, g);
185
186 clear_vertex(u, g);
187
188 assert(out_degree(u, g) == 0);
189
190 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
191 {
192 typename GraphTraits::adjacency_iterator ai, ai_end;
193 for (boost::tie(ai, ai_end) = adjacent_vertices(*vi, g);
194 ai != ai_end; ++ai)
195 assert(*ai != u);
196 }
197 }
198 }
199
main()200 int main()
201 {
202 adjacency_list< listS, vecS, bidirectionalS, no_property,
203 property< edge_name_t, std::string > >
204 g;
205
206 modify_demo(g);
207 return 0;
208 }
209