|
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 * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved. |
|
12 */ |
|
13 |
|
14 #include <boost/config.hpp> |
|
15 #include <iostream> |
|
16 #include <vector> |
|
17 #include <utility> |
|
18 #include <algorithm> |
|
19 #include <boost/graph/adjacency_list.hpp> |
|
20 |
|
21 #ifdef __SYMBIAN32__ |
|
22 #include "std_log_result.h" |
|
23 #define LOG_FILENAME_LINE __FILE__, __LINE__ |
|
24 #endif |
|
25 |
|
26 |
|
27 |
|
28 using namespace boost; |
|
29 using namespace std; |
|
30 |
|
31 typedef property<vertex_color_t, default_color_type, |
|
32 property<vertex_distance_t,int, |
|
33 property<vertex_degree_t,int, |
|
34 property<vertex_in_degree_t, int, |
|
35 property<vertex_out_degree_t,int> > > > > VertexProperty; |
|
36 typedef property<edge_weight_t,int> EdgeProperty; |
|
37 typedef adjacency_list<vecS, vecS, bidirectionalS, |
|
38 VertexProperty, EdgeProperty> Graph; |
|
39 |
|
40 template <class Graph> |
|
41 void print(Graph& g) { |
|
42 typename Graph::vertex_iterator i, end; |
|
43 typename Graph::out_edge_iterator ei, edge_end; |
|
44 for(boost::tie(i,end) = vertices(g); i != end; ++i) { |
|
45 cout << *i << " --> "; |
|
46 for (boost::tie(ei,edge_end) = out_edges(*i, g); ei != edge_end; ++ei) |
|
47 cout << target(*ei, g) << " "; |
|
48 cout << endl; |
|
49 } |
|
50 } |
|
51 |
|
52 std::size_t myrand(std::size_t N) { |
|
53 std::size_t ret = rand() % N; |
|
54 // cout << "N = " << N << " rand = " << ret << endl; |
|
55 return ret; |
|
56 } |
|
57 |
|
58 template <class Graph> |
|
59 bool check_edge(Graph& g, std::size_t a, std::size_t b) { |
|
60 typedef typename Graph::vertex_descriptor Vertex; |
|
61 typename Graph::adjacency_iterator vi, viend, found; |
|
62 boost::tie(vi, viend) = adjacent_vertices(vertex(a,g), g); |
|
63 |
|
64 found = find(vi, viend, vertex(b, g)); |
|
65 if ( found == viend ) |
|
66 return false; |
|
67 |
|
68 return true; |
|
69 } |
|
70 |
|
71 int main(int, char*[]) |
|
72 { |
|
73 std::size_t N = 5; |
|
74 |
|
75 Graph g(N); |
|
76 int i; |
|
77 |
|
78 bool is_failed = false; |
|
79 |
|
80 for (i=0; i<6; ++i) { |
|
81 std::size_t a = myrand(N), b = myrand(N); |
|
82 while ( a == b ) b = myrand(N); |
|
83 cout << "edge edge (" << a << "," << b <<")" << endl; |
|
84 //add edges |
|
85 add_edge(a, b, g); |
|
86 is_failed = is_failed || (! check_edge(g, a, b) ); |
|
87 } |
|
88 |
|
89 if ( is_failed ) |
|
90 cerr << " Failed."<< endl; |
|
91 else |
|
92 cerr << " Passed."<< endl; |
|
93 |
|
94 print(g); |
|
95 |
|
96 //remove_edge |
|
97 for (i = 0; i<2; ++i) { |
|
98 std::size_t a = myrand(N), b = myrand(N); |
|
99 while ( a == b ) b = myrand(N); |
|
100 cout << "remove edge (" << a << "," << b <<")" << endl; |
|
101 remove_edge(a, b, g); |
|
102 is_failed = is_failed || check_edge(g, a, b); |
|
103 } |
|
104 if ( is_failed ) |
|
105 cerr << " Failed."<< endl; |
|
106 else |
|
107 cerr << " Passed."<< endl; |
|
108 |
|
109 print(g); |
|
110 |
|
111 //add_vertex |
|
112 is_failed = false; |
|
113 std::size_t old_N = N; |
|
114 std::size_t vid = add_vertex(g); |
|
115 std::size_t vidp1 = add_vertex(g); |
|
116 |
|
117 N = num_vertices(g); |
|
118 if ( (N - 2) != old_N ) |
|
119 cerr << " Failed."<< endl; |
|
120 else |
|
121 cerr << " Passed."<< endl; |
|
122 |
|
123 is_failed = false; |
|
124 for (i=0; i<2; ++i) { |
|
125 std::size_t a = myrand(N), b = myrand(N); |
|
126 while ( a == vid ) a = myrand(N); |
|
127 while ( b == vidp1 ) b = myrand(N); |
|
128 cout << "add edge (" << vid << "," << a <<")" << endl; |
|
129 cout << "add edge (" << vid << "," << vidp1 <<")" << endl; |
|
130 add_edge(vid, a, g); |
|
131 add_edge(b, vidp1, g); |
|
132 is_failed = is_failed || ! check_edge(g, vid, a); |
|
133 is_failed = is_failed || ! check_edge(g, b, vidp1); |
|
134 } |
|
135 if ( is_failed ) |
|
136 cerr << " Failed."<< endl; |
|
137 else |
|
138 cerr << " Passed."<< endl; |
|
139 print(g); |
|
140 |
|
141 // clear_vertex |
|
142 std::size_t c = myrand(N); |
|
143 is_failed = false; |
|
144 clear_vertex(c, g); |
|
145 |
|
146 if ( out_degree(c, g) != 0 ) |
|
147 is_failed = true; |
|
148 |
|
149 cout << "Removing vertex " << c << endl; |
|
150 remove_vertex(c, g); |
|
151 |
|
152 old_N = N; |
|
153 N = num_vertices(g); |
|
154 |
|
155 if ( (N + 1) != old_N ) |
|
156 is_failed = true; |
|
157 |
|
158 if ( is_failed ) |
|
159 cerr << " Failed."<< endl; |
|
160 else |
|
161 cerr << " Passed."<< endl; |
|
162 |
|
163 print(g); |
|
164 |
|
165 #ifdef __SYMBIAN32__ |
|
166 |
|
167 std_log(LOG_FILENAME_LINE,"[End Test Case ]"); |
|
168 testResultXml("graph"); |
|
169 close_log_file(); |
|
170 #endif |
|
171 return 0; |
|
172 } |