[ceph.git] / ceph / src / boost / libs / signals / test / random_signal_system.cpp

// Boost.Signals library

// Copyright Douglas Gregor 2001-2004. Use, modification and
// distribution is subject to 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)

// For more information, see http://www.boost.org

#include <boost/signal.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/random.hpp>
#include <map>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <boost/test/minimal.hpp>

using namespace boost;
using namespace boost::signals;

struct signal_tag {
  typedef vertex_property_tag kind;
};

struct connection_tag {
  typedef edge_property_tag kind;
};

typedef signal4<void, int, int, double, int&> signal_type;
typedef adjacency_list<listS, listS, directedS,
                       // Vertex properties
                       property<signal_tag, signal_type*,
  //                       property<vertex_color_t, default_color_type,
                       property<vertex_index_t, int> >,
                       // Edge properties
                       property<connection_tag, connection,
                       property<edge_weight_t, int> > >
  signal_graph_type;
typedef signal_graph_type::vertex_descriptor vertex_descriptor;
typedef signal_graph_type::edge_descriptor edge_descriptor;

// The signal graph
static signal_graph_type signal_graph;

// Mapping from a signal to its associated vertex descriptor
static std::map<signal_type*, vertex_descriptor> signal_to_descriptor;

// Mapping from a connection to its associated edge descriptor
static std::map<connection, edge_descriptor> connection_to_descriptor;

std::map<signal_type*, int> min_signal_propagate_distance;

void remove_disconnected_connections()
{
  // remove disconnected connections
  std::map<connection, edge_descriptor>::iterator i =
    connection_to_descriptor.begin();
  while (i != connection_to_descriptor.end()) {
    if (!i->first.connected()) {
      connection_to_descriptor.erase(i++);
    }
    else {
      ++i;
    }
  }
}

void remove_signal(signal_type* sig)
{
  clear_vertex(signal_to_descriptor[sig], signal_graph);
  remove_vertex(signal_to_descriptor[sig], signal_graph);
  delete sig;
  signal_to_descriptor.erase(sig);
  remove_disconnected_connections();
}

void random_remove_signal(minstd_rand& rand_gen);

struct tracking_bridge {
  tracking_bridge(const tracking_bridge& other) 
    : sig(other.sig), rand_gen(other.rand_gen)
  { ++bridge_count; }

  tracking_bridge(signal_type* s, minstd_rand& rg) : sig(s), rand_gen(rg) 
  { ++bridge_count; }

  ~tracking_bridge()
  { --bridge_count; }

  void operator()(int cur_dist, int max_dist, double deletion_prob,
                  int& deletions_left) const
  {
    if (signal_to_descriptor.find(sig) == signal_to_descriptor.end())
      return;

    ++cur_dist;

    // Update the directed Bacon distance
    if (min_signal_propagate_distance.find(sig) ==
          min_signal_propagate_distance.end()) {
      min_signal_propagate_distance[sig] = cur_dist;
    }
    else if (cur_dist < min_signal_propagate_distance[sig]) {
      min_signal_propagate_distance[sig] = cur_dist;
    }
    else if (deletion_prob == 0.0) {
      // don't bother calling because we've already found a better route here
      return;
    }

    // Maybe delete the signal
    if (uniform_01<minstd_rand>(rand_gen)() < deletion_prob &&
        deletions_left-- && signal_to_descriptor.size() > 1) {
      random_remove_signal(rand_gen);
    }
    // propagate the signal
    else if (cur_dist < max_dist) {
      (*sig)(cur_dist, max_dist, deletion_prob, deletions_left);
    }
  }

  signal_type* sig;
  minstd_rand& rand_gen;
  static int bridge_count;
};

int tracking_bridge::bridge_count = 0;

namespace boost {
  template<typename V>
  void visit_each(V& v, const tracking_bridge& t, int)
  {
    v(t);
    v(t.sig);
  }
}

signal_type* add_signal()
{
  signal_type* sig = new signal_type();
  vertex_descriptor v = add_vertex(signal_graph);
  signal_to_descriptor[sig] = v;
  put(signal_tag(), signal_graph, v, sig);

  return sig;
}

