Undirected graph implementation

Question

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

Peter Taylor · Accepted Answer · 2017-03-28 13:20:36Z

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:

Why use arrays internally? An IDictionary<TVertex, ISet<TVertex>> captures the essence of a graph and gives you straightforward lookups.
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.
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'},
    };

Stack Exchange Network

Undirected graph implementation

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Undirected graph implementation

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions