14
\$\begingroup\$

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled.

I tried to implement the Dijkstra's algorithm using TDD. This algorithm is designed to find the fastest route to reach all nodes of a graph. Right now, I'm concerned about if I implemented the algorithm with the good angle. I tested it (obviously) and all my tests passes, so I'm pretty confident the algorithm works, I'm just not sure if it's the way it should be written.

Those are the two classes I used to represent the graphs :

[DebuggerDisplay("{Name}")]
public class Node
{
    public string Name { get; }
    public ICollection<Link> Links { get; }

    public Node(string name)
    {
        if (String.IsNullOrWhiteSpace(name)) throw new ArgumentNullException(nameof(name));

        Name = name;
        Links = new Collection<Link>();
    }

    public override bool Equals(object obj)
    {
        Node node = obj as Node;
        if (node == null) return false;

        return Name.Equals(node.Name);
    }

    public override int GetHashCode()
    {
        return Name.GetHashCode();
    }

    /// <summary>
    /// Creates links betwen two nodes
    /// </summary>
    /// <param name="a">First node</param>
    /// <param name="b">Second node</param>
    /// <param name="distance">Distance between nodes</param>
    /// <remarks>There is no order in the nodes</remarks>
    public static void Join(Node a, Node b, int distance)
    {
        if (a == null) throw new ArgumentNullException("a");
        if (b == null) throw new ArgumentNullException("b");

        Link linkAToB = new Link(a, b, distance);
        Link linkBToA = new Link(b, a, distance);

        a.Links.Add(linkAToB);
        b.Links.Add(linkBToA);
    }
}

[DebuggerDisplay("({From.Name}) to ({To.Name}), Distance : {Distance}")]
public class Link
{
    public Guid Id { get; } = Guid.NewGuid();

    public Node From { get; }
    public Node To { get; }
    public int Distance { get; }

    public Link(Node from, Node to, int distance)
    {
        if (from == null) throw new ArgumentNullException("from");
        if (to == null) throw new ArgumentNullException("to");

        From = from;
        To = to;
        Distance = distance;
    }

    public bool ConnectsSameNodes(Link other)
    {
        if (other == null) throw new ArgumentNullException("other");

        bool connectsSameFrom = other.From.Equals(From) || other.To.Equals(From);

        return connectsSameFrom && (other.From.Equals(To) || other.To.Equals(To));
    }

    public override bool Equals(object obj)
    {
        Link link = obj as Link;
        if (link == null) return false;

        return Id == link.Id;
    }

    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
}

This is the algorithm's implementation :

public interface IGraphSolverStrategy
{
    IEnumerable<Link> Solve(Node head);
}

class LinkDistanceComparer : IComparer<Link>
{
    public int Compare(Link x, Link y)
    {
        if (y == null) throw new ArgumentNullException("y");
        if (x == null) throw new ArgumentNullException("x");

        return Math.Sign(x.Distance - y.Distance);
    }

}

public class DijkstraSolverStrategy : IGraphSolverStrategy
{
    public IEnumerable<Link> Solve(Node head)
    {
        if (head == null) throw new ArgumentNullException(nameof(head));

        var orderedLinks = new SortedSet<Link>(new LinkDistanceComparer());
        AddLinksToSet(orderedLinks, head.Links);
        var traveledLinks = new List<Link>();

        while (orderedLinks.Count != 0)
        {
            var link = orderedLinks.ElementAt(0);
            orderedLinks.Remove(link);

            if (traveledLinks.Any(l => l.To.Equals(link.To))) continue;

            traveledLinks.Add(link);
            var linksToAdd = link.To.Links.Where(l => !l.ConnectsSameNodes(link));
            AddLinksToSet(orderedLinks, linksToAdd);
        }

        return traveledLinks;
    }

    private static void AddLinksToSet(SortedSet<Link> linkSet, IEnumerable<Link> linksToAdd)
    {
        foreach (var item in linksToAdd)
        {
            linkSet.Add(item);
        }
    }
}

Basically, I start with the head node, add the links from this node to a SortedSet then pick the smallest link. The I remove the current link from the set, add the links of the new node, pick the smallest link, and repeat. I make sure there's no closing loops by assuring a link that has the same To node cannot be in the set twice.

Since I used TDD, I thought including my unit tests would be a good move :

[TestFixture]
public class DijsktraSolverStrategyTest
{
    private DijkstraSolverStrategy solver = new DijkstraSolverStrategy();

    #region Helpers

    private static Node CreateHeadWithChilds(params int[] nodesDistance)
    {
        var head = new Node("head");

        for (int i = 0; i < nodesDistance.Length; i++)
        {
            var distance = nodesDistance[i];
            var child = new Node($"child {i + 1}");
            Node.Join(head, child, distance);    
        }

        return head;
    }

    private static Node CreateHeadWithTriangleLink(int triangleDistance, params int[] nodesDistance)
    {
        var head = CreateHeadWithChilds(nodesDistance);
        var otherNodes = head.Links.Select(l => l.To);
        Node.Join(otherNodes.ElementAt(0), otherNodes.ElementAt(1), triangleDistance);

        return head;
    }


    #endregion

    [Test]
    public void Solve_NullHead()
    {
        Assert.Throws<ArgumentNullException>(() => solver.Solve(null));
    }

    [Test]
    public void Solve_OneNode_ReturnsEmptyList()
    {
        //Build
        var head = new Node("Node");
        var expected = new List<Link>();

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TwoNodes_ReturnsLinkBetweenNodes()
    {
        //Build
        var head = CreateHeadWithChilds(1);
        var expected = new []{ head.Links.Single() };

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TwoNodesWithTwoLinks_PicksFastestLink()
    {
        //Build
        const int smallestDistance = 2;
        var head = CreateHeadWithChilds(smallestDistance);
        Node.Join(head, head.Links.Single().To, smallestDistance + 1);
        var expected = head.Links.Where(l => l.Distance == smallestDistance);

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);            
    }

    [Test]
    public void Solve_HeadWithMultipleChilds_TravelsByOrder()
    {
        //Build
        var distances = new []{ 5, 7, 4 };
        var head = CreateHeadWithChilds(distances);
        var expected = head.Links.OrderBy(l => l.Distance).ToList();

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TriangleNodes_DoesntCloseTheLoop()
    {
        //Build
        var distances = new []{ 5, 7 };
        var head = CreateHeadWithTriangleLink(3, distances);
        var unexpected = head.Links.Single(l => l.Distance == 7);

        //Test
        var links = solver.Solve(head);

        //Assert
        CollectionAssert.DoesNotContain(links, unexpected);
    }

    [Test]
    public void Solve_ThreeLevelHierarchyWithPossibleLoop()
    {
        var distances = new int[]{ 1, 700000 };
        var head = CreateHeadWithTriangleLink(2, distances);
        var thirdLevelNode = new Node("3rd child");
        Node.Join(head.Links.First().To, thirdLevelNode, 3);
        var expected = new List<Link>
        {
            head.Links.Single(l => l.Distance == 1),
            head.Links.First().To.Links.Single(l => l.Distance == 2),
            head.Links.First().To.Links.Single(l => l.Distance == 3),
        };

        var actual = solver.Solve(head);

        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_InvertedFromTo_TravelIsNonDirectional()
    {
        //Build
        var head = CreateHeadWithChilds(10);
        var otherNode = head.Links.Single().To;
        var thirdNode = new Node("case");
        Node.Join(thirdNode, otherNode, 5);
        var expected = new List<Link>(){ head.Links.Single(), otherNode.Links.Single(l => l.Distance == 5) };

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Something to be aware of is that SortedSet uses the IComparable implementation to determine equality. So if you add two items which compare to 0, they won't both get added to the set, even if itemOne.Equals(itemTwo) is false \$\endgroup\$ – Ben Aaronson Dec 25 '15 at 0:44
  • \$\begingroup\$ Oh that's interesting, thanks for the information \$\endgroup\$ – IEatBagels Dec 25 '15 at 1:23
  • \$\begingroup\$ Also, what exactly do you mean by finding the shortest route to every node? For example in Solve_ThreeLevelHierarchyWithPossibleLoop the result is "head->child 1, child 1 -> child 2, child 1 -> child 3" But that's not a "route" in the sense of something you could walk, because you don't count going back from child 2 to child 1. \$\endgroup\$ – Ben Aaronson Dec 25 '15 at 11:12
  • \$\begingroup\$ @BenAaronson Maybe the term "route" isn't the good one then, but it's how the algorithm works. \$\endgroup\$ – IEatBagels Dec 26 '15 at 23:23
  • \$\begingroup\$ Yeah I'm not trying to nitpick terminology, I just want to understand what the output is supposed to represent \$\endgroup\$ – Ben Aaronson Dec 26 '15 at 23:57
6
+200
\$\begingroup\$

I've been thinking this over for a while now and I'm pretty sure you're not implementing Dijkstra's algorithm (which is the shortest path between two nodes in a graph). It looks like you're computing a minimum spanning tree (set of edges connecting all nodes with minimal cost).

Some additional remarks:

  1. Link is an odd name - more generally the term Edge is used for a connection of two nodes in a graph.

  2. I think your abstraction is a bit too leaky - the algorithm needs to know quite a bit about the internals of the nodes and links (I'm referring to things like this link.To.Links.Where(l => !l.ConnectsSameNodes(link)).

    I would stipulate you could implement a Graph object with the following public interface and still create independent graph algorithms:

    class Graph<TNode> : IEnumerable<TNode>
    {
        // adds an edge between two nodes with the provided cost
        // creates the nodes if not present
        public Graph<TNode> AddEdge(TNode from, TNode to, int cost)
        {
        }
    
        // returns a list of nodes connected to the source via an edge and the associated cost
        public IEnumerable<Tuple<TNode, int>> GetEdges(TNode source)
        {
        }
    
        // plus IEnumerable<TNode> implementation - enumerate all nodes in the graph
    }
    

    This has the advantages that:

    1. Users can define their own node types and associate any meta data they like with it.
    2. The internal implementation of how nodes and edges are stored is hidden from the user as they do not have to concern themselves with it - neither should they.

Update:

To make it clear and summarize the comments left by @BenAaronson as well: Dijkstra's algorithm as explained on wikipedia finds the shortest path between two nodes in a graph. In which case you would expect having to provide a start and a end node for the algorithm. If your goal was to find all shortest paths from a given node to any other node via Dijkstra then this isn't what you're doing.

A simple example would be this graph:

  A -6-> D
  |      ^
  5      |
  |      1
  v      |
  B -2-> C

You algorithm yields the sequence A -> B, B -> C, C -> D with a total cost of 7 which is indeed the set of edges connecting all nodes with minimal cost. If you were to use Dijkstra's algorithm to compute all shortest paths from A to every other node you would get: A -> B, A -> B -> C, A -> D at cost 13 (if you do not count A -> B twice) since the path with the minimal cost from A to D is indeed the edge with cost 6.

So your implementation finds the set of all edges so that all nodes are connected with the minimal cost. This, as mentioned above, is typically called a minimum spanning tree for which several algorithms exist, most notably Prim's algorithm and Kruskal's algorithm.

I haven't checked it in detail but it looks like your algorithm essentially is an implementation of Kruskal's algorithm. So it's not entirely wrong - it just isn't the algorithm you set out to implement.

You could rename your implementation to KruskalSolverStrategy and try again with Dijkstra (if you need help with that then Stackoverflow would be the better place to ask since CodeReview is about reviewing existing code).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the interesting answer. Though I'd like to know what doesn't fit in my code to consider it a Dijkstra implementation? I mean, if I were to have a GUI over my algorithm it'd look pretty much the same as the Wikipedia's one. \$\endgroup\$ – IEatBagels Dec 28 '15 at 16:31
  • 3
    \$\begingroup\$ @TopinFrassi Dijkstra's algorithm finds the shortest path between a source and a destination node. It does that by maintaining the shortest known ("tentative") distance between every node and the source, and by expanding the nodes in a certain order. As far as I can see, yours doesn't find a path, doesn't maintain a tentative distance, and expands in a different order. \$\endgroup\$ – Ben Aaronson Dec 29 '15 at 0:34
  • \$\begingroup\$ @BenAaronson See, that's the kind of thing I'd like an answer to explain. :p As I did miss something in the algorithm. \$\endgroup\$ – IEatBagels Dec 29 '15 at 1:13
  • 1
    \$\begingroup\$ @TopinFrassi: I've expanded my answer to hopefully provide a clearer picture. \$\endgroup\$ – ChrisWue Dec 29 '15 at 2:16
  • \$\begingroup\$ I've decided to award the bounty now. Implementing the Graph<T> has lead to really nice results and about 10 refactoring commits. Plus well, you pointed out the main point about the algorithm. Thanks alot. \$\endgroup\$ – IEatBagels Dec 31 '15 at 17:15
4
\$\begingroup\$

Nest and Link should implement IComparable<T>

Then LinkDistanceComparer can use them. This is the single responsibility principle in action.

public int Compare(Link x, Link y) {
    // ...
    return x.CompareTo(y);
}

And be sure to implement IComparable<T> not IComparable. The generic gets you type safety.

public int CompareTo (object other)   // IComparable
public int CompareTo (Link other )    // IComparable<T>

Implement IEquatable<Node> and IEquatable<Link>

`IEquatable MSDN documentation:

The IEquatable interface is used by generic collection objects such as Dictionary, List, and LinkedList when testing for equality in such methods as Contains, IndexOf, LastIndexOf, and Remove. It should be implemented for any object that might be stored in a generic collection.

public bool Equals (Node other) {

  if (other == null) return false;

  return this.Name.Equals(other.Name);
}

What about object.Equals override? Again, MSDN:

If you implement IEquatable, you should also override the base class implementations of Object.Equals(Object) and GetHashCode so that their behavior is consistent with that of the IEquatable.Equals method.

public bool override Equals (object other) {
    if (!other is Node ) return false;
    return Equals ((Node)other));
}

Exceptions

Use Exception.Data to capture context. It will be very handy to know parameter values when things blow up.

To facilitate the above, Node and Link should override ToString(). Then you can do this.

new whateverException() {
    Data = {
         { "Node A" , NodeA.ToString() }
        ,{ "Node B", NodeB.ToString() }
    }  
}

Refactor DijkstraSolverStrategy.Solve

I can't see the forest for the trees; it is not structured. What does Solve do? This is high level code and should read as such.

public IEnumerable<Link> Solve(Node head) {
    var orderedLinks = AddLinksToHead( SortedSet<Link>(new LinkDistanceComparer()), head) ;

    // this may be several steps, but I'm not looking at the specific
    // algorithm implementation here.
    // The point is to express the steps.
    // It is not about how many LOC are in a method.
    // It is not about LOC --> yes, I said this twice.

    return BuildShortestPathSet(orderedLinks);
}

Test Deeper

My inclination is to test important things in my basic classes, like the equals overrides.

  • Too simple to bother with? No. Testing is also about future-proofing change.
  • In this particular code Equals is critical. If Equals is FUBARed, nothing works.
  • As you build your system compositing and interacting objects, it's a great feeling to know those parts work.
  • P.S. Write that test before implementing IEquatable.

Create Custom Collections

This hits lots of OO principles like encapsulation and Law of Demeter, but mostly the single responsibility principle. The custom collections will have the responsibility for things like:

  • Not allow duplicate Nodes
  • Not allow null
  • Ensuring valid element joining

Benefits

  • Client code will clean up. For example Solve will not hide "the big picture" with so much busy code looping and fussing with plain Collection objects.

  • Hide underlying collection's public interface so that it does only the things it should.

  • Create custom Find, Contains, etc. so it does things only the way we want.

  • Overall the code is far more robust.

  • We limit potential WTFery in client code. The client must do the right thing.

  • Collection functionality has a proper place.

    • Node.Join
    • Links.ConnectsSameNodes
    • DijkstraSolverStrategy.AddLinksToSet
    • Client does not foreach a collection in order to add to another.
  • Client does not have to know how to build collections

    • var orderedLinks = new SortedSet<Link>(new LinkDistanceComparer()); could simply be new SortedLinkSet().
    • If we have different IComparers to inject, use the factory pattern.
  • code will begin to naturally express itself in domain language

.

public class SortedLinkSet {
    public SortedSet<Link> Links {get; protected set; }
    protected LinkDistanceComparer LinkComparer ( get; set; }

    public SortedLinkSet() { 
        Links = new SortedSet<Link>(new LinkDistanceComparer());
    }

    public void Add(Link newLink) {
        if ( newLink == null ) return;
        if ( Links.Contains(newLink) return;

        Links.Add(newLink);
    }

    public void Add(SortedLinkSet<Link>()) { }

    public void Join (Node a, Node b, int distance) {
        // I "return" for expediency. do what you want.
        // perhaps return a boolean so we can handle a failed join
        // without throwing exceptions.

        if (a == null || b == null) return;
        if (a.Equals(b)) return;
        if (distance <= 0) return;

        // ok, now we can join ...
}
\$\endgroup\$
  • \$\begingroup\$ By definition, a set cannot contain duplicates. Still, the rest are good points \$\endgroup\$ – IEatBagels Dec 30 '15 at 20:46

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.