For this homework, use the implementation Graphs.zip. This implementation also provides a simple main function in a file named main.cpp.

Graphs.zip (includes the following files below in c++):

BFS.cpp:

// **************************************************** // Implementation file BFS.cpp // A breadth-first search of the Graph class. // ****************************************************

#include "BFS.h"

BFS::BFS(const Graph &g) : g(g), mark(g.getNumVertices(), -1), parents(g.getNumVertices(), 0), count(0) { startSearch(); } // end constructor

void BFS::startSearch() { for (int v = 0; v

void BFS::search(Edge e) { // create a queue to push edges queue q;

map m; // holds adjacency list of current vertex map::iterator iter;

q.push(e); while (!q.empty()) { // get the edge at the front if the queue e = q.front();

// pop the edge off the queue q.pop();

// if the vertex w has not visited yet, visit it if (mark[e.w] == -1) { int v = e.v, w = e.w, weight = e.weight; mark[w] = count++; // mark w visited parents[w] = v; // store w's parent

// go through adjacency list of w m = g.adjList[w]; for (iter = m.begin(); iter != m.end(); iter++) // if w's neighbor vertices have not been visited, // push the edge on the queue if (mark[iter->first] == -1) q.push(Edge(w, iter->first, iter->second)); } // end if } // end while } // end search // End of implementation file

BFS.h:

// **************************************************** // Implementation file BFS.cpp // A breadth-first search of the Graph class. // ****************************************************

#include "BFS.h"

BFS::BFS(const Graph &g) : g(g), mark(g.getNumVertices(), -1), parents(g.getNumVertices(), 0), count(0) { startSearch(); } // end constructor

void BFS::startSearch() { for (int v = 0; v

void BFS::search(Edge e) { // create a queue to push edges queue q;

map m; // holds adjacency list of current vertex map::iterator iter;

q.push(e); while (!q.empty()) { // get the edge at the front if the queue e = q.front();

// pop the edge off the queue q.pop();

// if the vertex w has not visited yet, visit it if (mark[e.w] == -1) { int v = e.v, w = e.w, weight = e.weight; mark[w] = count++; // mark w visited parents[w] = v; // store w's parent

// go through adjacency list of w m = g.adjList[w]; for (iter = m.begin(); iter != m.end(); iter++) // if w's neighbor vertices have not been visited, // push the edge on the queue if (mark[iter->first] == -1) q.push(Edge(w, iter->first, iter->second)); } // end if } // end while } // end search // End of implementation file

Edge.h:

// ************************************************** // Header file Edge.h // An Edge class for graph implementations. // ************************************************** class Edge { public: int v, w, weight; Edge(int firstVertex, int secondVertex, int edgeWeight) { v = firstVertex; w = secondVertex; weight = edgeWeight; } // end constructor }; // End of header file Graph.cpp:

// **************************************************** // Implementation file Graph.cpp // An adjacency list representation of an undirected, // weighted graph. // **************************************************** #include "Graph.h"

Graph::Graph(int n) { map zero_map; zero_map[0] = 0; adjList.assign(n,zero_map); numVertices = n; numEdges = 0; } // end constructor

int Graph::getNumVertices() const { return numVertices; } // end getNumVertices

int Graph::getNumEdges() const { return numEdges; } // end getNumEdges

int Graph::getWeight(Edge e) const { return e.weight; } // end getWeight

void Graph::add(Edge e) { int v = e.v, w = e.w, weight = e.weight;

adjList[v].insert(make_pair(w, weight)); adjList[w].insert(make_pair(v, weight)); numEdges++; } // end add

void Graph::remove(Edge e) { int v = e.v, w = e.w, weight = e.weight;

adjList[e.v].erase(w); adjList[e.w].erase(v); numEdges--; } // end remove

map::iterator Graph::findEdge(int v, int w) { map m = adjList[v]; map::iterator iter = m.find(w);

return iter; } // end findEdge

Graph.h:

/ **************************************************** // Header file Graph.h // An adjacency list representation of an undirected, // weighted graph. // **************************************************** #include #include #include

using namespace std;

class Graph { public: int numVertices; // number of vertices in the graph int numEdges; // number of edges in the graph

// Adjacency list representation of the graph; // the map pair consists of the second vertex (key) // and the edge weight (value). vector

Graph(int n); // Constructor. // Precondition: The graph is empty. // Postcondition: The graph is initialized to hold n // vertices.

int getNumVertices() const; // Determines the number of vertices in the graph. // Precondition: None. // Postcondition: Returns the number of vertices in the // graph.

int getNumEdges() const; // Determines the number of edges in the graph. // Precondition: None. // Postcondition: Returns the number of edges in the graph.

int getWeight(Edge e) const; // Determines the weight of an edge. // Precondition: The edge exists in the graph. // Postcondition: Returns the weight of the edge parameter.

void add(Edge e); // Creates an edge in the graph. // Precondition: The vertices exist in the graph. // Postcondition: Adds to both v and w's list.

void remove(Edge e); // Removes an edge from the graph. // Precondition: The vertices exist in the graph. // Postcondition: Removes edges from both v and w's list.

map::iterator findEdge(int v, int w); // Finds the edge connecting v and w. // Precondition: The edge exists. // Postcondition: Returns an iterator to map key w in // vector[v]. }; // End of header file

main.cpp:

include #include "Graph.h"

using namespace std;

int main() { Graph g(5); cout

1) (50 points] Write a function in main.cpp, which creates a random graph of a certain size as follows. The function takes two parameters. The first parameter is the number of vertices n. The second parameter p (1 >= p >= 0) is the probability that an edge exists between a pair of nodes. In particular, after instantiating a graph with n vertices and o edges, go over all possible vertex pairs one by one, and for each such pair, put an edge between the vertices with probability p. (Thus, there is no edge between the vertices with probability 1-p). In the main function, create a graph with 10,000 (ten thousand) vertices, and experiment the following. Pick some p to create the edges of the graph, and then determine the number of components of the graph (Write a function to do this. How do you do this? I talked about this in the class). Remember the extreme cases: for p = 0, there are no edges in the graph so that the number of components is the number of vertices, which is 10,000. For p = 1, we have the complete graph so that the graph is certainly connected, the number of components is 1. Now by experiment, determine when the graph becomes connected as you increase from p = 0 up to p = 1. As a mathematical fact, there is some value p such that for values smaller than p, the graph has more than one component. After the probability hits p and goes higher, the graph suddenly becomes connected. Try to determine this value of p. Write your result as a comment in your code. 2) (50 points) Now, extend your function creating a random graph so as to assign weights to the edges. The edges will have random integer weights in the range [1...10). Make sure you select some p so as to make the graph connected. Implement Prim's algorithm in a function. Then run it on this graph and calculate the cost of the minimum spanning tree. You may get help online for the implementation of Prim's algorithm