using System;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Collections.Generic;
namespace lab3
{


class lab3
{

  static void Main()
  {
    matrixGraph myMatrixGraph=new matrixGraph(14);          //initialize a graph of size 14 as requested by the lab manual
    listGraph myListGraph=new listGraph(14);
    //THIS IS THE GRAPH DEPICED IN THE LAB. A-N are depicted as 0-13
    Tuple<int, int, int>[] edges ={
      Tuple.Create(0,1,1),    //A, B
      Tuple.Create(0,3,1),    //A, D
      Tuple.Create(3, 4, 1),  //D, E
      Tuple.Create(1, 2, 1),  //B, C
      Tuple.Create(2, 12, 1),         //C,M
      Tuple.Create(12, 11, 1),         //M, L
      Tuple.Create(11, 10, 1),         //L, K
      Tuple.Create(10, 7, 1),  //K, H
      Tuple.Create(7, 5, 1),  //H, F
      Tuple.Create(5, 4, 1),  //F, E
      Tuple.Create(3, 5, 1),  //D,F
      Tuple.Create(3, 6, 1),  //D,G
      Tuple.Create(7, 8, 1),   //H, I
      Tuple.Create(8, 9, 1),   //I, J
      Tuple.Create(6, 9, 1),   //G,J
      Tuple.Create(9, 10, 1),   //J,K
      Tuple.Create(9, 13, 1),   //J,N
      Tuple.Create(2, 13, 1),   //C,N
      Tuple.Create(2, 12, 1),   //C,M
      Tuple.Create(3, 13, 1),   //D, N
      Tuple.Create(12, 13, 1),   //N, M
      Tuple.Create(7, 6, 1)};   //h, g

for( int index=0;index<edges.Length;index++)  //CONSTRUCT THE GRAPH FROM THE GIVEN DATA
  {
  myMatrixGraph.addEdgeUndirected(edges[index].Item1, edges[index].Item2, edges[index].Item3);
  myListGraph.addEdgeUndirected(edges[index].Item1, edges[index].Item2);
  }
//myMatrixGraph.breadthFirstSearchMatrix(0);
//myListGraph.breadthFirstSearchList(0);
int[] p={30, 4, 8, 5, 10, 25, 15};

Stopwatch timer= new Stopwatch();
timer.Start();
Console.WriteLine(matrixChainOrderDP(p));
timer.Stop();
Console.WriteLine("Time for Dynamic Programming MCM: {0}", timer.Elapsed);
timer.Reset();


timer.Start();
Console.WriteLine(matrixChainOrderNaiveHelper(p));
timer.Stop();
Console.WriteLine("Time for Naive MCM: {0}", timer.Elapsed);
timer.Reset();



}//END MAIN




//Dynamic Programming version of MCM optimizatization algorithm
static int matrixChainOrderDP(int[] p)    //returns an integer which represents the minimum number of operations required to multiply the matrix chain
{
  int length=p.Length;
  int[,] brackets = new int[length, length];        //Array storing where brackets are located
  int[,] grid = new int[length, length];  //stores the grid of minimum operations for each product
  int i;  //i keeps track of x axis values
  int j;  //j keeps track of y axis values
  int k;  //k is the iteration count to take minimum for each square
  int L;  //L is the length of each chain
  int q;  //q is a temporary value used to compare to the result of each k iteration to the current minimum stored in the matrix grid

  for(i=1;i<length;i++)
  {
    grid[i,i]=0;              //set squares where i=j to zero
  }

  //indices of the matrix grid contain the minimum number of operations required to calculate their product
for(L=2; L<length; L++)
  {

    for(i=1; i<length-L+1;i++)
    {
        j=i+L-1;
        if(j==length)//if we finished our last j
        {
          continue;
        }
        grid[i,j]=int.MaxValue;  //initialize values to infinity before calculating their values
        for(k=i;k<=j-1;k++)//Calculate value for each K
        {
          q = grid[i, k] + grid[k+1, j] + p[i-1] * p[k] * p[j]; //APPLY THE FORMULA FOR EACH K AND KEEP THE MINIMUM

          if(q<grid[i,j])  //if this is smaller than the previous number of operations, update the result
          {
            grid[i, j]=q;
            brackets[i,j]=k;  //brackets holds the locations of parentheses in the result
          }
        }

    }

  }

  char name='A';
  printParenthesized(1, length-1, length, brackets, ref name);//print reuslt with matix names starting at A.
return grid[1, length-1];//return the top right square which contains the minimum operations for the full multiplication process
}

static void printParenthesized(int i, int j, int length, int[,] brackets, ref char name)
{
  if(i==j)
  {
    Console.Write(name++);
    return;
  }
  Console.Write("(");


  printParenthesized(i, brackets[i,j], length, brackets, ref name);   //recursively prints the final locations of the parentheses

  printParenthesized(brackets[i,j]+1, j, length, brackets, ref name);

  Console.Write(")");
}




static int matrixChainOrderNaiveHelper(int[] p)
{
  return matrixChainOrderNaive(p, 1, p.Length-1);
}



//RECURSIVE MEMOIZED SOLUTION
static int matrixChainOrderNaive(int[] p, int i, int j)  //This recursively solves the problem without using a lookup table (repeated calculations)
{
  if(i==j)
  {return 0;}
  int min=int.MaxValue;   //sets the minimum value to  infinity

  for(int k=i; k<j;k++) //calculate for each k value
  {
      int operations=matrixChainOrderNaive(p,i,k)+matrixChainOrderNaive(p,k+1, j)+p[i-1]*p[k]*p[j]; //recursively calculate the value of each square
      if(operations<min)  //get min values for each k
      {
        min=operations;
      }
  }

return min;
}






//recursive Naive MCM function
static int matrixChainOrderNaive(int[] p, int i, int j)  //This recursively solves the problem without using a lookup table (repeated calculations)
{
  if(i==j)
  {return 0;}
  int min=int.MaxValue;   //sets the minimum value to  infinity

  for(int k=i; k<j;k++) //calculate for each k value
  {
      int operations=matrixChainOrderNaive(p,i,k)+matrixChainOrderNaive(p,k+1, j)+p[i-1]*p[k]*p[j]; //recursively calculate the value of each square
      if(operations<min)  //get min values for each k
      {
        min=operations;
      }
  }

return min;
}
}//END CLASS










//GRAPH STUFF FUNCTIONS

//BUILD GRAPH MATRIX STYLE
public class matrixGraph
{
private int[ , ] myGraph;
private int edgeCount;
  public matrixGraph(int numNodes)  //builds matrix of size numNodes x numNodes
  {
   myGraph=new int[numNodes,numNodes];  //collection of weighted edges
   edgeCount=0;                                    //initializes edge count to zero
  }

