[ceph.git] / ceph / src / boost / libs / graph / test / graph.cpp

//=======================================================================
// 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;
}
Commit	Line	Data
7c673cae FG	1	//=======================================================================
	2	// Copyright 2002 Indiana University.
	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
	12	#include <iostream>
	13	#include <vector>
	14	#include <set>
	15	#include <utility>
	16	#include <algorithm>
	17
	18	#define VERBOSE 0
	19
	20	#include <boost/utility.hpp>
	21	#include <boost/graph/graph_utility.hpp>
	22	#include <boost/graph/random.hpp>
	23	#include <boost/pending/indirect_cmp.hpp>
	24
	25	#include <boost/random/mersenne_twister.hpp>
	26
	27
	28	enum vertex_id_t { vertex_id = 500 };
	29	enum edge_id_t { edge_id = 501 };
	30	namespace boost {
	31	BOOST_INSTALL_PROPERTY(vertex, id);
	32	BOOST_INSTALL_PROPERTY(edge, id);
	33	}
	34
	35
	36	#include "graph_type.hpp" // this provides a typedef for Graph
	37
	38	using namespace boost;
	39
	40	/*
	41	This program tests models of the MutableGraph concept.
	42	*/
	43
	44	using std::cout;
	45	using std::endl;
	46	using std::cerr;
	47	using std::find;
	48
	49
	50	template <class Graph, class Vertex, class ID>
	51	bool check_vertex_cleared(Graph& g, Vertex v, ID id)
	52	{
	53	typename graph_traits<Graph>::vertex_iterator vi, viend;
	54	for (boost::tie(vi,viend) = vertices(g); vi != viend; ++vi) {
	55	typename graph_traits<Graph>::adjacency_iterator ai, aiend, found;
	56	boost::tie(ai, aiend) = adjacent_vertices(*vi, g);
	57	boost::indirect_cmp<ID, std::equal_to<std::size_t> > cmp(id);
	58
	59	#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) && defined(__SGI_STL_PORT)
	60	// seeing internal compiler errors when using std::find_if()
	61	found = aiend;
	62	for ( ; ai != aiend; ++ai)
	63	if (cmp(*ai, v)) {
	64	found = ai;
65	break;
66	}
92f5a8d4 TL	67	#elif defined(BOOST_NO_CXX98_BINDERS)
92f5a8d4 TL	68	found = std::find_if(ai, aiend, std::bind(cmp,v,std::placeholders::_1));
7c673cae FG	69	#else
	70	found = std::find_if(ai, aiend, std::bind1st(cmp,v));
	71	#endif
	72
	73	if ( found != aiend ) {
	74	#if VERBOSE
	75	std::cerr << "should not have found vertex " << id[*found] << std::endl;
	76	#endif
	77	return false;
	78	}
	79	}
	80	return true;
	81	}
	82
	83	template <class Graph, class Edge, class EdgeID>
	84	bool check_edge_added(Graph& g, Edge e,
	85	typename graph_traits<Graph>::vertex_descriptor a,
	86	typename graph_traits<Graph>::vertex_descriptor b,
	87	EdgeID edge_id, std::size_t correct_id,
	88	bool inserted)
	89	{
	90	if (! (source(e, g) == a)) {
	91	#if VERBOSE
	92	cerr << " Failed, vertex a not source of e."<< endl;
	93	#endif
	94	return false;
	95	} else if (! (target(e, g) == b)) {
	96	#if VERBOSE
	97	cerr << " Failed, vertex b not source of e."<< endl;
	98	#endif
	99	return false;
	100	} else if (! is_adjacent(g, a, b)) {
	101	#if VERBOSE
	102	cerr << " Failed, not adj."<< endl;
	103	#endif
	104	return false;
	105	} else if (! in_edge_set(g,e)) {
	106	#if VERBOSE
	107	cerr << " Failed, not in edge set."<< endl;
	108	#endif
	109	return false;
	110	} else if (inserted && edge_id[e] != correct_id) {
	111	#if VERBOSE
	112	cerr << " Failed, invalid edge property."<< endl;
	113	#endif
	114	return false;
	115	} else if (!inserted && edge_id[e] != edge_id[edge(a, b, g).first]) {
	116	#if VERBOSE
	117	cerr << " Failed, invalid edge property."<< endl;
	118	#endif
	119	return false;
	120	} else if (num_edges(g) != count_edges(g)) {
	121	#if VERBOSE
	122	cerr << " Failed, invalid number of edges."<< endl;
	123	#endif
	124	return false;
	125	}
	126	return true;
	127	}
	128
	129
	130	template <class Graph>
	131	std::size_t count_edges(Graph& g)
	132	{
133	std::size_t e = 0;
134	typename boost::graph_traits<Graph>::edge_iterator ei,ei_end;
135	for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
136	++e;
137	return e;
138	}
139
140
141	int main(int, char* [])
142	{
143	int ret = 0;
144	std::size_t N = 5, E = 0;
145	std::size_t old_N;
146
147	typedef ::Graph Graph;
148	Graph g;
149	typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
150	typedef boost::graph_traits<Graph>::edge_descriptor Edge;
151
152	int i, j;
153	std::size_t current_vertex_id = 0;
154	std::size_t current_edge_id = 0;
155
156	bool is_failed = false;
157
158	property_map<Graph, vertex_id_t>::type vertex_id_map = get(vertex_id, g);
159
160	property_map<Graph, edge_id_t>::type edge_id_map = get(edge_id, g);
161
162	for (std::size_t k = 0; k < N; ++k)
163	add_vertex(current_vertex_id++, g);
164
165	// also need to test EdgeIterator graph constructor -JGS
166	mt19937 gen;
167
168	for (j=0; j < 10; ++j) {
169
170	// add_edge
171	#if VERBOSE
172	cerr << "Testing add_edge ..." << endl;
173	#endif
174	for (i=0; i < 6; ++i) {
175	Vertex a, b;
176	a = random_vertex(g, gen);
177	do {
178	b = random_vertex(g, gen);
179	} while ( a == b ); // don't do self edges
180	#if VERBOSE
181	cerr << "add_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] <<")" << endl;
182	#endif
183	Edge e;
184	bool inserted;
185	boost::tie(e, inserted) = add_edge(a, b, current_edge_id++, g);
186	#if VERBOSE
187	std::cout << "inserted: " << inserted << std::endl;
188	std::cout << "source(e,g)" << source(e,g) << endl;
189	std::cout << "target(e,g)" << target(e,g) << endl;
190	std::cout << "edge_id[e] = " << edge_id_map[e] << std::endl;
191	print_edges2(g, vertex_id_map, edge_id_map);
192	print_graph(g, vertex_id_map);
193	std::cout << "finished printing" << std::endl;
194	// print_in_edges(g, vertex_id_map);
195	#endif
196	if (! check_edge_added(g, e, a, b, edge_id_map,
197	current_edge_id - 1, inserted)) {
198	ret = -1;
199	break;
200	}
201	++E;
202	}
203
204	// remove_edge(u, v, g)
205	#if VERBOSE
206	cerr << "Testing remove_edge(u, v, g) ..." << endl; is_failed = false;
207	#endif
208	for (i = 0; i < 2; ++i) {
209	#if VERBOSE
210	print_edges(g, vertex_id_map);
211	#endif
212	Vertex a, b;
213
214	Edge e = random_edge(g, gen);
215	boost::tie(a,b) = boost::incident(e, g);
216	--E;
217	#if VERBOSE
218	cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
219	#endif
220	remove_edge(a, b, g);
221	#if VERBOSE
222	print_graph(g, vertex_id_map);
223	// print_in_edges(g, vertex_id_map);
224	print_edges(g, vertex_id_map);
225	#endif
226	is_failed = is_failed \|\| is_adjacent(g, a, b) \|\| in_edge_set(g, a, b)
227	\|\| num_edges(g) != count_edges(g);
228	if (is_failed)
229	break;
230	}
231	if ( is_failed ) {
232	ret = -1;
233	#if VERBOSE
234	cerr << " Failed."<< endl;
235	#endif
236	} else {
237	#if VERBOSE
238	cerr << " Passed."<< endl;
239	#endif
240	}
241
242	// remove_edge(e, g)
243	#if VERBOSE
244	cerr << "Testing remove_edge(e, g) ..." << endl; is_failed = false;
245	#endif
246	for (i = 0; i < 2; ++i) {
247	#if VERBOSE
248	print_edges(g, vertex_id_map);
249	#endif
250	Vertex a, b;
251	Edge e = random_edge(g, gen);
252	boost::tie(a,b) = boost::incident(e, g);
253	--E;
254	#if VERBOSE
255	cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
256	#endif
257	graph_traits<Graph>::edges_size_type old_E = num_edges(g);
258	remove_edge(e, g);
259
260	#if VERBOSE
261	print_graph(g, vertex_id_map);
262	// print_in_edges(g, vertex_id_map);
263	print_edges(g, vertex_id_map);
264	#endif
265
266	is_failed = is_failed \|\| old_E != num_edges(g) + 1
267	\|\| num_edges(g) != count_edges(g);
268	if (is_failed)
269	break;
270	}
271	if ( is_failed ) {
272	ret = -1;
273	#if VERBOSE
274	cerr << " Failed."<< endl;
275	#endif
276	} else {
277	#if VERBOSE
278	cerr << " Passed."<< endl;
279	#endif
280	}
281
282	// add_vertex
283	#if VERBOSE
284	cerr << "Testing add_vertex ..." << endl; is_failed = false;
285	#endif
286	old_N = num_vertices(g);
287	graph_traits<Graph>::vertex_descriptor vid = add_vertex(g),
288	vidp1 = add_vertex(g);
289	vertex_id_map[vid] = current_vertex_id++;
290	vertex_id_map[vidp1] = current_vertex_id++;
291
292	#if VERBOSE
293	print_vertices(g,vertex_id_map);
294	print_graph(g,vertex_id_map);
295	// print_in_edges(g,vertex_id_map);
296	print_edges(g,vertex_id_map);
297	#endif
298	// make sure the two added vertices are in the graph's vertex set
299	{
300	if (!in_vertex_set(g, vid)) {
301	#if VERBOSE
302	cerr << " Failed, " << vertex_id_map[vid] << " not in vertices(g)" << endl;
303	#endif
304	ret = -1;
305	break;
306	}
307	if (!in_vertex_set(g, vidp1)) {
308	#if VERBOSE
309	cerr << " Failed, " << vertex_id_map[vidp1] << " not in vertices(g)" << endl;
310	#endif
311	ret = -1;
312	break;
313	}
314	}
315
316	// make sure the vertices do not have any out edges yet
317	{
318	graph_traits<Graph>::out_edge_iterator e, e_end;
319	boost::tie(e,e_end) = out_edges(vid,g);
320	if (e != e_end) {
321	#if VERBOSE
322	cerr << " Failed, " << vertex_id_map[vid]
323	<< " should not have any out-edges yet" << endl;
324	#endif
325	ret = -1;
326	break;
327	}
328	boost::tie(e,e_end) = out_edges(vidp1,g);
329	if (e != e_end) {
330	#if VERBOSE
331	cerr << " Failed, " << vertex_id_map[vidp1]
332	<< " should not have any out-edges yet" << endl;
333	#endif
334	ret = -1;
335	break;
336	}
337	}
338
339	// make sure the vertices do not yet appear in any of the edges
340	{
341	graph_traits<Graph>::edge_iterator e, e_end;
342	for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) {
343	if (source(e,g) == vid \|\| target(e,g) == vid) {
344	#if VERBOSE
345	cerr << " Failed, " << vertex_id_map[vid]
346	<< " should not have any edges" << endl;
347	#endif
348	ret = -1;
349	break;
350	}
351	if (source(e,g) == vidp1 \|\| target(e,g) == vidp1) {
352	#if VERBOSE
353	cerr << " Failed, " << vertex_id_map[vidp1]
354	<< " should not have any edges" << endl;
355	#endif
356	ret = -1;
357	break;
358	}
359	}
360	}
361	// Make sure num_vertices(g) has been updated
362	N = num_vertices(g);
363	if ( (N - 2) != old_N ) {
364	ret = -1;
365	#if VERBOSE
366	cerr << " Failed. N = " << N
367	<< " but should be " << old_N + 2 << endl;
368	#endif
369	break;
370	} else {
371	#if VERBOSE
372	cerr << " Passed."<< endl;
373	#endif
374	}
375	// add_edge again
376	#if VERBOSE
377	cerr << "Testing add_edge after add_vertex ..." << endl; is_failed = false;
378	#endif
379
380	for (i=0; i<2; ++i) {
381	Vertex a = random_vertex(g, gen), b = random_vertex(g, gen);
382	while ( a == vid ) a = random_vertex(g, gen);
383	while ( b == vidp1 ) b = random_vertex(g, gen);
384	Edge e;
385	bool inserted;
386	#if VERBOSE
387	cerr << "add_edge(" << vertex_id_map[vid] << "," << vertex_id_map[a] <<")" << endl;
388	#endif
389	boost::tie(e,inserted) = add_edge(vid, a, EdgeID(current_edge_id++), g);
390
391	if (! check_edge_added(g, e, vid, a, edge_id_map, current_edge_id - 1,
392	inserted)) {
393	ret = -1;
394	break;
395	}
396
397	#if VERBOSE
398	cerr << "add_edge(" << vertex_id_map[b] << "," << vertex_id_map[vidp1] <<")" << endl;
399	#endif
400	// add_edge without plugin
401	boost::tie(e,inserted) = add_edge(b, vidp1, g);
402	if (inserted)
403	edge_id_map[e] = current_edge_id;
404	++current_edge_id;
405
406	if (! check_edge_added(g, e, b, vidp1, edge_id_map,
407	current_edge_id - 1, inserted)) {
408	ret = -1;
409	break;
410	}
411	}
412
413	// clear_vertex
414	Vertex c = random_vertex(g, gen);
415	#if VERBOSE
416	cerr << "Testing clear vertex ..." << endl; is_failed = false;
417	print_graph(g, vertex_id_map);
418	// print_in_edges(g, vertex_id_map);
419	cerr << "clearing vertex " << vertex_id_map[c] << endl;
420	#endif
421	clear_vertex(c, g);
422	#if VERBOSE
423	print_graph(g, vertex_id_map);
424	// print_in_edges(g, vertex_id_map);
425	print_edges(g, vertex_id_map);
426	#endif
427	if (check_vertex_cleared(g, c, vertex_id_map) && num_edges(g) == count_edges(g)) {
428	#if VERBOSE
429	cerr << " Passed."<< endl;
430	#endif
431	} else {
432	#if VERBOSE
433	cerr << "**** Failed" << endl;
434	#endif
435	ret = -1;
436	break;
437	}
438
439	#if VERBOSE
440	cerr << "Testing remove vertex ..." << endl; is_failed = false;
441	cerr << "removing vertex " << vertex_id_map[c] << endl;
442	#endif
443
444	old_N = num_vertices(g);
445	remove_vertex(c, g);
446	#if VERBOSE
447	print_graph(g,vertex_id_map);
448	// print_in_edges(g,vertex_id_map);
449	print_edges(g, vertex_id_map);
450	#endif
451	// can't check in_vertex_set here because the vertex_descriptor c
452	// is no longer valid, we'll just make sure the vertex set has
453	// one fewer vertex
454	{
455	graph_traits<Graph>::vertex_iterator v, v_end;
456	boost::tie(v, v_end) = vertices(g);
457	for (N = 0; v != v_end; ++v) ++N; // N = std::distance(v, v_end);
458	if (N != old_N - 1) {
459	ret = -1;
460	#if VERBOSE
461	cerr << " Failed. N = " << N
462	<< " but should be " << old_N - 1 << endl;
463	#endif
464	}
465	}
466
467	N = num_vertices(g);
468	if (N != old_N - 1) {
469	ret = -1;
470	#if VERBOSE
471	cerr << " Failed. N = " << N
472	<< " but should be " << old_N - 1 << endl;
473	#endif
474	} else {
475	#if VERBOSE
476	cerr << " Passed."<< endl;
477	#endif
478	}
479	}
480	if (ret == 0)
481	std::cout << "tests passed" << std::endl;
482
483	return ret;
484	}