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