#include <iostream>
#include <string>
#include <vector>
#include "WeightedGraph.h"
#include "WeightedEdge.h"
using namespace std;

/** Print tree */
template <typename T>
void printTree(Tree &tree, vector<T> vertices)
{
  cout << "\nThe root is " << vertices[tree.getRoot()];
  cout << "\nThe edges are: ";
  for (int i = 0; i < vertices.size(); i++)
  {
    if (tree.getParent(i) != -1)
      cout << " (" << vertices[tree.getParent(i)] << ", "
        << vertices[i] << ")";
  }
}

int main()
{
  // Vertices for graph in Figure 24.1
  string vertices[] = {"Seattle", "San Francisco", "Los Angeles",
    "Denver", "Kansas City", "Chicago", "Boston", "New York",
    "Atlanta", "Miami", "Dallas", "Houston"};

  // Edge array for graph in Figure 24.1
  int edges[][3] = {
    {0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
    {1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
    {2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
    {3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599},
      {3, 5, 1003},
    {4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260},
      {4, 8, 864}, {4, 10, 496},
    {5, 0, 2097}, {5, 3, 1003}, {5, 4, 533},
      {5, 6, 983}, {5, 7, 787},
    {6, 5, 983}, {6, 7, 214},
    {7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
    {8, 4, 864}, {8, 7, 888}, {8, 9, 661},
      {8, 10, 781}, {8, 11, 810},
    {9, 8, 661}, {9, 11, 1187},
    {10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
    {11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
  };
  const int NUMBER_OF_EDGES = 46; // 46 edges in Figure 24.1

  // Create a vector for vertices
  vector<string> vectorOfVertices(12);
  copy(vertices, vertices + 12, vectorOfVertices.begin());

  // Create a vector for edges
  vector<WeightedEdge> edgeVector;
  for (int i = 0; i < NUMBER_OF_EDGES; i++)
    edgeVector.push_back(WeightedEdge(edges[i][0],
    edges[i][1], edges[i][2]));

  WeightedGraph<string> graph1(vectorOfVertices, edgeVector);
  MST tree1 = graph1.getMinimumSpanningTree();
  cout << "The spanning tree weight is " << tree1.getTotalWeight();
  printTree<string>(tree1, graph1.getVertices());

  // Create a graph for Figure 24.3(a)
  int edges2[][3] =
  {
    {0, 1, 2}, {0, 3, 8},
    {1, 0, 2}, {1, 2, 7}, {1, 3, 3},
    {2, 1, 7}, {2, 3, 4}, {2, 4, 5},
    {3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
    {4, 2, 5}, {4, 3, 6}
  }; // 14 edges in Figure 24.3(a)

  const int NUMBER_OF_EDGES2 = 14; // 14 edges in Figure 24.3(a)

  vector<WeightedEdge> edgeVector2;
  for (int i = 0; i < NUMBER_OF_EDGES2; i++)
    edgeVector2.push_back(WeightedEdge(edges2[i][0],
    edges2[i][1], edges2[i][2]));

  WeightedGraph<int> graph2(5, edgeVector2); // 5 vertices in graph2
  MST tree2 = graph2.getMinimumSpanningTree();
  cout << "\nThe spanning tree weight is " << tree2.getTotalWeight();
  printTree<int>(tree2, graph2.getVertices());

  return 0;
}