random_signal_system.cpp

来自「Boost provides free peer-reviewed portab」· C++ 代码 · 共 430 行

// 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.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;
}