Question One – Generating a Random Network (5 Points) We want to generate a rand

Question

Question One – Generating a Random Network (5 Points)

We want to generate a random network to compare to the Facebook data.

You can assume the number of vertices and edges are identical to the Facebook data:

              int n = 4039;

              int m = 88234;

Randomly generate pairs (i,j) adding them to the network if i != j and that edge does not already exist in the network.

To generate a random number between 0 and n-1:

             i = rand() % n;

To determine if an edge is already in the network use the find function from the algorithms package.

#include <algorithms>

…

vector<int>::iterator it;

it = find(vecEx.begin(), vecEx.end(), 10);

If it == vecEx.end() then 10 is not contained in the vector of integers vecEx.

Explanation / Answer

I am pasting the required C++ code below. The program outputs the edges on the console. So, you can simply redirect the output to any file using redirection operator (<). Well, I have also added the code to output the edgelist in to a file called 'Network.txt'

#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;

int main() {

   int n = 4039;    // No of nodes
   int m = 88234;   // No of edges

   // vector of pairs for storing the edges  
   vector<pair<int, int> > edgeList;

   // File stream for storing edges in the output network file
   fstream nwFile;
   nwFile.open("Network.txt");

   int edgeCnt = 0;
   int i, j;
   pair<int, int> p;
   vector<pair<int, int> >::iterator it;
   while(edgeCnt < m)
       {
           i = rand() % n;
           j = rand() % n;
           while(i == j)
               j = rand() % n;

           p = make_pair(i,j);
           it = find(edgeList.begin(), edgeList.end(), p);
           if (it == edgeList.end()) {
               edgeList.push_back( std::make_pair(i, j));
               nwFile << i << " " << j << endl;
               cout << i << " " << j << endl;
           }
           else
               continue;
          
           edgeCnt++;
       }
       return 0;
   }

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.