using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using GraphDataStructure;

namespace Tests
{
    public static class Helper
    {
        public static string ToJoinedString(this char[] array)
        {
            return string.Join(" ", array);
        }
    }

    [TestClass]
    public class Tests
    {
        #region graphs
        public static char[][] graph1 = new char[][] {
                new char [] {'A', 'B'},
                new char [] {'A', 'D'},
                new char [] {'A', 'C'},
                new char [] {'C', 'D'},
                new char [] {'C', 'E'}
            };

        public static char[][] graph2 = new char[][]
        {
            new char [] {'A', 'G'},
            new char [] {'A', 'C'},
            new char [] {'A', 'B'},
            new char [] {'A', 'D'},
            new char [] {'C', 'G'},
            new char [] {'C', 'B'},
            new char [] {'D', 'B'},
            new char [] {'D', 'E'},
            new char [] {'B', 'F'},
        };
        public static char[][] graph3 = new char[][]
        {
            new char [] {'A', 'G'}
        };
        #endregion

        #region graph1
        [TestMethod]
        public void TestGraph1Initialisation()
        {
            var graph = new Graph();
            graph.initGraph(graph1);

            var expectedAdjecencyMatrix = new char[][]
            {
                new char[] { 'B', 'C', 'D' },
                new char[] { 'A' },
                new char[] { 'A', 'D', 'E' },
                new char[] { 'A', 'C' },
                new char[] { 'C' },
            };

            //Testing vertices
            var expectedVertices = new char[] { 'A', 'B', 'C', 'D', 'E' };
            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());

            //Testing adjecency matrix
            int i = 0;
            foreach (var row in expectedAdjecencyMatrix)
                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());
        }

        [TestMethod]
        public void TestGraph1GetAdjecents()
        {
            var graph = new Graph();
            graph.initGraph(graph1);

            var expectedAdjecents = new char[] { 'B', 'C', 'D' };
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());

            expectedAdjecents = new char[] { 'C' };
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('E').ToJoinedString());
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void TestGraph1GetAdjecentsOfNonExistentVertex()
        {
            var graph = new Graph();
            graph.initGraph(graph1);

            graph.getAdjecents('Y');
        }

        [TestMethod]
        public void TestGraph1Traversal()
        {
            var graph = new Graph();
            graph.initGraph(graph1);

            var expectedResult = new char[] { 'A', 'B', 'C', 'D', 'E' } ;
            char[] result = graph.Traverse();

            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());
        }
        #endregion

        #region graph2
        [TestMethod]
        public void TestGraph2Initialisation()
        {
            var graph = new Graph();
            graph.initGraph(graph2);

            var expectedAdjecencyMatrix = new char[][]
            {
                new char[] { 'B', 'C', 'D', 'G' },  //A
                new char[] { 'A', 'C', 'D', 'F' },  //B
                new char[] { 'A', 'B', 'G' },       //C
                new char[] { 'A', 'B', 'E' },       //D
                new char[] { 'D' },                 //E
                new char[] { 'B' },                 //F
                new char[] { 'A', 'C' },            //G
            };

            //Testing vertices
            var expectedVertices = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());

            //Testing adjecency matrix
            int i = 0;
            foreach (var row in expectedAdjecencyMatrix)
                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());
        }

        [TestMethod]
        public void TestGraph2GetAdjecents()
        {
            var graph = new Graph();
            graph.initGraph(graph2);

            var expectedAdjecents = new char[] { 'B', 'C', 'D', 'G' };
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());

            expectedAdjecents = new char[] { 'A', 'B', 'E' };
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('D').ToJoinedString());
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void TestGraph2GetAdjecentsOfNonExistentVertex()
        {
            var graph = new Graph();
            graph.initGraph(graph2);

            graph.getAdjecents('Y');
        }

        [TestMethod]
        public void TestGraph2Traversal()
        {
            var graph = new Graph();
            graph.initGraph(graph2);

            var expectedResult = new char[] { 'A', 'B', 'C', 'G', 'D', 'E', 'F' };
            char[] result = graph.Traverse();

            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());
        }
        #endregion

        #region graph3
        [TestMethod]
        public void TestGraph3Initialisation()
        {
            var graph = new Graph();
            graph.initGraph(graph3);

            var expectedAdjecencyMatrix = new char[][]
            {
                new char[] { 'G' },  //A
                new char[] { 'A' },  //G
            };

            //Testing vertices
            var expectedVertices = new char[] { 'A', 'G' };
            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());

            //Testing adjecency matrix
            int i = 0;
            foreach (var row in expectedAdjecencyMatrix)
                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());
        }

        [TestMethod]
        public void TestGraph3GetAdjecents()
        {
            var graph = new Graph();
            graph.initGraph(graph3);

            var expectedAdjecents = new char[] { 'G' };
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());

            expectedAdjecents = new char[] { 'A'};
            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('G').ToJoinedString());
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void TestGraph3GetAdjecentsOfNonExistentVertex()
        {
            var graph = new Graph();
            graph.initGraph(graph3);

            graph.getAdjecents('Y');
        }

        [TestMethod]
        public void TestGraph3Traversal()
        {
            var graph = new Graph();
            graph.initGraph(graph3);

            var expectedResult = new char[] { 'A', 'G'};
            char[] result = graph.Traverse();

            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());
        }
        #endregion
    }
}


using System;
using System.Collections.Generic;
using System.Linq;

namespace GraphDataStructure
{
    public class Graph
    {
        private char[][] adjecencyMatrix;
        private char[] vertices;

        public Graph()
        {
        }

        public char[] Vertices { get { return vertices; } }

        public char[][] AdjecencyMatrix { get { return adjecencyMatrix;  } }

        public void initGraph(char[][] edges)
        {
            vertices = edges.SelectMany(x => x).Distinct().OrderBy(x => x).ToArray();

            adjecencyMatrix = new char[vertices.Length][];
            for (int j = 0; j < vertices.Length; j++)
            {
                var adjecents = new List<char>();
                foreach(var row in edges)
                {
                    if (row.Contains(vertices[j]))
                        adjecents.Add(row.First(x => x != vertices[j]));
                }
                adjecencyMatrix[j] = adjecents.OrderBy(x => x).ToArray();
            }
        }

        public char[] getAdjecents(char c)
        {
            if (Array.IndexOf(vertices, c) < 0)
                throw new InvalidOperationException("Invalid vertex");

            return adjecencyMatrix[Array.IndexOf(vertices, c)];
        }

        //DFS algorithm
        public char[] Traverse()
        {
            var stack = new Stack<char>();
            var result = new List<char>();
            var c = Vertices[0];
            result.Add(c);
            stack.Push(c);
            while(stack.Count > 0)
            {
                var adjecents = getAdjecents(stack.Peek());
                if (adjecents.Any(x => !result.Contains(x)))
                {
                    c = adjecents.Where(x => !result.Contains(x)).ElementAt(0);
                    result.Add(c);
                    stack.Push(c);
                }
                else
                    stack.Pop();
            }
            return result.ToArray();
        }
    }
}