connection add_connection(signal_type* sig1, signal_type* sig2,
                          minstd_rand& rand_gen)
{
  std::cout << "  Adding connection: " << sig1 << " -> " << sig2 << std::endl;

  connection c = sig1->connect(tracking_bridge(sig2, rand_gen));
  edge_descriptor e =
    add_edge(signal_to_descriptor[sig1], signal_to_descriptor[sig2],
             signal_graph).first;
  connection_to_descriptor[c] = e;
  put(connection_tag(), signal_graph, e, c);
  put(edge_weight, signal_graph, e, 1);
  return c;
}

void remove_connection(connection c)
{
  signal_type* sig1 = get(signal_tag(), signal_graph,
                          source(connection_to_descriptor[c], signal_graph));
  signal_type* sig2 = get(signal_tag(), signal_graph,
                          target(connection_to_descriptor[c], signal_graph));
  std::cout << "  Removing connection: " << sig1 << " -> " << sig2
            << std::endl;
  c.disconnect();
  remove_edge(connection_to_descriptor[c], signal_graph);
  connection_to_descriptor.erase(c);
}

bool signal_connection_exists(signal_type* sig1, signal_type* sig2,
                              edge_descriptor& edge_desc)
{
  vertex_descriptor source_sig = signal_to_descriptor[sig1];
  vertex_descriptor target_sig = signal_to_descriptor[sig2];
  signal_graph_type::out_edge_iterator e;
  for (e = out_edges(source_sig, signal_graph).first;
       e != out_edges(source_sig, signal_graph).second; ++e) {
    if (target(*e, signal_graph) == target_sig) {
      edge_desc = *e;
      return true;
    }
  }
  return false;
}

bool signal_connection_exists(signal_type* sig1, signal_type* sig2)
{
  edge_descriptor e;
  return signal_connection_exists(sig1, sig2, e);
}

std::map<signal_type*, vertex_descriptor>::iterator
choose_random_signal(minstd_rand& rand_gen)
{
  int signal_idx
    = uniform_int<>(0, signal_to_descriptor.size() - 1)(rand_gen);
  std::map<signal_type*, vertex_descriptor>::iterator result =
    signal_to_descriptor.begin();
  for(; signal_idx; --signal_idx)
    ++result;

  return result;
}

void random_remove_signal(minstd_rand& rand_gen)
{
  std::map<signal_type*, vertex_descriptor>::iterator victim =
    choose_random_signal(rand_gen);
  std::cout << "  Removing signal " << victim->first << std::endl;
  remove_signal(victim->first);
}

void random_add_connection(minstd_rand& rand_gen)
{
  std::map<signal_type*, vertex_descriptor>::iterator source;
  std::map<signal_type*, vertex_descriptor>::iterator target;
  do {
    source = choose_random_signal(rand_gen);
    target = choose_random_signal(rand_gen);
  } while (signal_connection_exists(source->first, target->first));

  add_connection(source->first, target->first, rand_gen);
}

void random_remove_connection(minstd_rand& rand_gen)
{
  int victim_idx =
    uniform_int<>(0, num_edges(signal_graph)-1)(rand_gen);
  signal_graph_type::edge_iterator e = edges(signal_graph).first;
  while (victim_idx--) {
    ++e;
  }

  remove_connection(get(connection_tag(), signal_graph, *e));
}

