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

using namespace std;

int matrix[50][50];
int finishedWeight[50];
int finishedVertices[50];
char* edges[50];
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);
  } 

  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
    }
  }
}

// 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);
  }

  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
    }
  }
} 

//execute the algorithm
void prim(int startingVertex)
{
  cout << "Size = " << size << endl;
  int start = startingVertex;
  int end;
  int weight;
  int minx;
  int miny;
  int minWeight = pow(2, 32) - 1;
  for(int k = 0; k < size; k++)
  {
    finishedVertices[k] = start;
    for(int l = 0; l < size; l++)
    {
      if(matrix[start][l] < minWeight)
      {
        for(int i = 0; i < size; i++)
	{
	   if(matrix[start][l] != finishedVertices[i])
	   {
	     minx = start;
             miny = l;
             minWeight = matrix[minx][miny];
	   }
	 }
      }
    }
  }
  finishedVertices[counter] = minx;
  cout << "counter = " << counter << endl;
  cout << "finished vertices at 0 = " << finishedVertices[0] << endl;
  cout << "finished vertices at 1 = " << finishedVertices[1] << endl;
  finishedWeight[counter] = minWeight;
  cout << "FinishedWeight at 0 = " << finishedWeight[0] << endl;
  cout << "finishedWeight at 1 = " << finishedWeight[1] << endl;
  //edges[counter] = minx + ',' + miny;
  counter++;
  if(counter != size)
    prim(2); // this is just to test to see if another vertex would work
               // really the parameter for this should be the column the lowest
              // weight was in
}

void display()
{
  for(int v = 0; v < size; v++)
  {
    cout << finishedVertices[v];
    for(int w = 0; w < size; w++)
    {
      cout << finishedWeight[w];
    }
  }
}

// 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)
      {
        cout << "Please enter a starting vertex for the algorithm ";
        cin >> option;
        prim(option);
        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)
      {
        cout << "Please enter a starting vertex for the algorithm ";
        cin >> option;
        prim(option);
        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;
}