123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/config.hpp>
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <algorithm>
- #include <boost/graph/adjacency_list.hpp>
- using namespace boost;
- using namespace std;
- typedef property<vertex_color_t, default_color_type,
- property<vertex_distance_t,int,
- property<vertex_degree_t,int,
- property<vertex_in_degree_t, int,
- property<vertex_out_degree_t,int> > > > > VertexProperty;
- typedef property<edge_weight_t,int> EdgeProperty;
- typedef adjacency_list<vecS, vecS, bidirectionalS,
- VertexProperty, EdgeProperty> Graph;
- template <class Graph>
- void print(Graph& g) {
- typename Graph::vertex_iterator i, end;
- typename Graph::out_edge_iterator ei, edge_end;
- for(boost::tie(i,end) = vertices(g); i != end; ++i) {
- cout << *i << " --> ";
- for (boost::tie(ei,edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
- cout << target(*ei, g) << " ";
- cout << endl;
- }
- }
- std::size_t myrand(std::size_t N) {
- std::size_t ret = rand() % N;
- // cout << "N = " << N << " rand = " << ret << endl;
- return ret;
- }
- template <class Graph>
- bool check_edge(Graph& g, std::size_t a, std::size_t b) {
- typename Graph::adjacency_iterator vi, viend, found;
- boost::tie(vi, viend) = adjacent_vertices(vertex(a,g), g);
- found = find(vi, viend, vertex(b, g));
- if ( found == viend )
- return false;
- return true;
- }
- int main(int, char*[])
- {
- std::size_t N = 5;
- Graph g(N);
- int i;
- bool is_failed = false;
- for (i=0; i<6; ++i) {
- std::size_t a = myrand(N), b = myrand(N);
- while ( a == b ) b = myrand(N);
- cout << "edge edge (" << a << "," << b <<")" << endl;
- //add edges
- add_edge(a, b, g);
- is_failed = is_failed || (! check_edge(g, a, b) );
- }
-
- if ( is_failed )
- cerr << " Failed."<< endl;
- else
- cerr << " Passed."<< endl;
-
- print(g);
-
- //remove_edge
- for (i = 0; i<2; ++i) {
- std::size_t a = myrand(N), b = myrand(N);
- while ( a == b ) b = myrand(N);
- cout << "remove edge (" << a << "," << b <<")" << endl;
- remove_edge(a, b, g);
- is_failed = is_failed || check_edge(g, a, b);
- }
- if ( is_failed )
- cerr << " Failed."<< endl;
- else
- cerr << " Passed."<< endl;
- print(g);
-
- //add_vertex
- is_failed = false;
- std::size_t old_N = N;
- std::size_t vid = add_vertex(g);
- std::size_t vidp1 = add_vertex(g);
-
- N = num_vertices(g);
- if ( (N - 2) != old_N )
- cerr << " Failed."<< endl;
- else
- cerr << " Passed."<< endl;
-
- is_failed = false;
- for (i=0; i<2; ++i) {
- std::size_t a = myrand(N), b = myrand(N);
- while ( a == vid ) a = myrand(N);
- while ( b == vidp1 ) b = myrand(N);
- cout << "add edge (" << vid << "," << a <<")" << endl;
- cout << "add edge (" << vid << "," << vidp1 <<")" << endl;
- add_edge(vid, a, g);
- add_edge(b, vidp1, g);
- is_failed = is_failed || ! check_edge(g, vid, a);
- is_failed = is_failed || ! check_edge(g, b, vidp1);
- }
- if ( is_failed )
- cerr << " Failed."<< endl;
- else
- cerr << " Passed."<< endl;
- print(g);
-
- // clear_vertex
- std::size_t c = myrand(N);
- is_failed = false;
- clear_vertex(c, g);
- if ( out_degree(c, g) != 0 )
- is_failed = true;
- cout << "Removing vertex " << c << endl;
- remove_vertex(c, g);
-
- old_N = N;
- N = num_vertices(g);
-
- if ( (N + 1) != old_N )
- is_failed = true;
-
- if ( is_failed )
- cerr << " Failed."<< endl;
- else
- cerr << " Passed."<< endl;
-
- print(g);
-
- return 0;
- }
|