void random_bacon_test(minstd_rand& rand_gen)
{
  signal_type* kevin = choose_random_signal(rand_gen)->first;
  min_signal_propagate_distance.clear();
  min_signal_propagate_distance[kevin] = 0;

  const int horizon = 10; // only go to depth 10 at most

  std::cout << "  Bacon test: kevin is " << kevin
            << "\n    Propagating signal...";

  // Propagate the signal out to the horizon
  int deletions_left = 0;
  (*kevin)(0, horizon, 0.0, deletions_left);

  std::cout << "OK\n    Finding shortest paths...";

  // Initialize all colors to white
  {
    unsigned int num = 0;
    for (signal_graph_type::vertex_iterator v = vertices(signal_graph).first;
         v != vertices(signal_graph).second;
         ++v) {
      //      put(vertex_color, signal_graph, *v, white_color);
      put(vertex_index, signal_graph, *v, num++);
    }

    BOOST_CHECK(num == num_vertices(signal_graph));
  }

  // Perform a breadth-first search starting at kevin, and record the
  // distances from kevin to each reachable node.
  std::map<vertex_descriptor, int> bacon_distance_map;

#if 0
  bacon_distance_map[signal_to_descriptor[kevin]] = 0;
  breadth_first_visit(signal_graph, signal_to_descriptor[kevin],
                      visitor(
                        make_bfs_visitor(
                         record_distances(
                           make_assoc_property_map(bacon_distance_map),
                           on_examine_edge()))).
                      color_map(get(vertex_color, signal_graph)));
#endif

  dijkstra_shortest_paths(signal_graph, signal_to_descriptor[kevin],
                          distance_map(make_assoc_property_map(bacon_distance_map)));
  std::cout << "OK\n";
  // Make sure the bacon distances agree (prior to the horizon)
  {
    std::map<signal_type*, int>::iterator i;
    for (i = min_signal_propagate_distance.begin();
         i != min_signal_propagate_distance.end();
         ++i) {
      if (i->second != bacon_distance_map[signal_to_descriptor[i->first]]) {
        std::cout << "Signal distance to " << i->first << " was "
                  << i->second << std::endl;
        std::cout << "Graph distance was "
                  << bacon_distance_map[signal_to_descriptor[i->first]]
                  << std::endl;
      }
      BOOST_CHECK(i->second == bacon_distance_map[signal_to_descriptor[i->first]]);
    }
  }
}

void randomly_create_connections(minstd_rand& rand_gen, double edge_probability)
{
  // Randomly create connections
  uniform_01<minstd_rand> random(rand_gen);
  for (signal_graph_type::vertex_iterator v1 = vertices(signal_graph).first;
       v1 != vertices(signal_graph).second; ++v1) {
    for (signal_graph_type::vertex_iterator v2 = vertices(signal_graph).first;
         v2 != vertices(signal_graph).second; ++v2) {
      if (random() < edge_probability) {
        add_connection(get(signal_tag(), signal_graph, *v1),
                       get(signal_tag(), signal_graph, *v2),
                       rand_gen);
      }
    }
  }
}

void random_recursive_deletion(minstd_rand& rand_gen)
{
  signal_type* kevin = choose_random_signal(rand_gen)->first;
  min_signal_propagate_distance.clear();
  min_signal_propagate_distance[kevin] = 0;

  const int horizon = 4; // only go to depth "horizon" at most

  std::cout << "  Recursive deletion test: start is " << kevin << std::endl;

  // Propagate the signal out to the horizon
  int deletions_left = (int)(0.05*num_vertices(signal_graph));
  (*kevin)(0, horizon, 0.05, deletions_left);
}

