Go back to NetworkGeneration

<project-file type=“source”/>

<content> #include <genrand2.h> #include <iostream> #include <fstream> #include <algorithm> #include <set> #include <time.h> #include “parameters.h”

class Link { public:

  Link(int n, bool type) : neighbor(n), internal(type) {}
  int node() const { return neighbor; }
  bool operator == (int n) const { return neighbor == n; }
  void dump() const {
      std::cout<<neighbor<<((internal)?"h":"e");
  }

  bool internal;

private:

  int neighbor;

};

class Node { public:

  int degree() const { return links.size(); }
  int isNeighbor(int node) const {
      return std::find(links.begin(), links.end(), node) == links.end();
  }
  void connect(int node, bool internal) {
      std::vector<Link>::iterator i = std::find(links.begin(), links.end(), node);
      if (i == links.end())
          links.push_back(Link(node, internal));
      else
          i->internal = internal;
  }
  const std::vector<Link> &neighbors() const { return links; }
  void dump() const {
      int n = links.size();
      for (int i = 0; i < n; i++)
          links[i].dump();
      std::cout<<std::endl;
  }
  int id;

private:

  std::vector<Link> links;

};

class Net { public:

  Net(int population);
  void connect(int i, int j, bool internal, bool directed = false);
  bool connected(int i, int j) { return nodes[i].isNeighbor(j); }
  int degree(int i) const { return nodes[i].degree(); }
  const std::vector<int> connectedComponent(int i) const;
  int maximumDegree() { return M; }
  int population() { return nodes.size(); }
  void dump() const;

private:

  int M;
  std::vector<Node> nodes;
  void traverse(int node, std::vector<bool> &visited) const;

};

Net::Net(int population)

  : nodes(population)

{

  M = 0;
  for (int i = 0; i < population; i++)
      nodes[i].id = i;

}

void Net::connect(int i, int j, bool internal, bool directed) {

  nodes[i].connect(j, internal);
  int k = nodes[i].degree();
  if (M < k) M = k;
  if (!directed) {
      nodes[j].connect(i, internal);
      k = nodes[j].degree();
      if (M < k) M = k;
  }

}

const std::vector<int> Net::connectedComponent(int i) const {

  int n = nodes.size();
  std::vector<bool> connected(n, false);
  traverse(i, connected);
  std::vector<int> component(n);
  std::vector<int>::iterator j = component.begin();
  for (int i = 0; i < n; i++)
      if (connected[i]) *j++ = i;
  component.erase(j, component.end());
  return component;

}

void Net::traverse(int node, std::vector<bool> &visited) const {

  visited[node] = true;
  const std::vector<Link> &neighbors = nodes[node].neighbors();
  std::vector<Link>::const_iterator i;
  for (i = neighbors.begin(); i != neighbors.end(); i++)
      if(!visited[i->node()]) traverse(i->node(), visited);

}

void Net::dump() const {

  int n = nodes.size();
  for (int i = 0; i < n; i++) nodes[i].dump();

}

class Households { public:

  Households(int n, SimDistribution *household_size_dist);
  Households(const Households &);
  ~Households();
  int populationSize() const { return population_size; }
  int householdSize(int i) const { return household_sizes[i]; }
  int inHousehold(int node) const { return in_household[node]; }
  int nodeNotInHousehold(int node, int house) const;
  int randomInHousehold(int i) const {
      return households[i][genrand2i() % household_sizes[i]];
  }
  int nodeInHouse(int i, int j) const { return households[i][j]; }
  void combine(int i, int j);
  int houseHolds() const { return households.size(); }

private:

  std::vector<int *> households;
  std::vector<int> in_household;
  std::vector<int> household_sizes;
  int population_size;
  void move(int i, int j);

};

Households::Households(const Households &hh)

  : households(hh.houseHolds()), household_sizes(hh.household_sizes), in_household(hh.in_household)

{

int n = hh.houseHolds(), m, *p, *q;
for (int i = 0; i < n; i++) {
	m = hh.householdSize(i);
              p = (int*) malloc(sizeof(int) * m);
	q = hh.households[i];
	for (int j = 0; j < m ; j++) p[j] = q[j];
	households[i] = p;
}
  population_size = hh.populationSize();

}

Households::Households(int n, SimDistribution *household_size_dist)

  : households(n), household_sizes(n)

{

  population_size = 0;
  int k;
  for (int i = 0; i < n; i++) {
      k = (int) household_size_dist->draw();
      population_size += household_sizes[i] = k;
      households[i] = (int*) malloc(sizeof(int) * k);
  }
  in_household.resize(population_size);
  for (int i = 0, k = 0; i < n; i++)
      for (int j = 0; j < household_sizes[i]; j++) {
          households[i][j] = k;
          in_household[k] = i;
          ++k;
      }

}

Households::~Households() {

  int n = households.size();
  for (int i = 0; i < n; i++) free(households[i]);

}

