using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace DSGraph
{
    public class Graph
    {

        private ArrayList nodes;
        public int numOfNodes;
        public int numOfLinks;

        public Graph()
        {
            this.nodes = new ArrayList();
        }
        public void addNode(Node incoming)
        {
            numOfLinks += incoming.getAll().Count;
            numOfNodes++;
            this.nodes.Add(incoming);
        }

        public bool addLink(Link l)
        {
            for (int x = 0; x < this.nodes.Count; x++)
            {
                if (((Node)this.nodes[x]).ID == l.startNodeID)
                {
                    Node temp = ((Node)this.nodes[x]);
                    temp.addLink(l);
                    this.nodes[x] = temp;
                    this.numOfLinks++;

                    return true;
                }
            }
            return false;
        }

        public bool BellmanFord(int source)
        {
            StartBFA(source);

            //run first pass
            for (int x = 1; x < this.nodes.Count; x++)
            {
                //keep going
                for (int y = 0; y < this.nodes.Count; y++)
                {
                    //check paths per edge
                    for (int z = 0; z < ((Node)this.nodes[y]).links.Count; z++)
                    {
                        //look edge for pathing improvements
                        predicateChange(y, ((Link)((Node)this.nodes[y]).links[z]).endNodeID, ((Link)((Node)this.nodes[y]).links[z]).weight);

                    }
                }
            }
            //check for negative 
            for (int y = 0; y < this.nodes.Count; y++)
            {
                for (int z = 0; z < ((Node)this.nodes[y]).links.Count; z++)
                {
                    if (((Node)this.nodes[((Link)((Node)this.nodes[y]).links[z]).endNodeID]).data >
                        ((Node)this.nodes[y]).data + ((Link)((Node)this.nodes[y]).links[z]).weight)
                    {
                        return false;
                    }
                }

            }
            return true;
        }


        private void predicateChange(int y, int z, float weight)
        {
            //if reaching node v from node u is cheaper than cheapest known route 
            //set u as predicate of v and update distance to v
            if (((Node)this.nodes[z]).data > ((Node)this.nodes[y]).data + weight)
            {
                Node temp = ((Node)this.nodes[z]);
                temp.data = (int)((Node)this.nodes[y]).data + (int)weight;
                temp.predicate = y;
            }
        }

        private void StartBFA(int source)
        {
            Node temp;
            for (int z = 0; z < this.nodes.Count; z++)
            {
                temp = (Node)this.nodes[z];
                temp.data = int.MaxValue;
                temp.predicate = -1;
                this.nodes[z] = temp;
            }
            temp = (Node)this.nodes[source];
            temp.data = 0;
            this.nodes[source] = temp;
        }
        public ArrayList printAllRoutes()
        {
            ArrayList printable = new ArrayList();
            for (int x = 0; x < this.nodes.Count; x++)
            {
                printable.Add(this.printRoute(x));
            }

            return printable;
        }
        public string printRoute(int destination)
        {
            string returnString = "";
            string returnString2 = "";
            string returnString3 = "";

            int prev;
            int totalCost;
            prev = ((Node)this.nodes[destination]).predicate;
            returnString += "Starting at Node: " + (((Node)this.nodes[destination]).ID + 1);
            totalCost = ((Node)this.nodes[destination]).data;
            if (prev != -1)
            {
                while (prev != -1)
                {
                    returnString2 += " to " + (((Node)this.nodes[prev]).ID + 1);
                    
                    prev = ((Node)this.nodes[prev]).predicate;

                }
            }
            returnString3 += ":: Total Cost = " + totalCost;
            Console.Write(returnString);
            Console.Write(returnString2);
            Console.WriteLine(returnString3);
            return returnString;
        }

       
    }
}