C++ Program to Model Undirected Graph Assignment Solution.

Instructions

Objective

Write a C++ assignment class definition for an abstract data type called Graph that models an undirected graph.

Requirements and Specifications

Implement the following public member functions.

Graph(char *fileName): A constructor that creates the graph using the file passed into the function.

The format of the file is described later in the document

Graph(): An appropriate destructor.
void display() const: Displays the graph's adjacency matrix to the screen using this format (see examples later):

Single space between digits.
First row (top) and first column (left) is vertex 0, second row and column is vertex 1,…, last row (bottom) and last column (right) is vertex n – 1.

void displayDFS(int vertex) const: Displays the result of a depth first search starting at the provided vertex.

When you have a choice between selecting two vertices, pick the vertex with the lower number .

bool isBipartite() const: Returns true if the graph is bipartite and false otherwise.

Screenshots of output

program to model undirected graph in C++

Source Code

// NAME:
// FILE: Graph.cpp
// DESCRIPTION: Implementation of the Graph class.

#include  
#include 
#include 
using namespace std;

#include "Graph.h" 
#include "QueueInt.h"
#include "StackInt.h"

// Constructor: load the graph from a file 
Graph::Graph(char *filename)
{
string line;
ifstream graphFile(filename);
graphFile >> this->numVertices;
this->createMatrix(this->numVertices);
int vertexA;
int vertexB;
int weight;
while (graphFile >> vertexA)
{
graphFile >> vertexB;
graphFile >> weight;
this->addEdge(vertexA, vertexB, weight);
}
graphFile.close(); 

} 

// Destructor 
Graph::~Graph()
{
for (int i = 0; i < this->numVertices; i++)
{
delete[] this->matrix[i];
}
delete[] this->matrix;

} 

// Display the adjacency matrix 
void Graph::display() const
{

for (int i = 0; i < this->numVertices; i++)
{
for (int j = 0; j < this->numVertices; j++)
{

if (i == j)
{
cout << 0;
}
else if (this->matrix[i][j] == -1)
{
cout << "x";
}
else
{
cout << this->matrix[i][j];
}
cout << " ";
if (j == this->numVertices - 1)
{
cout << endl;
      }
    }
  }
}



// Displays the depth first search starting at the given vertex
void Graph::displayDFS(int vertex) const
{


cout << " DFS at vertex 0: " << vertex << ": ";

bool visited[this->numVertices];
for (int i = 0; i < this->numVertices; i++)
{
visited[i] = false;
}

this->dfsHelper(vertex, visited);

cout << endl;
}


void Graph::dfsHelper(int vertex, bool *visited) const
{

visited[vertex] = true;
cout << vertex << " ";
for (int i = 0; i < this->numVertices; i++)
{
if (!(visited[i]) && this->isAdjacent(vertex, i))
{
dfsHelper(i, visited);
    }
  }
}



// Perform breadth first search starting at the given vertex
void Graph::displayBFS(int vertex) const
{

  cout << "BFS at vertex 0: " << vertex << ": ";
  bool visited[this->numVertices];
  for (int i = 0; i < this->numVertices; i++)
  {
    visited[i] = false;
  }

  QueueInt queue;
  visited[vertex] = true;

  cout << vertex << " ";
  queue.enqueue(vertex);
  while (!queue.isEmpty())
  {
    vertex = queue.dequeue();

    for (int i = 0; i < this->numVertices; i++)
    {
      if (!(visited[i]) && this->isAdjacent(vertex, i))
      {

        visited[i] = true;
        cout << i << " ";
        queue.enqueue(i);
      }
    }
  }
  cout << endl;
}

int *Graph::mstNextEdge(bool *visited, int edge[]) const
{
edge[0] = -1;
edge[1] = -1;
edge[2] = -1;

for (int i = 0; i < this->numVertices; i++)
{
for (int j = 0; j < this->numVertices; j++)
{
int weight = this->matrix[i][j];

if (this->isAdjacent(i, j) && (visited[i] && !visited[j]))
{
if (edge[0] == -1 || edge[1] == -1)
{
edge[0] = i;
edge[1] = j;
edge[2] = weight;
}

int minWeight = this->matrix[edge[0]][edge[1]];

if (weight < minWeight)
{
edge[0] = i;
edge[1] = j;
edge[2] = weight;
        }
      }
    }
  }

return edge;
}

// Create 2D matrix
void Graph::createMatrix(int numVertices)
{
this->matrix = new int *[numVertices];
for (int i = 0; i < numVertices; i++)
{
this->matrix[i] = new int[numVertices];
for (int j = 0; j < numVertices; j++)
{
this->matrix[i][j] = -1;
    }
  }
}

void Graph::addEdge(int vertexA, int vertexB, int weight)
{
this->matrix[vertexA][vertexB] = weight;
this->matrix[vertexB][vertexA] = weight;
}

bool Graph::isAdjacent(int vertexA, int vertexB) const
{
 return this->matrix[vertexA][vertexB] > 0;
}



// Determine whether the graph is bipartite or not
bool Graph::isBipartite() const
{
return false;
}

C++ Program to Model an Undirected Graph Assignment Solution.

Instructions

Requirements and Specifications

Implement the following public member functions.