123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484 |
- //=======================================================================
- // Copyright 2002 Indiana University.
- // 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 <set>
- #include <utility>
- #include <algorithm>
- #define VERBOSE 0
- #include <boost/utility.hpp>
- #include <boost/graph/graph_utility.hpp>
- #include <boost/graph/random.hpp>
- #include <boost/pending/indirect_cmp.hpp>
- #include <boost/random/mersenne_twister.hpp>
- enum vertex_id_t { vertex_id = 500 };
- enum edge_id_t { edge_id = 501 };
- namespace boost {
- BOOST_INSTALL_PROPERTY(vertex, id);
- BOOST_INSTALL_PROPERTY(edge, id);
- }
- #include "graph_type.hpp" // this provides a typedef for Graph
- using namespace boost;
- /*
- This program tests models of the MutableGraph concept.
- */
- using std::cout;
- using std::endl;
- using std::cerr;
- using std::find;
- template <class Graph, class Vertex, class ID>
- bool check_vertex_cleared(Graph& g, Vertex v, ID id)
- {
- typename graph_traits<Graph>::vertex_iterator vi, viend;
- for (boost::tie(vi,viend) = vertices(g); vi != viend; ++vi) {
- typename graph_traits<Graph>::adjacency_iterator ai, aiend, found;
- boost::tie(ai, aiend) = adjacent_vertices(*vi, g);
- boost::indirect_cmp<ID, std::equal_to<std::size_t> > cmp(id);
- #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) && defined(__SGI_STL_PORT)
- // seeing internal compiler errors when using std::find_if()
- found = aiend;
- for ( ; ai != aiend; ++ai)
- if (cmp(*ai, v)) {
- found = ai;
- break;
- }
- #elif defined(BOOST_NO_CXX98_BINDERS)
- found = std::find_if(ai, aiend, std::bind(cmp,v,std::placeholders::_1));
- #else
- found = std::find_if(ai, aiend, std::bind1st(cmp,v));
- #endif
- if ( found != aiend ) {
- #if VERBOSE
- std::cerr << "should not have found vertex " << id[*found] << std::endl;
- #endif
- return false;
- }
- }
- return true;
- }
- template <class Graph, class Edge, class EdgeID>
- bool check_edge_added(Graph& g, Edge e,
- typename graph_traits<Graph>::vertex_descriptor a,
- typename graph_traits<Graph>::vertex_descriptor b,
- EdgeID edge_id, std::size_t correct_id,
- bool inserted)
- {
- if (! (source(e, g) == a)) {
- #if VERBOSE
- cerr << " Failed, vertex a not source of e."<< endl;
- #endif
- return false;
- } else if (! (target(e, g) == b)) {
- #if VERBOSE
- cerr << " Failed, vertex b not source of e."<< endl;
- #endif
- return false;
- } else if (! is_adjacent(g, a, b)) {
- #if VERBOSE
- cerr << " Failed, not adj."<< endl;
- #endif
- return false;
- } else if (! in_edge_set(g,e)) {
- #if VERBOSE
- cerr << " Failed, not in edge set."<< endl;
- #endif
- return false;
- } else if (inserted && edge_id[e] != correct_id) {
- #if VERBOSE
- cerr << " Failed, invalid edge property."<< endl;
- #endif
- return false;
- } else if (!inserted && edge_id[e] != edge_id[edge(a, b, g).first]) {
- #if VERBOSE
- cerr << " Failed, invalid edge property."<< endl;
- #endif
- return false;
- } else if (num_edges(g) != count_edges(g)) {
- #if VERBOSE
- cerr << " Failed, invalid number of edges."<< endl;
- #endif
- return false;
- }
- return true;
- }
- template <class Graph>
- std::size_t count_edges(Graph& g)
- {
- std::size_t e = 0;
- typename boost::graph_traits<Graph>::edge_iterator ei,ei_end;
- for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
- ++e;
- return e;
- }
- int main(int, char* [])
- {
- int ret = 0;
- std::size_t N = 5, E = 0;
- std::size_t old_N;
- typedef ::Graph Graph;
- Graph g;
- typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef boost::graph_traits<Graph>::edge_descriptor Edge;
- int i, j;
- std::size_t current_vertex_id = 0;
- std::size_t current_edge_id = 0;
- bool is_failed = false;
- property_map<Graph, vertex_id_t>::type vertex_id_map = get(vertex_id, g);
- property_map<Graph, edge_id_t>::type edge_id_map = get(edge_id, g);
- for (std::size_t k = 0; k < N; ++k)
- add_vertex(current_vertex_id++, g);
- // also need to test EdgeIterator graph constructor -JGS
- mt19937 gen;
-
- for (j=0; j < 10; ++j) {
- // add_edge
- #if VERBOSE
- cerr << "Testing add_edge ..." << endl;
- #endif
- for (i=0; i < 6; ++i) {
- Vertex a, b;
- a = random_vertex(g, gen);
- do {
- b = random_vertex(g, gen);
- } while ( a == b ); // don't do self edges
- #if VERBOSE
- cerr << "add_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] <<")" << endl;
- #endif
- Edge e;
- bool inserted;
- boost::tie(e, inserted) = add_edge(a, b, current_edge_id++, g);
- #if VERBOSE
- std::cout << "inserted: " << inserted << std::endl;
- std::cout << "source(e,g)" << source(e,g) << endl;
- std::cout << "target(e,g)" << target(e,g) << endl;
- std::cout << "edge_id[e] = " << edge_id_map[e] << std::endl;
- print_edges2(g, vertex_id_map, edge_id_map);
- print_graph(g, vertex_id_map);
- std::cout << "finished printing" << std::endl;
- // print_in_edges(g, vertex_id_map);
- #endif
- if (! check_edge_added(g, e, a, b, edge_id_map,
- current_edge_id - 1, inserted)) {
- ret = -1;
- break;
- }
- ++E;
- }
- // remove_edge(u, v, g)
- #if VERBOSE
- cerr << "Testing remove_edge(u, v, g) ..." << endl; is_failed = false;
- #endif
- for (i = 0; i < 2; ++i) {
- #if VERBOSE
- print_edges(g, vertex_id_map);
- #endif
- Vertex a, b;
-
- Edge e = random_edge(g, gen);
- boost::tie(a,b) = boost::incident(e, g);
- --E;
- #if VERBOSE
- cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
- #endif
- remove_edge(a, b, g);
- #if VERBOSE
- print_graph(g, vertex_id_map);
- // print_in_edges(g, vertex_id_map);
- print_edges(g, vertex_id_map);
- #endif
- is_failed = is_failed || is_adjacent(g, a, b) || in_edge_set(g, a, b)
- || num_edges(g) != count_edges(g);
- if (is_failed)
- break;
- }
- if ( is_failed ) {
- ret = -1;
- #if VERBOSE
- cerr << " Failed."<< endl;
- #endif
- } else {
- #if VERBOSE
- cerr << " Passed."<< endl;
- #endif
- }
- // remove_edge(e, g)
- #if VERBOSE
- cerr << "Testing remove_edge(e, g) ..." << endl; is_failed = false;
- #endif
- for (i = 0; i < 2; ++i) {
- #if VERBOSE
- print_edges(g, vertex_id_map);
- #endif
- Vertex a, b;
- Edge e = random_edge(g, gen);
- boost::tie(a,b) = boost::incident(e, g);
- --E;
- #if VERBOSE
- cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
- #endif
- graph_traits<Graph>::edges_size_type old_E = num_edges(g);
- remove_edge(e, g);
- #if VERBOSE
- print_graph(g, vertex_id_map);
- // print_in_edges(g, vertex_id_map);
- print_edges(g, vertex_id_map);
- #endif
- is_failed = is_failed || old_E != num_edges(g) + 1
- || num_edges(g) != count_edges(g);
- if (is_failed)
- break;
- }
- if ( is_failed ) {
- ret = -1;
- #if VERBOSE
- cerr << " Failed."<< endl;
- #endif
- } else {
- #if VERBOSE
- cerr << " Passed."<< endl;
- #endif
- }
- // add_vertex
- #if VERBOSE
- cerr << "Testing add_vertex ..." << endl; is_failed = false;
- #endif
- old_N = num_vertices(g);
- graph_traits<Graph>::vertex_descriptor vid = add_vertex(g),
- vidp1 = add_vertex(g);
- vertex_id_map[vid] = current_vertex_id++;
- vertex_id_map[vidp1] = current_vertex_id++;
- #if VERBOSE
- print_vertices(g,vertex_id_map);
- print_graph(g,vertex_id_map);
- // print_in_edges(g,vertex_id_map);
- print_edges(g,vertex_id_map);
- #endif
- // make sure the two added vertices are in the graph's vertex set
- {
- if (!in_vertex_set(g, vid)) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vid] << " not in vertices(g)" << endl;
- #endif
- ret = -1;
- break;
- }
- if (!in_vertex_set(g, vidp1)) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vidp1] << " not in vertices(g)" << endl;
- #endif
- ret = -1;
- break;
- }
- }
- // make sure the vertices do not have any out edges yet
- {
- graph_traits<Graph>::out_edge_iterator e, e_end;
- boost::tie(e,e_end) = out_edges(vid,g);
- if (e != e_end) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vid]
- << " should not have any out-edges yet" << endl;
- #endif
- ret = -1;
- break;
- }
- boost::tie(e,e_end) = out_edges(vidp1,g);
- if (e != e_end) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vidp1]
- << " should not have any out-edges yet" << endl;
- #endif
- ret = -1;
- break;
- }
- }
- // make sure the vertices do not yet appear in any of the edges
- {
- graph_traits<Graph>::edge_iterator e, e_end;
- for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) {
- if (source(*e,g) == vid || target(*e,g) == vid) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vid]
- << " should not have any edges" << endl;
- #endif
- ret = -1;
- break;
- }
- if (source(*e,g) == vidp1 || target(*e,g) == vidp1) {
- #if VERBOSE
- cerr << " Failed, " << vertex_id_map[vidp1]
- << " should not have any edges" << endl;
- #endif
- ret = -1;
- break;
- }
- }
- }
- // Make sure num_vertices(g) has been updated
- N = num_vertices(g);
- if ( (N - 2) != old_N ) {
- ret = -1;
- #if VERBOSE
- cerr << " Failed. N = " << N
- << " but should be " << old_N + 2 << endl;
- #endif
- break;
- } else {
- #if VERBOSE
- cerr << " Passed."<< endl;
- #endif
- }
- // add_edge again
- #if VERBOSE
- cerr << "Testing add_edge after add_vertex ..." << endl; is_failed = false;
- #endif
- for (i=0; i<2; ++i) {
- Vertex a = random_vertex(g, gen), b = random_vertex(g, gen);
- while ( a == vid ) a = random_vertex(g, gen);
- while ( b == vidp1 ) b = random_vertex(g, gen);
- Edge e;
- bool inserted;
- #if VERBOSE
- cerr << "add_edge(" << vertex_id_map[vid] << "," << vertex_id_map[a] <<")" << endl;
- #endif
- boost::tie(e,inserted) = add_edge(vid, a, EdgeID(current_edge_id++), g);
-
- if (! check_edge_added(g, e, vid, a, edge_id_map, current_edge_id - 1,
- inserted)) {
- ret = -1;
- break;
- }
- #if VERBOSE
- cerr << "add_edge(" << vertex_id_map[b] << "," << vertex_id_map[vidp1] <<")" << endl;
- #endif
- // add_edge without plugin
- boost::tie(e,inserted) = add_edge(b, vidp1, g);
- if (inserted)
- edge_id_map[e] = current_edge_id;
- ++current_edge_id;
- if (! check_edge_added(g, e, b, vidp1, edge_id_map,
- current_edge_id - 1, inserted)) {
- ret = -1;
- break;
- }
- }
-
- // clear_vertex
- Vertex c = random_vertex(g, gen);
- #if VERBOSE
- cerr << "Testing clear vertex ..." << endl; is_failed = false;
- print_graph(g, vertex_id_map);
- // print_in_edges(g, vertex_id_map);
- cerr << "clearing vertex " << vertex_id_map[c] << endl;
- #endif
- clear_vertex(c, g);
- #if VERBOSE
- print_graph(g, vertex_id_map);
- // print_in_edges(g, vertex_id_map);
- print_edges(g, vertex_id_map);
- #endif
- if (check_vertex_cleared(g, c, vertex_id_map) && num_edges(g) == count_edges(g)) {
- #if VERBOSE
- cerr << " Passed."<< endl;
- #endif
- } else {
- #if VERBOSE
- cerr << "**** Failed" << endl;
- #endif
- ret = -1;
- break;
- }
- #if VERBOSE
- cerr << "Testing remove vertex ..." << endl; is_failed = false;
- cerr << "removing vertex " << vertex_id_map[c] << endl;
- #endif
- old_N = num_vertices(g);
- remove_vertex(c, g);
- #if VERBOSE
- print_graph(g,vertex_id_map);
- // print_in_edges(g,vertex_id_map);
- print_edges(g, vertex_id_map);
- #endif
- // can't check in_vertex_set here because the vertex_descriptor c
- // is no longer valid, we'll just make sure the vertex set has
- // one fewer vertex
- {
- graph_traits<Graph>::vertex_iterator v, v_end;
- boost::tie(v, v_end) = vertices(g);
- for (N = 0; v != v_end; ++v) ++N; // N = std::distance(v, v_end);
- if (N != old_N - 1) {
- ret = -1;
- #if VERBOSE
- cerr << " Failed. N = " << N
- << " but should be " << old_N - 1 << endl;
- #endif
- }
- }
- N = num_vertices(g);
- if (N != old_N - 1) {
- ret = -1;
- #if VERBOSE
- cerr << " Failed. N = " << N
- << " but should be " << old_N - 1 << endl;
- #endif
- } else {
- #if VERBOSE
- cerr << " Passed."<< endl;
- #endif
- }
- }
- if (ret == 0)
- std::cout << "tests passed" << std::endl;
- return ret;
- }
|