3
\$\begingroup\$

My knowledge in graph theory is very limited. I have to look for elements in an (undirected) graph who are in the same connected component.

The idea is simple. First, build the graph. Then, allocate a "color" to a point and spread it to its neighbours recursively. Once there are no neighbours to color any more, pick a point without any color and repeat the same process. This ends when all the points have a color.

I wrote the following class :

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

namespace ConnectedComponents
{
    public class UndirectedGraph
    {
        private Dictionary<int, List<int>> _graph;
        private Dictionary<int, int> _colors;

        public UndirectedGraph()
        {
            _graph = new Dictionary<int, List<int>>();
        }

        private int SpreadColorFromPoint(int p1, int color, HashSet<int> visitedVertices)
        {

            if (_colors.ContainsKey(p1))
            {
                _colors[p1] = color;
            }
            else
            {
                _colors.Add(p1, color);
            }

            visitedVertices.Add(p1);

            foreach (int vertex in _graph[p1])
            {
                if (visitedVertices.Contains(vertex)) continue;
                SpreadColorFromPoint(vertex, color, visitedVertices);
            }

            return visitedVertices.Count;
        }

        private void AddEdge(int p1, int p2)
        {
            if (_graph.ContainsKey(p1))
            {
                _graph[p1].Add(p2);
            }
            else
            {
                _graph.Add(p1, new List<int>() { p2 });
            }
        }

        public int Count
        {
            get
            {
                return _graph.Count;
            }
        }

        public void AddUndirectedEdge(int p1, int p2)
        {
            AddEdge(p1, p2);
            AddEdge(p2, p1);
        }

        public void Color()
        {
            int color = 1;
            _colors = new Dictionary<int, int>();
            foreach (int key in _graph.Keys)
            {
                int visited = 0;
                if (!_colors.ContainsKey(key))
                    visited = SpreadColorFromPoint(key, color, new HashSet<int>());
                color++;
            }
        }

        public bool BelongToSameComponent(int p1, int p2)
        {
            if (_colors.ContainsKey(p1) && _colors.ContainsKey(p2))
            {
                return _colors[p1] == _colors[p2];
            }
            else
            {
                return false;
            }
        }

        public int CountConnectedComponents()
        {
            return _colors.Values.Distinct().Count();
        }
    }
}

And the following tests :

namespace ConnectedComponents
{
    class UnitTests
    {
        public bool CountPoints()
        {
            UndirectedGraph myGraph = new UndirectedGraph();
            myGraph.AddUndirectedEdge(1, 2);
            myGraph.AddUndirectedEdge(3, 4);

            bool test1 = myGraph.Count == 4;

            myGraph.AddUndirectedEdge(3, 2);

            bool test2 = myGraph.Count == 4;

            return test1 && test2;
        }

        public bool CountConnectedComponents()
        {
            UndirectedGraph myGraph = new UndirectedGraph();
            myGraph.AddUndirectedEdge(1, 2);
            myGraph.AddUndirectedEdge(3, 4);
            myGraph.Color();

            bool test1 = myGraph.BelongToSameComponent(1, 2);
            bool test2 = myGraph.BelongToSameComponent(3, 4);
            bool test3 = !myGraph.BelongToSameComponent(1, 3);
            bool test4 = myGraph.CountConnectedComponents() == 2;

            myGraph.AddUndirectedEdge(2, 3);
            myGraph.Color();
            bool test5 = myGraph.CountConnectedComponents() == 1;

            return (test1 && test2 && test3 && test4 && test5);
        }
    }
}

I don't really like the Color methods which forces the user to call it every time before calling CountConnectedComponents. Besides, the algorithm is very basic...

Are there libraries doing this already ? Is there another algorithm, simple to implement (performance is not really an issue, this was working with roughly 1000000 elements)

My tests are really poor as well, are there better guidelines to write them ?

\$\endgroup\$
3
\$\begingroup\$

Unit Tests

I can see why you would not like your unit tests. Although it isn't required for you to use a test framework to write unit tests it is helpful to use them because you can run them in isolation and quickly and as an extra bonus visual studio has a nice window showing the status of your unit tests.

MSDN - Run unit tests with Test Explorer

Test Explorer Image from MSDN

Many of the unit test frameworks work on the same premise that you are trying to achieve where you check if a certain condition exists, but they offer a little better form of "Assertions" that give you some more information except true and false.

I also want to point out that you shouldn't write a method in your class that tests its state only unless it makes sense. 9 times out of 10 though it does not. So for instance this method

    public bool BelongToSameComponent(int p1, int p2)
    {
        if (_colors.ContainsKey(p1) && _colors.ContainsKey(p2))
        {
            return _colors[p1] == _colors[p2];
        }
        else
        {
            return false;
        }
    }

I'm going to assume that this isn't used in anyplace other than your unit tests. Part of the reason you wrote it is because your class isn't testable. I would rather see maybe another class created that represents a point on your graph that would contain its point in space and its color. Than you'd return the two points and test that the colors are the same. Some pseudo code.

[Test]
public void ConnectedComponentsHaveSameColor()
{
    var myGraph = new UndirectedGraph();
    myGraph.AddUndirectedEdge(1, 2);
    myGraph.AddUndirectedEdge(3, 4);

    myGraph.Color();

    Assert.That(myGraph[1].Color, Is.EqualTo(myGraph[2].Color));
    Assert.That(myGraph[3].Color, Is.EqualTo(myGraph[4].Color));
    Assert.That(myGraph[1].Color, Is.Not.EqualTo(myGraph[3].Color));
    //...
}

Note that the syntax above is using NUnit

\$\endgroup\$
  • \$\begingroup\$ Thanks ! Never used this feature before, indeed, it is much nicer than having an option to run the tests before running the program... \$\endgroup\$ – RUser4512 Jun 22 '16 at 17:41
3
\$\begingroup\$

I’m not going to comment about tests.

Braces and Casing

Overall good use of braces and casing, though you slip a few times. In your Color method, I would suggest braces inside the foreach:

if (!_colors.ContainsKey(key))
{
    visited = SpreadColorFromPoint(key, color, new HashSet<int>());
}

Naming

Naming could be better, e.g. p1 in methods without a p2 could simple be point. In methods with a p1 and p2, you could use point1 and point2 as names.

Code Changes

In SpreadColorFromPoint, I think this:

else
{
    _colors.Add(p1, color);
}

visitedVertices.Add(p1);

should be:

else
{
    _colors.Add(p1, color);
    visitedVertices.Add(p1);
}

If you are using C# 6.0 or better, the Count property could be shortened to:

public int Count => _graph.Count;

Likewise, CountConnectedComponents could be a one-liner as well.

public int CountConnectedComponents() => _colors.Values.Distinct().Count();

On one hand, this is proper to be a method in that it must take a wee-bit of time for .Distinct().Count(). On the other hand, if _colors was to be small enough, you may consider making it ConnectedComponentsCount property. Note that "Count" in the beginning is a verb and "Count" on the end is a noun.

Color: A verb or a noun?

Speaking of nouns vs verbs, for the Color method, I take issue with the name since whenever I see Color I tend to think of a the Color structure. Perhaps AppyColor or GenerateColors are suitable as action verbs. Granted “color” can be a verb or a noun, but again most developers may think noun.

That said, I don’t see where you do anything useful with visited. Looking at it further, there is no need that SpreadColorFromPoint should return a value. That would shorten up code in the Color (or GenerateColors) method.

\$\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.