4
\$\begingroup\$

I have implemented in C# a graph data structure (undirected graph) using TDD technique, tests are provided upfront. This implementation provides common graph methods also it traverses graph using DFS algorithm. Tests are passing so I guess, implementation is correct. I would appreciate any test case that I might be missing (edge cases) and general code review.

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();
        }
    }
}
\$\endgroup\$
7
\$\begingroup\$
public class Graph

Is there any reason not to make it Graph<TVertex>?


    private char[][] adjecencyMatrix;
    private char[] vertices;

    ...

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

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

I have three related questions:

  1. Why use arrays internally? An IDictionary<TVertex, ISet<TVertex>> captures the essence of a graph and gives you straightforward lookups.

  2. Even if you are using arrays internally, why expose arrays? A public getter which returns an array is implicitly also a public setter, because the code which calls it can mutate your internal state.

  3. Why is AdjecencyMatrix exposed at all?


    public Graph()
    {
    }

    public void initGraph(char[][] edges)

This is an anti-pattern. The constructor should give a fully initialised object, and if that's not possible then it should be hidden and public access should be via a builder or other factory.

With a graph I would be tempted to make the constructor private and have static factory methods to build from a set of edges (as here), from adjacency lists, and from an adjacency matrix.


    {
        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();
        }
    }

Naming. adjacency has two as. And what you have here isn't an adjacency matrix: that's indexed by two vertices and contains bools. This is the adjacency lists representation of a graph.

See earlier comments about use of dictionary and set rather than array.


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

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

In addition to earlier comments, have you considered making the neighbours of a vertex be an indexed property? I think that would be quite a natural notation.


    //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();
    }

I personally don't find Traverse a very descriptive name. DFS would tell me immediately what it's doing. I'm not sure, though, how useful a DFS is which just returns a list of vertices. Most of the time DFS is used as a building block for other algorithms, and they require additional data.

            if (adjecents.Any(x => !result.Contains(x)))
            {
                c = adjecents.Where(x => !result.Contains(x)).ElementAt(0);

I'd always use First() rather than ElementAt(0), and to save doing the search twice I'd rework to

            c = adjecents.Where(x => !result.Contains(x)).FirstOrDefault();
            if (c != default(TElement))
            {

result.Contains(x) does a linear search. For reasonable performance you should use an ISet implementation in parallel to result.


Looking at the DFS implementation, I can spot a missing test case. Consider

    public static char[][] graph4 = new char[][]
    {
        new char [] {'A', 'B'},
        new char [] {'C', 'D'},
    };
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.