  public void addEdgeUndirected(int node1, int node2, int weight)    //updates weight of edge between two nodes, undirected
  {
    myGraph[node1,node2]=weight;  //sets weigt at selected index
    myGraph[node2,node1]=weight;
    edgeCount++;                  //incriments edge count
  }

  public int getWeight(int node1, int node2)                  //gets node at selected index
  {
    return myGraph[node1,node2];
  }









  public int[] breadthFirstSearchMatrix(int startNode)               //Breadth first search for adjacency matrix!
  {
    int[] result=new int[myGraph.GetLength(0)];
    bool[] visited = new bool[myGraph.GetLength(0)];//This Queue contains nodesthat have been visited in our search
    Queue<int> adjacent= new Queue<int>();//This is the Queue of nodes adjacent to current node
    for(int i=0;i<myGraph.GetLength(0);i++)
    {
      visited[i]=false;
    }
    visited[startNode]=true;             //ADD the start node to the visited Queue
    adjacent.Enqueue(startNode);        //enqueue the starting node
    int current;
    int resultCount=0;


    while(adjacent.Count!=0)              //While there are still nodes to check
    {
      //Deque,Add to result
      current=adjacent.Dequeue();
      result[resultCount]=current;
      resultCount++;
      Console.WriteLine(current);
      //Add edges adjacent to current
      for(int index=0;index<myGraph.GetLength(0);index++)
      {
        if(myGraph[current, index]!=0 && visited[index]==false)
        {
          //Console.WriteLine("{0} has been added to queue", index);
          //set it to visited
          visited[index]=true;
          //enqueue it
          adjacent.Enqueue(index);
        }
      }
                          //if current edge exists (is not zero)
                          //Add it to adjacent

    }

    return result;                      //Return the result of BFS
  }







  public void printEdges()
  {
    for(int xAxisIndex=0;xAxisIndex<myGraph.GetLength(0);xAxisIndex++)
      {
        for(int yAxisIndex=0; yAxisIndex<myGraph.GetLength(1);yAxisIndex++)
        {
          if(getWeight(xAxisIndex, yAxisIndex)!=0)
          {
            Console.WriteLine("{0}, {1} weight is: {2}", xAxisIndex, yAxisIndex, getWeight(xAxisIndex, yAxisIndex));
          }
        }
      }
  }

}



//ADJACENCY LIST Graph
public class listGraph
{
private Queue<int>[] myGraph;
private int edgeCount;
  public listGraph(int numNodes)                    //builds array of lists
  {
   myGraph=new Queue<int>[numNodes];               //collection of edges
   edgeCount=0;
   for(int temp=0;temp<myGraph.Length;temp++)
   {
     myGraph[temp]= new Queue<int>();
   }                                  //initializes edge count to zero
  }

  public void addEdgeUndirected(int node1, int node2)    //adds edge between two nodes, undirected
  {
    myGraph[node1].Enqueue(node2);
    myGraph[node2].Enqueue(node1);
    edgeCount++;                  //incriments edge count
  }











  public int[] breadthFirstSearchList(int startNode)               //Breadth first search for adjacency matrix!
  {
    int[] result=new int[myGraph.Length];
    bool[] visited = new bool[myGraph.Length];//This Queue contains nodesthat have been visited in our search
    Queue<int> adjacent= new Queue<int>();//This is the Queue of nodes adjacent to current node

    for(int i=0;i<myGraph.Length;i++)
    {
      visited[i]=false;               //initialize the visited array to false
    }

    visited[startNode]=true;             //ADD the start node to the visited Queue
    adjacent.Enqueue(startNode);        //enqueue the starting node
    int current;
    int resultCount=0;

    while(adjacent.Count!=0)
    {
        //Dequeue ,print and add to resultant array
        current=adjacent.Dequeue();
        Console.WriteLine(current);
        result[resultCount]=current;

        while(myGraph[current].Count!=0)
        {
          int adj=myGraph[current].Dequeue();
          if(visited[adj]!=true)
          {
            visited[adj]=true;
            adjacent.Enqueue(adj);

          }

        }


    }



    return result;                      //Return the result of BFS
  }









}






















  }//END NAMESPACE