C++ Program to Model an Undirected Graph Assignment Solution

// NAME:

// FILE: Graph.cpp

// DESCRIPTION: Implementation of the Graph class.

#include <iostream.h>

#include <fstream.h>

#include <cstdlib.h>

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;

}