Hello,
I'm getting an error when I try to compile the code and I do not know how to solve the problem. Please help! The assignment asks me to create a BOOLEAN function that can check if the graph is connected or not. So I decided to use DFS approach to this problem. But now my code does not want to compile please help. ERROR LNK 2019.
My code and other files necessary to run will be included in an attachment.
//*******************************************************************************************
// Program includes
// *******************************************************************************************
#include <iostream>
#include <iomanip>
#include <cmath>
#include <deque>
#include <vector>
#include "rstream.h"
using namespace std;
// *******************************************************************************************
// Function prototypes
// *******************************************************************************************
// Builds the representation of the network as random graph
void buildRG( int n, // n is the number of the vertices
double pr, // Probability (a number 0 < pr < 1) to have an edge between two vertex
vector< deque< int > > &adjl, // Adjacency list
int &l ); // Number of edges
// Prints the graph representation: Adj. list
// Used for testing
void printAList( int n, const vector< deque< int > > &l );
//Function for searching connected vertices
bool DFS_Con(int n, // n is the number of the vertices
vector< deque< int > > &adjl); // Adjacency list
//Function for exploring edges
void DFS_VISIT (const vector< deque<int> > &adjl_1, // Adjacency list
int u, // Current vertex counter
vector <bool> &col, // Store colors of Vetices
int x); // n is the number of the vertices
// *******************************************************************************************
// Definitions and calls withing your main() function
// *******************************************************************************************
int main ()
{
int nn = 0;
double edgeProb = 0;
// Total number of vertices in the graph. Asked as input from the user
cout<<"Enter total number of Vertices: ";
cin>>nn;
cout<<endl<<endl;
// Probability of an edge between two vertices. It can be asked as input from the user
cout<<"Enter probability between two Vertices: ";
cin>> edgeProb;
cout<<endl<<endl;
// Adjacency list
vector< deque< int > > G( nn );
// Number of edges
int ll = 0;
// Fucntion call for generating random graphs
buildRG( nn, edgeProb, G, ll );
// Function call for displaying Adjacency List
printAList( nn, G );
// Function call for searching connected vertices
if (DFS_Con(nn, G )== true)
cout<<"connected";
else
cout<<"not connected";
cin>>nn;
return 0;
}
// *******************************************************************************************
// Function definitions
// *******************************************************************************************
// Generates representation of random graphs
void buildRG( int n,
double pr,
vector< deque< int > > &adjl,
int &l ) {
static Rstream prob( 284723743 );
int nl = 0; // The number of edges
// Build up the adj. list, the adj matrix and count the number of edges
for( int a = 0; a < n; a++ )
for( int b = a + 1; b < n; b++ )
if ( prob.uniform01() <= pr )
{
adjl[ a ].push_front( b );
adjl[ b ].push_front( a );
nl++;
}
// Total number of edges
l = nl;
} // End buildRG
//---------------------------------------------------------------------
// Printing out graph representations: Adj. list
void printAList( int n, const vector< deque< int > > &l ) {
for( int i = 0; i < n; i++ ) {
cout << "Node " << i << " list:";
for( unsigned int j = 0; j < l[ i ].size(); j++ )
cout << " -> " << l[ i ][ j ];
cout << endl;
}
} // End printAList
//---------------------------------------------------------------------
//Finding connected vertices
bool DFS_Con (int n, const vector< deque <int> > &adjl){
vector <bool> color (n+1,false); //false = white, true = black
for ( int b=0; b<n; b++)
if (color[b] == false)
DFS_VISIT (adjl, b, color, n);
return color[n];
} // End DFS_Con
//--------------------------------------------------------------------
//Visiting vertices
void DFS_VISIT (const vector< deque<int> > &adjl_1, int u, vector <bool> &col, int x){
col[u] = true;
for (unsigned int a = 0; a < adjl_1[u].size(); a++)
if (col[adjl_1[u][a]] == false){
col[x] = true;
DFS_VISIT (adjl_1, adjl_1[u][a] , col, x);
}
} // End DFS_VISIT