using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _311_Assignment4_Graph
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph why = new Graph("A");
            why.BuildTestGraph();
            Console.Read();
        }

        public class Graph
        {
            Vertex head;
                // I struggled here figuring out if graphs should contain lists of
                // all its vertices and edges, so I went with an approach I was familiar with
                // from working with linked lists
            public Graph(string dataOfStartVertex)
            {
                head = new Vertex(dataOfStartVertex);
            }
            public class Edge
            {
                public Vertex linkOne;
                public Vertex linkTwo;
                public int label;
                    // 0 = unexplored
                    // 1 = discovery edge
                    // 2 = back edge

                public Edge(Vertex origin, string newVertexData)
                {
                    linkOne = origin;
                    linkTwo = new Vertex(newVertexData);
                    //linkTwo.connectedEdges.Add(this); // Probably should have done it this way
                    label = 0;
                }
                public Edge(Vertex origin, Vertex destination)
                {
                    linkOne = origin;
                    linkTwo = destination;
                }
            }
            public class Vertex
            {
                public List<Edge> connectedEdges;
                public string storedData;
                public int label;
                    // 0 = unexplored
                    // 1 = visted

                public Vertex(string data)
                {
                    storedData = data;
                    connectedEdges = new List<Edge>();
                }
            }
            public void PrintVertexInformation(Vertex vertex)
            {
                if (vertex.storedData != "Head")
                {
                    Console.WriteLine("> Now visiting node: " + vertex.storedData);
                    Console.WriteLine("-> Exploring edges and listing them...");
                    int edgeCount = 1;
                    foreach (Edge edge in vertex.connectedEdges)
                    {
                        if (edge.label != 1)
                        {
                            if (edge.linkTwo.label == 1 && edge.linkOne.label == 1)
                            {
                                edge.label = 2;
                            }
                        }
                        switch (edge.label)
                        {
                            case 0:
                                Console.WriteLine("--> #" + edgeCount + " is an UNEXPLORED edge linking vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                //Console.WriteLine("---> Links vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                break;
                            case 1:
                                Console.WriteLine("--> #" + edgeCount + " is a DISCOVERY edge linking vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                //Console.WriteLine("---> Links vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                break;
                            case 2:
                                Console.WriteLine("--> #" + edgeCount + " is a BACK edge linking vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                //Console.WriteLine("---> Links vertices " + edge.linkOne.storedData + "-" + edge.linkTwo.storedData);
                                break;
                        }
                        edgeCount++;
                    }
                    Console.WriteLine();
                }
            }
            public void BuildTestGraph()
                // Lazy method to build the graph from the DFS powerpoint
                // I struggled with figuring out a good way to build a user-defined graph
                // After I realized that wasn't necessary for the assignment, I chose this method
                // I also had a problem deciding if I should have a head node pointing to A (or whatever starting node)
            {
                head.connectedEdges.Add(new Edge(head, "B"));
                head.connectedEdges[0].linkTwo.connectedEdges.Add(head.connectedEdges[0]);
                // Adds the edge linking A-B to B's list
                head.connectedEdges.Add(new Edge(head, "C"));
                head.connectedEdges[1].linkTwo.connectedEdges.Add(head.connectedEdges[1]);
                // Adds the edge linking A-C to C's list
                head.connectedEdges[0].linkTwo.connectedEdges.Add
                    (new Edge(head.connectedEdges[0].linkTwo, head.connectedEdges[1].linkTwo));
                // Creates the edge linking B-C, adds it to B's list
                head.connectedEdges[1].linkTwo.connectedEdges.Add(head.connectedEdges[0].linkTwo.connectedEdges[1]);
                // Adds the edge linking B-C to C's list
                head.connectedEdges.Add(new Edge(head, "D"));
                head.connectedEdges[2].linkTwo.connectedEdges.Add(head.connectedEdges[2]);
                // Adds the edge linking A-D to D's list
                head.connectedEdges[2].linkTwo.connectedEdges.Add
                    (new Edge(head.connectedEdges[2].linkTwo, head.connectedEdges[1].linkTwo));
                // Creates the edge linking C-D, adds it to D's list
                head.connectedEdges[1].linkTwo.connectedEdges.Add(head.connectedEdges[2].linkTwo.connectedEdges[1]);
                // Adds the edge linking C-D to C's list
                head.connectedEdges.Add(new Edge(head, "E"));
                head.connectedEdges[3].linkTwo.connectedEdges.Add(head.connectedEdges[3]);
                // Adds the edge linking A-E to E's list
                head.connectedEdges[3].linkTwo.connectedEdges.Add
                    (new Edge(head.connectedEdges[3].linkTwo, head.connectedEdges[1].linkTwo));
                // Creates the edge linking C-E, adds it to E's list
                head.connectedEdges[1].linkTwo.connectedEdges.Add(head.connectedEdges[3].linkTwo.connectedEdges[1]);
                    // Adds the edge linking C-E to C's list

                DepthFirstSearch(this, head);
            }
            public void DepthFirstSearch(Graph graph, Vertex vertex)
            {
                vertex.label = 1; // Marks vertex as explored
                PrintVertexInformation(vertex); // Displays information about vertex
                foreach (Edge edge in vertex.connectedEdges)
                {
                    if (edge.label == 0) // If the edge is unexplored...
                    {
                        Vertex next = edge.linkTwo;
                        if (next.label == 0) // Check the vertex it points to
                        {
                            // If it is also unexplored...
                            edge.label = 1; // Set to discovery edge
                            DepthFirstSearch(graph, next); // Then dfs it
                        }
                        else // If the vertex is already explored then its a back edge
                        {
                            edge.label = 2;
                        }
                    }
                }
            }
            //public void BuildTestGraphWithUserInput()
            //{
            //    Graph graph = new Graph();
            //    head.connectedEdges.Add(new Edge(head, "A"));
            //    DoStuff(graph, head.connectedEdges[0].linkTwo);
            //}
            //public void DoStuff(Graph graph, Vertex vertex)
            //{
            //    PrintVertexEdges(vertex);
            //    int choice = RequestGraphInput();
            //}
            //public void RequestGraphInput()
            //{

            //}
        }
    }
}