random_bipartite.cpp

生成Bipartite Graphs ./distributions -u -m 1 -M 10 -n 100 -s 500 > top_distrib ./distributions -p

/*
  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/

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

  A bipartite graph is a graph G=(top, bottom, links) whose nodes can 
  be splitted in two sets (top and bottom nodes), such that there is no 
  links inside one set.
  Generates a random Bipartite graph with prescribed degree distribution
  for both top and bottom sets.
  Generated graph is sent to stdout either as a set of links in the 
  bipartite graph (top<->bottom), or as a set of links in the unipartite 
  vision G' of G (G'=(bottom, links2), where bottom nodes are linked if 
  there are connected to a same top node => each top node is responsible 
  for a clique in the projection).
*/

#include <math.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
using std::cout;
using std::cin;
using std::cerr;

void usage(char *program_name, int status) {
  if (status == EXIT_SUCCESS)
    {
      cout << "Usage: " << program_name << " -t top_distrib -b bottom_distrib [-u]" << endl
           << "  Generates a random bipartite graph with given distribution" << endl
           << "  Graph is printed on stdout with one link (betwen top and bottom) per line." << endl
           << "    -t: file containing top degree distribution" << endl
           << "    -b: file containing bottom degree distribution" << endl
           << "    -u: print links of the unipartite vision instead of bipartite one" << endl
	   << "        link between u and v if they are both linked to a same top node" << endl
           << "    -h, this usage" << endl
           << "Remarks:" << endl
           << "  Resulting graph may contain multiples links or loops." << endl ;
    }
  else
    {
      cerr << "Try '" << program_name << " -h' for usage information." << endl;
    }
  exit(status);
}

void
parse_args(int argc, char **argv, ifstream &top_d, ifstream &bot_d, int &u) {
  extern char *optarg;
  extern int optind, opterr, optopt;
  char c;
  
  u=0;

  while ((c = getopt(argc, argv, "t:b:uh")) != EOF){
    switch (c) {
    case 'h':       /* help */
      usage(argv[0], EXIT_SUCCESS);
      break;
    case 't':       /* nb vertices */
      top_d.open(optarg, ifstream::in);
      if (!top_d.is_open()) {
	cerr << argv[0] << ": can't stat source " << optarg << endl;
	exit(EXIT_FAILURE);
      }
      break;
    case 'b':       /* nb links */
      bot_d.open(optarg, ifstream::in);
      if (!bot_d.is_open()) {
	cerr << argv[0] << ": can't stat source " << optarg << endl;
	exit(EXIT_FAILURE);
      }
      break;
    case 'u':       /* connection probability */
      u=1;
      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 print_unipartite;
  ifstream top_d, bot_d;
  parse_args(argc, argv, top_d, bot_d, print_unipartite);

  //read top distrib from file
  vector<int> topdistrib(0);
  while(top_d) {
    int deg, freq;
    top_d >> deg >> freq;
    if (deg<0 || freq<0) {
      cerr << argv[0] << ": Top distribution not valid" << endl
	   << "  Check line: " << deg << " " << freq << endl;
      exit(EXIT_FAILURE);
    }
    if(top_d) {
      if (topdistrib.size()<deg+1)
	topdistrib.resize(deg+1);
      topdistrib[deg]=freq;
    }
  }
  top_d.close();

  //read bottom distrib from file
  vector<int> botdistrib(0);
  while(bot_d) {
    int deg, freq;
    bot_d >> deg >> freq;
    if (deg<0 || freq<0) {
      cerr << argv[0] << ": Bottom distribution not valid" << endl
	   << "  Check line: " << deg << " " << freq << endl;
      exit(EXIT_FAILURE);
    }
    if(bot_d) {
      if (botdistrib.size()<deg+1)
	botdistrib.resize(deg+1);
      botdistrib[deg]=freq;
    }
  }
  bot_d.close();

  //check distribs
  int sum_bot=0, sum_top=0;
  for(int i=0;i<botdistrib.size();i++)
    sum_bot += i*botdistrib[i];
  for(int i=0;i<topdistrib.size();i++)
    sum_top += i*topdistrib[i];
  if (sum_bot != sum_top) {
    cerr << argv[0] << ": Distributions not compatible: top=" << sum_top << ", " << "bot=" << sum_bot << endl
	 << "  sum(i*top[i]) must be equal to sum(i*bottom[i])" << endl;
    exit(EXIT_FAILURE);
  }

  //create top connection points
  int clique=0;
  vector<int> topdeg;
  for(int i=0 ; i<topdistrib.size() ; i++)
    for(int j=0 ; j<topdistrib[i] ; j++) {
      for(int k=0 ; k<i ; k++)
	topdeg.push_back(clique);
      clique++;
    }
  for(int i=0 ; i<topdeg.size() ; i++) {
    int t=rand()%(topdeg.size()-i)+i;
    int tmp=topdeg[i];
    topdeg[i]=topdeg[t];
    topdeg[t]=tmp;
  }

  //create bottom connection points
  int vertex=0;
  vector<int> botdeg;
  for(int i=0 ; i<botdistrib.size() ; i++)
    for(int j=0 ; j<botdistrib[i] ; j++) {
      for(int k=0 ; k<i ; k++)
	botdeg.push_back(vertex);
      vertex++;
    }
  for(int i=0 ; i<botdeg.size() ; i++) {
    int t=rand()%(botdeg.size()-i)+i;
    int tmp=botdeg[i];
    botdeg[i]=botdeg[t];
    botdeg[t]=tmp;
  }

  //link top and bottom connection points
  vector<vector<int> > graph(clique);
  for(int i=0 ; i<topdeg.size() ; i++)
    graph[topdeg[i]].push_back(botdeg[i]);
  
  if (print_unipartite) { //print graph in unipartite format (bottom<->bottom)
    for(int i=0 ; i<clique ; i++)
      for(int j=0 ; j<graph[i].size() ; j++)
	for(int k=j+1 ; k<graph[i].size() ; k++)
	  cout << graph[i][j] << " " << graph[i][k] << endl;
  } else { //print graph in bipartite format (top<->bottom)
    for(int i=0 ; i<clique ; i++)
      for(int j=0 ; j<graph[i].size() ; j++)
	cout << i << " " << graph[i][j] << endl ;
  }
}