erdos_renyi.cpp

Generates a random Erdos-Renyi network

/*
  Copyright (C) 2003, Guillaume-Latapy - LIAFA (University of Paris 7)

  Disclaimer: this code is provided 'as-is', without any express or
  implied warranty. In no event will the authors be held liable for 
  any damages arising from the use of this software.

  Permission is granted to anyone to use this code for any purpose,
  to alter it and redistribute it without restrictions. Just feel
  free to inform us if you plan to use it. If you face any problems
  or find any bug, please contact us using our webpage:
    http://www.liafa.jussieu.fr/~guillaume/

  --------------------------------------------------

  Generates a random Erdos-Renyi graph, with either a given connection 
  probability or a given number of links.
  Generated graph is sent to stdout as a set of links (one per line).
*/


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <iostream>
#include <set>

#define EXIT_SUCCESS 0
#define EXIT_FAILURE 1

using namespace std;

void usage(char *program_name, int status) {
  if (status == EXIT_SUCCESS)
    {
      cout << "Usage: " << program_name << " -n nbvertices -m nblinks" << endl
	   << "Usage: " << program_name << " -n nbvertices -p probability" << endl
	   << "  Generates a random Erdos-Renyi graph with a fixed number of links (Gnm)" << endl
	   << "  or a fixed connection probability (Gnp)." << endl
	   << "  Graph is printed on stdout with one link per line." << endl
	   << "    -n: number of vertices of the random graph (non negative)" << endl
	   << "    -m: number of links of the random graph (non negative)" << endl
	   << "    -p: connection probability for the random graph (between 0. and 1.)" << endl
	   << "    -h, this usage" << endl
	   << "Remarks:" << endl
	   << "  Gnp generation is quadratic in n and can take a while if n is large: 10^5 or more" << endl
	   << "  Gnm generation is fast as long as the density is not too high: m<<n(n-1)/2" << endl ;
    }
  else
    {
      cerr << "Try '" << program_name << " -h' for usage information." << endl;
    }
  exit(status);
}

void
parse_args(int argc, char **argv, int &n, int &m, float &p) {
  extern char *optarg;
  extern int optind, opterr, optopt;
  char c;

  while ((c = getopt(argc, argv, "n:m:p:h")) != EOF){
    switch (c) {
    case 'h':       /* help */
      usage(argv[0], EXIT_SUCCESS);
      break;
    case 'n':       /* nb vertices */
      n=atoi(optarg);
      break;
    case 'm':       /* nb links */
      m=atoi(optarg);
      break;
    case 'p':       /* connection probability */
      p=atof(optarg);
      break;

    case ':':       /* missing operand */
      cerr << argv[0] << ": Option -" << optopt << " requires an operand." << endl;
      usage(argv[0], EXIT_FAILURE);
      break;
    case '?':       /* unknown option */
      cerr << argv[0] << ": Unrecognized option -" << optopt << endl;
      usage(argv[0], EXIT_FAILURE);
    }
  }
}

int
main(int argc, char **argv)
{
  srand(time(NULL));

  int n=-1, m=-1;
  float p=-1.;

  parse_args(argc, argv, n, m, p);
  if (n<0 || (m==-1 && (p<0. || p>1.)) || (p!=-1 && m!=-1))
    usage(argv[0], EXIT_SUCCESS);

  if (p>0.) { // generates a Gnp
    for(int i=0 ; i<n ; i++)
      for(int j=i+1 ; j<n;j++)
	if ((random()*1.)/(RAND_MAX*1.)<=p)
	  cout << i << " " << j << endl;
  } else { // generates a Gnm
    set<pair<int, int> > links;
    
    int nblinks=0;
    while (nblinks<m) {
      int src = random()%n;
      int dest = random()%n;
      pair<int,int> p(min(src,dest),max(src,dest));

      if (src!=dest && links.find(p)==links.end()) {
	cout << src << " " << dest << endl;
	links.insert(p);
	nblinks++;
      }
    }
  }
}