int test_main(int argc, char* argv[])
{
  if (argc < 4) {
    std::cerr << "Usage: random_signal_system <# of initial signals> "
              << "<edge probability> <iterations>" << std::endl;
    return 1;
  }

  int number_of_initial_signals = atoi(argv[1]);
  double edge_probability = atof(argv[2]);
  int iterations = atoi(argv[3]);

  int seed;
  if (argc == 5)
    seed = atoi(argv[4]);
  else
    seed = time(0);

  std::cout << "Number of initial signals: " << number_of_initial_signals
            << std::endl;
  std::cout << "Edge probability: " << edge_probability << std::endl;
  std::cout << "Iterations: " << iterations << std::endl;
  std::cout << "Seed: " << seed << std::endl;

  // Initialize random number generator
  minstd_rand rand_gen;
  rand_gen.seed(seed);

  for (int iter = 0; iter < iterations; ++iter) {
    if (num_vertices(signal_graph) < 2) {
      for (int i = 0; i < number_of_initial_signals; ++i)
        add_signal();
    }

    while (num_edges(signal_graph) < 2) {
      randomly_create_connections(rand_gen, edge_probability);
    }

    std::cerr << "Iteration #" << (iter+1) << std::endl;

    uniform_int<> random_action(0, 7);
    switch (random_action(rand_gen)) {
    case 0:
      std::cout << "  Adding new signal: " << add_signal() << std::endl;
      break;

    case 1:
      random_remove_signal(rand_gen);
      break;

    case 2:
      if (num_edges(signal_graph) <
            num_vertices(signal_graph)*num_vertices(signal_graph)) {
        random_add_connection(rand_gen);
      }
      break;

    case 3:
      random_remove_connection(rand_gen);
      break;

    case 4:
    case 5:
    case 6:
      random_bacon_test(rand_gen);
      break;

    case 7:
      random_recursive_deletion(rand_gen);
      break;
    }
  }

  for (signal_graph_type::vertex_iterator v = vertices(signal_graph).first;
       v != vertices(signal_graph).second;
       ++v) {
    delete get(signal_tag(), signal_graph, *v);
  }

  BOOST_CHECK(tracking_bridge::bridge_count == 0);
  if (tracking_bridge::bridge_count != 0) {
    std::cerr << tracking_bridge::bridge_count << " connections remain.\n";
  }
  return 0;
}
Commit	Line	Data
7c673cae FG	1	// Boost.Signals library
	2
	3	// Copyright Douglas Gregor 2001-2004. Use, modification and
	4	// distribution is subject to the Boost Software License, Version
	5	// 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	6	// http://www.boost.org/LICENSE_1_0.txt)
	7
	8	// For more information, see http://www.boost.org
	9
	10	#include <boost/signal.hpp>
	11	#include <boost/graph/adjacency_list.hpp>
	12	#include <boost/graph/breadth_first_search.hpp>
	13	#include <boost/graph/dijkstra_shortest_paths.hpp>
	14	#include <boost/property_map/property_map.hpp>
	15	#include <boost/random.hpp>
	16	#include <map>
	17	#include <set>
	18	#include <stdlib.h>
	19	#include <time.h>
	20	#include <boost/test/minimal.hpp>
	21
	22	using namespace boost;
	23	using namespace boost::signals;
	24
	25	struct signal_tag {
	26	typedef vertex_property_tag kind;
	27	};
	28
	29	struct connection_tag {
	30	typedef edge_property_tag kind;
	31	};
	32
	33	typedef signal4<void, int, int, double, int&> signal_type;
	34	typedef adjacency_list<listS, listS, directedS,
	35	// Vertex properties
	36	property<signal_tag, signal_type*,
	37	// property<vertex_color_t, default_color_type,
	38	property<vertex_index_t, int> >,
	39	// Edge properties
	40	property<connection_tag, connection,
	41	property<edge_weight_t, int> > >
	42	signal_graph_type;
	43	typedef signal_graph_type::vertex_descriptor vertex_descriptor;
	44	typedef signal_graph_type::edge_descriptor edge_descriptor;
	45
	46	// The signal graph
	47	static signal_graph_type signal_graph;
	48
	49	// Mapping from a signal to its associated vertex descriptor
	50	static std::map<signal_type*, vertex_descriptor> signal_to_descriptor;
	51
	52	// Mapping from a connection to its associated edge descriptor
	53	static std::map<connection, edge_descriptor> connection_to_descriptor;
	54
	55	std::map<signal_type*, int> min_signal_propagate_distance;
	56
	57	void remove_disconnected_connections()
	58	{
	59	// remove disconnected connections
	60	std::map<connection, edge_descriptor>::iterator i =
	61	connection_to_descriptor.begin();
	62	while (i != connection_to_descriptor.end()) {
	63	if (!i->first.connected()) {
	64	connection_to_descriptor.erase(i++);
65	}
66	else {
67	++i;
68	}
69	}
70	}
71
72	void remove_signal(signal_type* sig)
73	{
74	clear_vertex(signal_to_descriptor[sig], signal_graph);
75	remove_vertex(signal_to_descriptor[sig], signal_graph);
76	delete sig;
77	signal_to_descriptor.erase(sig);
78	remove_disconnected_connections();
79	}
80
81	void random_remove_signal(minstd_rand& rand_gen);
82
83	struct tracking_bridge {
84	tracking_bridge(const tracking_bridge& other)
85	: sig(other.sig), rand_gen(other.rand_gen)
86	{ ++bridge_count; }
87
88	tracking_bridge(signal_type* s, minstd_rand& rg) : sig(s), rand_gen(rg)
89	{ ++bridge_count; }
90
91	~tracking_bridge()
92	{ --bridge_count; }
93
94	void operator()(int cur_dist, int max_dist, double deletion_prob,
95	int& deletions_left) const
96	{
97	if (signal_to_descriptor.find(sig) == signal_to_descriptor.end())
98	return;
99
100	++cur_dist;
101
102	// Update the directed Bacon distance
103	if (min_signal_propagate_distance.find(sig) ==
104	min_signal_propagate_distance.end()) {
105	min_signal_propagate_distance[sig] = cur_dist;
106	}
107	else if (cur_dist < min_signal_propagate_distance[sig]) {
108	min_signal_propagate_distance[sig] = cur_dist;
109	}
110	else if (deletion_prob == 0.0) {
111	// don't bother calling because we've already found a better route here
112	return;
113	}
114
115	// Maybe delete the signal
116	if (uniform_01<minstd_rand>(rand_gen)() < deletion_prob &&
117	deletions_left-- && signal_to_descriptor.size() > 1) {
118	random_remove_signal(rand_gen);
119	}
120	// propagate the signal
121	else if (cur_dist < max_dist) {
122	(*sig)(cur_dist, max_dist, deletion_prob, deletions_left);
123	}
124	}
125
126	signal_type* sig;
127	minstd_rand& rand_gen;
128	static int bridge_count;
129	};
130
131	int tracking_bridge::bridge_count = 0;
132
133	namespace boost {
134	template<typename V>
135	void visit_each(V& v, const tracking_bridge& t, int)
136	{
137	v(t);
138	v(t.sig);
139	}
140	}
141
142	signal_type* add_signal()
143	{
144	signal_type* sig = new signal_type();
145	vertex_descriptor v = add_vertex(signal_graph);
146	signal_to_descriptor[sig] = v;
147	put(signal_tag(), signal_graph, v, sig);
148
149	return sig;
150	}
151
152	connection add_connection(signal_type* sig1, signal_type* sig2,
153	minstd_rand& rand_gen)
154	{
155	std::cout << " Adding connection: " << sig1 << " -> " << sig2 << std::endl;
156
157	connection c = sig1->connect(tracking_bridge(sig2, rand_gen));
158	edge_descriptor e =
159	add_edge(signal_to_descriptor[sig1], signal_to_descriptor[sig2],
160	signal_graph).first;
161	connection_to_descriptor[c] = e;
162	put(connection_tag(), signal_graph, e, c);
163	put(edge_weight, signal_graph, e, 1);
164	return c;
165	}
166
167	void remove_connection(connection c)
168	{
169	signal_type* sig1 = get(signal_tag(), signal_graph,
170	source(connection_to_descriptor[c], signal_graph));
171	signal_type* sig2 = get(signal_tag(), signal_graph,
172	target(connection_to_descriptor[c], signal_graph));
173	std::cout << " Removing connection: " << sig1 << " -> " << sig2
174	<< std::endl;
175	c.disconnect();
176	remove_edge(connection_to_descriptor[c], signal_graph);
177	connection_to_descriptor.erase(c);
178	}
179
180	bool signal_connection_exists(signal_type* sig1, signal_type* sig2,
181	edge_descriptor& edge_desc)
182	{
183	vertex_descriptor source_sig = signal_to_descriptor[sig1];
184	vertex_descriptor target_sig = signal_to_descriptor[sig2];
185	signal_graph_type::out_edge_iterator e;
186	for (e = out_edges(source_sig, signal_graph).first;
187	e != out_edges(source_sig, signal_graph).second; ++e) {
188	if (target(*e, signal_graph) == target_sig) {
189	edge_desc = *e;
190	return true;
191	}
192	}
193	return false;
194	}
195
196	bool signal_connection_exists(signal_type* sig1, signal_type* sig2)
197	{
198	edge_descriptor e;
199	return signal_connection_exists(sig1, sig2, e);
200	}
201
202	std::map<signal_type*, vertex_descriptor>::iterator
203	choose_random_signal(minstd_rand& rand_gen)
204	{
205	int signal_idx
206	= uniform_int<>(0, signal_to_descriptor.size() - 1)(rand_gen);
207	std::map<signal_type*, vertex_descriptor>::iterator result =
208	signal_to_descriptor.begin();
209	for(; signal_idx; --signal_idx)
210	++result;
211
212	return result;
213	}
214
215	void random_remove_signal(minstd_rand& rand_gen)
216	{
217	std::map<signal_type*, vertex_descriptor>::iterator victim =
218	choose_random_signal(rand_gen);
219	std::cout << " Removing signal " << victim->first << std::endl;
220	remove_signal(victim->first);
221	}
222
223	void random_add_connection(minstd_rand& rand_gen)
224	{
225	std::map<signal_type*, vertex_descriptor>::iterator source;
226	std::map<signal_type*, vertex_descriptor>::iterator target;
227	do {
228	source = choose_random_signal(rand_gen);
229	target = choose_random_signal(rand_gen);
230	} while (signal_connection_exists(source->first, target->first));
231
232	add_connection(source->first, target->first, rand_gen);
233	}
234
235	void random_remove_connection(minstd_rand& rand_gen)
236	{
237	int victim_idx =
238	uniform_int<>(0, num_edges(signal_graph)-1)(rand_gen);
239	signal_graph_type::edge_iterator e = edges(signal_graph).first;
240	while (victim_idx--) {
241	++e;
242	}
243
244	remove_connection(get(connection_tag(), signal_graph, *e));
245	}
246
247	void random_bacon_test(minstd_rand& rand_gen)
248	{
249	signal_type* kevin = choose_random_signal(rand_gen)->first;
250	min_signal_propagate_distance.clear();
251	min_signal_propagate_distance[kevin] = 0;
252
253	const int horizon = 10; // only go to depth 10 at most
254
255	std::cout << " Bacon test: kevin is " << kevin
256	<< "\n Propagating signal...";
257
258	// Propagate the signal out to the horizon
259	int deletions_left = 0;
260	(*kevin)(0, horizon, 0.0, deletions_left);
261
262	std::cout << "OK\n Finding shortest paths...";
263
264	// Initialize all colors to white
265	{
266	unsigned int num = 0;
267	for (signal_graph_type::vertex_iterator v = vertices(signal_graph).first;
268	v != vertices(signal_graph).second;
269	++v) {
270	// put(vertex_color, signal_graph, *v, white_color);
271	put(vertex_index, signal_graph, *v, num++);
272	}
273
274	BOOST_CHECK(num == num_vertices(signal_graph));
275	}
276
277	// Perform a breadth-first search starting at kevin, and record the
278	// distances from kevin to each reachable node.
279	std::map<vertex_descriptor, int> bacon_distance_map;
280
281	#if 0
282	bacon_distance_map[signal_to_descriptor[kevin]] = 0;
283	breadth_first_visit(signal_graph, signal_to_descriptor[kevin],
284	visitor(
285	make_bfs_visitor(
286	record_distances(
287	make_assoc_property_map(bacon_distance_map),
288	on_examine_edge()))).
289	color_map(get(vertex_color, signal_graph)));
290	#endif
291
292	dijkstra_shortest_paths(signal_graph, signal_to_descriptor[kevin],
293	distance_map(make_assoc_property_map(bacon_distance_map)));
294	std::cout << "OK\n";
295	// Make sure the bacon distances agree (prior to the horizon)
296	{
297	std::map<signal_type*, int>::iterator i;
298	for (i = min_signal_propagate_distance.begin();
299	i != min_signal_propagate_distance.end();
300	++i) {
301	if (i->second != bacon_distance_map[signal_to_descriptor[i->first]]) {
302	std::cout << "Signal distance to " << i->first << " was "
303	<< i->second << std::endl;
304	std::cout << "Graph distance was "
305	<< bacon_distance_map[signal_to_descriptor[i->first]]
306	<< std::endl;
307	}
308	BOOST_CHECK(i->second == bacon_distance_map[signal_to_descriptor[i->first]]);
309	}
310	}
311	}
312
313	void randomly_create_connections(minstd_rand& rand_gen, double edge_probability)
314	{
315	// Randomly create connections
316	uniform_01<minstd_rand> random(rand_gen);
317	for (signal_graph_type::vertex_iterator v1 = vertices(signal_graph).first;
318	v1 != vertices(signal_graph).second; ++v1) {
319	for (signal_graph_type::vertex_iterator v2 = vertices(signal_graph).first;
320	v2 != vertices(signal_graph).second; ++v2) {
321	if (random() < edge_probability) {
322	add_connection(get(signal_tag(), signal_graph, *v1),
323	get(signal_tag(), signal_graph, *v2),
324	rand_gen);
325	}
326	}
327	}
328	}
329
330	void random_recursive_deletion(minstd_rand& rand_gen)
331	{
332	signal_type* kevin = choose_random_signal(rand_gen)->first;
333	min_signal_propagate_distance.clear();
334	min_signal_propagate_distance[kevin] = 0;
335
336	const int horizon = 4; // only go to depth "horizon" at most
337
338	std::cout << " Recursive deletion test: start is " << kevin << std::endl;
339
340	// Propagate the signal out to the horizon
341	int deletions_left = (int)(0.05*num_vertices(signal_graph));
342	(*kevin)(0, horizon, 0.05, deletions_left);
343	}
344
345	int test_main(int argc, char* argv[])
346	{
347	if (argc < 4) {
348	std::cerr << "Usage: random_signal_system <# of initial signals> "
349	<< "<edge probability> <iterations>" << std::endl;
350	return 1;
351	}
352
353	int number_of_initial_signals = atoi(argv[1]);
354	double edge_probability = atof(argv[2]);
355	int iterations = atoi(argv[3]);
356
357	int seed;
358	if (argc == 5)
359	seed = atoi(argv[4]);
360	else
361	seed = time(0);
362
363	std::cout << "Number of initial signals: " << number_of_initial_signals
364	<< std::endl;
365	std::cout << "Edge probability: " << edge_probability << std::endl;
366	std::cout << "Iterations: " << iterations << std::endl;
367	std::cout << "Seed: " << seed << std::endl;
368
369	// Initialize random number generator
370	minstd_rand rand_gen;
371	rand_gen.seed(seed);
372
373	for (int iter = 0; iter < iterations; ++iter) {
374	if (num_vertices(signal_graph) < 2) {
375	for (int i = 0; i < number_of_initial_signals; ++i)
376	add_signal();
377	}
378
379	while (num_edges(signal_graph) < 2) {
380	randomly_create_connections(rand_gen, edge_probability);
381	}
382
383	std::cerr << "Iteration #" << (iter+1) << std::endl;
384
385	uniform_int<> random_action(0, 7);
386	switch (random_action(rand_gen)) {
387	case 0:
388	std::cout << " Adding new signal: " << add_signal() << std::endl;
389	break;
390
391	case 1:
392	random_remove_signal(rand_gen);
393	break;
394
395	case 2:
396	if (num_edges(signal_graph) <
397	num_vertices(signal_graph)*num_vertices(signal_graph)) {
398	random_add_connection(rand_gen);
399	}
400	break;
401
402	case 3:
403	random_remove_connection(rand_gen);
404	break;
405
406	case 4:
407	case 5:
408	case 6:
409	random_bacon_test(rand_gen);
410	break;
411
412	case 7:
413	random_recursive_deletion(rand_gen);
414	break;
415	}
416	}
417
418	for (signal_graph_type::vertex_iterator v = vertices(signal_graph).first;
419	v != vertices(signal_graph).second;
420	++v) {
421	delete get(signal_tag(), signal_graph, *v);
422	}
423
424	BOOST_CHECK(tracking_bridge::bridge_count == 0);
425	if (tracking_bridge::bridge_count != 0) {
426	std::cerr << tracking_bridge::bridge_count << " connections remain.\n";
427	}
428	return 0;
429	}