int Households::nodeNotInHousehold(int node, int house) const {

  int m, n = households.size();
  for (int i = 0; i < n; i++) if (i != house) {
      m = household_sizes[i];
      if (node < m) return households[i][node];
      node -= m;
  }

} void Households::combine(int i, int j) {

  move(j, i);
  households[j] = NULL;
  move(households.size() - 1, j);
  households.pop_back();

}

void Households::move(int j, int i) {

  int m = household_sizes[i];
  int n = household_sizes[j];
  household_sizes[i] = m + n;
  household_sizes[j] = 0;
  int *p = (int*) realloc(households[i], sizeof(int)*(m + n));
  int *q = households[j];
  for (int k = 0; k < n; k++) {
      in_household[q[k]] = i;
      p[k + m] = q[k];
  }
  free(households[j]);
  households[i] = p;
  households[j] = NULL;

}

generate an integer i such that 0 ⇐ i < n, and i != m inline int genrand2i(int n, int m) { if (m >= n) return genrand2i() % n; int k = genrand2i() % (n - 1); if (k < m) return k; return k + 1; } int main(int argc, const char *argv[]) { Parameters params; BoolArgument ArgType(“random-on-household”, “if true, construct a random network of households, otherwise construct a random network of individuals”, Argument::REQUIRED); IntArgument ArgHouseholds(“households”, “number of households”, Argument::REQUIRED); IntArgument ArgM(“M”, “maximum allowable external degree”, Argument::NOT_REQUIRED); FloatArgument ArgAvgk(“average-degree”, “average degree”, Argument::REQUIRED); DistributionArgument ArgHouseholdSize(“household-size”, “the household size distributionr”, Argument::REQUIRED); LongArgument ArgSeed(“seed”, “the seed to initialize the random number generator”, Argument::NOT_REQUIRED); ArgHouseholdSize.setEnableDiscrete(true); ArgHouseholdSize.setEnableExp(false); ArgHouseholdSize.setEnableNormal(false); ArgHouseholdSize.setEnableGamma(false); ArgHouseholdSize.setEnableExp(false); ArgHouseholdSize.setEnableNULL(false); params.addArgument(ArgHouseholds); params.addArgument(ArgType); params.addArgument(ArgM); params.addArgument(ArgAvgk); params.addArgument(ArgHouseholdSize); params.addArgument(ArgSeed); if (!params.parse(argc, argv)) { params.usage(argv[0]); return 1; } int households = ArgHouseholds.value(); int M = ArgM.value(); bool random_on_household = ArgType.value(); float avgk = ArgAvgk.value(); SimDistribution *household_size_dist = ArgHouseholdSize.value(); time_t seed; if (ArgSeed.set()) seed = ArgSeed.value(); else time(&seed); sgenrand2(seed); Households hh(households, household_size_dist); Net net(hh.populationSize()); internal connections

  for (int i = 0; i < households; i++) {
      int n = hh.householdSize(i);
      for (int j = 0; j < n; j++)
          for (int k = j + 1; k < n; k++)
              net.connect(hh.nodeInHouse(i, j), hh.nodeInHouse(i, k), true);
  }

  // connected components
  Households components(hh);

  // total number of links
  int links = (int)(avgk * hh.populationSize() / 2);
  if (links < households - 1) {
      std::cerr<<"Too few edges, cannot make a connected graph"<<std::endl;
      return 1;
  }

  int k = 0, n, m, i, j;
  while (k < links) {
      m = components.houseHolds();
      if (random_on_household) {
          int h1 = genrand2i() % m;
          int h2 = genrand2i(m, h1);
          i = components.randomInHousehold(h1);
          j = components.randomInHousehold(h2);
      }
      else {
          i = genrand2i() % components.populationSize();
          int house = components.inHousehold(i);
          int total = components.populationSize() - components.householdSize(house);
          int h = genrand2i() % total;
          j = components.nodeNotInHousehold(h, house);
      }
      if (net.degree(i) == M || net.degree(j) == M) continue;
      net.connect(i, j, false);
      components.combine(components.inHousehold(i), components.inHousehold(j));
      if (components.houseHolds() == 1) break;
      k++;
  }
  m = hh.houseHolds();
  while (k < links) {
      if (random_on_household) {
          int h1 = genrand2i() % m;
          int h2 = genrand2i(m, h1);
          i = hh.randomInHousehold(h1);
          j = hh.randomInHousehold(h2);
      }
      else {
          i = genrand2i() % hh.populationSize();
          while (true) {
              j = genrand2i(hh.populationSize(), i);
              if (hh.inHousehold(i) != hh.inHousehold(j)) break;
          }
      }

#define external_degree(i) (net.degree(i) - hh.householdSize(hh.inHousehold(i)) + 1)

      if (external_degree(i) == M || external_degree(j) == M) continue;
      net.connect(i, j, false);
      k++;
  }
  net.dump();

  return 0;

} </content> <use name=“genrand2.h”/> <use name=“parameters.h”/>