//matrix implementation of prim's algorithm

#include <iostream>
#include<math.h>
#import<string.h>

using namespace std;

int matrix[50][50];
int finishedWeight[50];
int finishedVertices[50];
char edges[50][20];
int counter = 0;
int size = 0;

//fill the matrix with a big number
void fillMatrix(int vertexNum)
{
  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      matrix[i][j] = pow(2,32) - 1;
    }
  }
}

//set the weight of the vertices
void insert(int start, int end, int weight)
{
    matrix[start][end] = weight;
}


//add the edge for an undirected graph
void addUndirected(int vertexNum)
{
  int start = 0;
  int end = 0;
  int weight;
  size = vertexNum;
  
  fillMatrix(vertexNum);
  while(start != -1)
  {
    cout << "Please enter a starting vertex: ";
    cin >> start;
    cout << "Please enter an ending vertex: ";
    cin >> end;
    cout << "Please enter a weight: ";
    cin >> weight;
    insert(start, end, weight);
    insert(end, start, weight);
  } 
}

// add the edge for a directed graph
void addDirected(int vertexNum)
{
  int start = 0;
  int end = 0;
  int weight;
  size = vertexNum;
  fillMatrix(vertexNum);
  while(start != -1)
  {
    cout << "Please enter a starting vertex: ";
    cin >> start;
    cout << "Please enter an ending vertex: ";
    cin >> end;
    cout << "Please enter a weight: ";
    cin >> weight;
    insert(start, end, weight);
  }
} 

// checks to see if the value is in the array
bool isInArray(int ar[], int value, int size)
{
  bool check = false;
  for(int i = 0; i < size; i++)
  {
    if(ar[i] == value)
      check = true;
  }
  return check;
}

//execute the algorithm
void prim()
{
  int minx;
  int miny;
  int firstVertex;
  int check = 0;
  int minWeight = pow(2, 32) - 1;
  for(int k = 0; k < counter; k++)
  {
    firstVertex = finishedVertices[k];
    for(int l = 0; l < size; l++)
    {
      if(matrix[firstVertex][l] < minWeight && !isInArray(finishedVertices, l, counter))
      {
	     minx = firstVertex;
             miny = l;
             minWeight = matrix[firstVertex][l];
             check = 1;
      }
    }
  }
  if(check == 1)
  {
    finishedVertices[counter] = miny;
    finishedWeight[counter] = minWeight;
    sprintf(edges[counter], "edge %d: %d - %d.\n", counter, minx, miny);

    counter++;
    prim();
  }
}

// print the vertices and the corresponding weight and each edge
void print()
{
   for(int i = 0; i < counter; i++)
  {
    cout << finishedVertices[i] << "\t" << finishedWeight[i] << endl;
  }
 
  for(int u = 0; u < counter; u++)
    cout << edges[u];
}

//0 out finishedVertices[], finishedWeights[], and counter
void reset()
{
  for(int i = 0; i < size; i++)
    finishedVertices[i] = 0;
  for(int j = 0; j < size; j++)
    finishedWeight[j] = 0;
  counter = 0;
}


// run functions and prompts
int main()
{
  int option = 0;   // option for starting vertex for algorithm
  int option1 = 0;  // option for directed or undirected
  int option2;  // option to see if the algorithm is run again
  int vertexNum = 0;

  while(option1 != 3)
  {
    option2 = 1;
    cout << "1. Directed Graph. \n"
         << "2. Undirected Graph. \n"
         << "3. Exit. \n"
         << "Selection: ";
    cin >> option1;

    if(option1 == 1)
    {
      cout << "Enter the number of vertices ";
      cin >> vertexNum;
      addDirected(vertexNum);
      while(option2 == 1)
      {
        reset();
        cout << "Please enter a starting vertex for the algorithm ";
        cin >> option;
        finishedVertices[0] = option;
        counter++;
        prim();
        print();
        cout << "Press 1 to run the algorithm with a different starting vertex or 2 to go back to the main menu ";
        cin >> option2;
      }
    }

    else if(option1 == 2)
    {
      cout << "Enter the number of vertices ";
      cin >> vertexNum;
      addUndirected(vertexNum);
      while(option2 == 1)
      {
        reset();
        cout << "Please enter a starting vertex for the algorithm ";
        cin >> option;
        finishedVertices[0] = option;
        counter++;
        prim();
        print();
        //display();
        cout << "Press 1 to run the algorithm with a different starting vertex or 2 to go back to the main menu ";
        cin >> option2;
      }
    }
  }
  return 0;
}