lengyijun
1/4/2019 - 11:34 AM

a.c

#include <iostream>
#include <set>
#include <map>
#include <stdlib.h> 
#include <stdio.h> 

using namespace std;

void printEdge();
void printNode();
bool qualify(int i);

const int N=1001;
map<int,set<int> > neighSet;
int edgeCount;

int main(){
  srand((unsigned)time(0));
  neighSet[0].insert(1);
  neighSet[1].insert(0);
  edgeCount=1;

  for(int i=1;i<N;i++){
    int size;
    map<int,set<int> >::iterator it=neighSet.find(i);
    if(it==neighSet.end()){
      size=0;
    }else{
      size=neighSet[i].size();
    }

    if(N-i+size<11){
      for(int j=i+1;j<N;j++){
        neighSet[i].insert(j);
        neighSet[j].insert(i);
        edgeCount++;
      }
    }else{
      int t=0;
      for(int j=size;j<11;j++){
        if(t>10){break;}
        int r1 = rand() % (N-i) + i;
        if(qualify(r1) && r1>i){
          neighSet[i].insert(r1);
          neighSet[r1].insert(i);
          edgeCount++;
          t=0;
        }else{
          j--;
          t++;
          //cout<<i<<" "<<j<<" "<<r1<<" "<<t<<endl;
        }
      }
    }
  }
  cout<<N<<" "<<edgeCount<<endl;
  printNode();
  printEdge();
}

void printNode(){
  for(int i=0;i<N;i++){
    int r1 = rand() % 30 + 1985;  //meaningless
    int r2 = rand() % 30 + 1985;  //meaningless
    cout<<i<<" "<<r1<<" "<<r2<<endl;
  }
}

void printEdge(){
  long totalDelay=0;
  for(int i=0;i<N;i++){
    set<int>  v=neighSet[i];
    set<int>::iterator it;
    for(it=v.begin();it!=v.end();it++){
      int k=*it;
      if(k>i){
        int r1 = rand() % 400;  //delay in 100ms 50 2000ms
        cout<<i<<" "<<k<<" "<<r1<<endl;
        totalDelay+=r1;
      }
    }
  }
  cout<<"AverageDelay: "<<totalDelay/edgeCount<<endl;
}

bool qualify(int i){
  map<int,set<int> > ::iterator it=neighSet.find(i);
  if(it==neighSet.end()){
    return true;
  }
  return it->second.size()<10;
}