WordPress 你所有的基地属于 Dijkstra

问题描述

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.

我试图用 TDD 实现 Dijkstra’s algorithm 。该算法旨在找到到达图的所有节点的最快路由。现在，我担心如果我以很好的角度实现了算法。我测试了 (显然)，我的所有测试通过，所以我很自信的算法工作，我只是不知道是否应该写的方式。

这些是我用来表示图表的两个类：

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

这是算法的实现：

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

基本上，我从头节点开始，从这个节点添加链接到 SortedSet，然后选择最小的链接。我从集合中删除当前链接，添加新节点的链接，选择最小的链接，然后重复。我确保没有关闭循环，确保具有相同 To 节点的链接不能在集合中两次。

由于我使用 TDD，我认为包括我的单元测试将是一个很好的举措：

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

最佳解决方案

我一直在想这一段时间，我很确定你没有实现 Dijkstra 的算法 (这是图中两个节点之间的最短路径) 。看起来您正在计算最小生成树 (以最小的成本连接所有节点的边集合) 。

一些额外的评论：

Link 是一个奇怪的名称 – 更一般来说，术语 Edge 用于连接图中的两个节点。
我认为你的抽象有点太漏洞 – 算法需要了解节点和链接的内部结构 (我指的是 link.To.Links.Where(l => !l.ConnectsSameNodes(link)) 。我会规定您可以使用以下公共接口实现一个 Graph 对象，并且还可以创建独立的图形算法：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
}
这具有以下优点：
1. 用户可以定义自己的节点类型，并将他们喜欢的任何元数据关联起来。
2. 如何存储节点和边的内部实现是隐藏的，因为他们不必关心它 – 也不应该。

更新：

为了清楚和总结 @BenAaronson 留下的评论：Dijkstra’s algorithm as explained on wikipedia 在图中找到两个节点之间的最短路径。在这种情况下，您将期望为算法提供一个开始和结束节点。如果您的目标是通过 Dijkstra 找到从给定节点到任何其他节点的所有最短路径，那么这不是您正在做的。

一个简单的例子就是这个图：

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

您的算法产生序列 A – > B，B – > C，C – > D，总成本为 7，这确实是以最小的成本连接所有节点的一组边。如果要使用 Dijkstra 算法来计算从 A 到其他节点的所有最短路径，您将得到：A – > B，A – > B – > C，A – > D，费用为 13(如果您不计算 A – > B 两次)，因为从 A 到 D 的最小成本的路径确实是成本为 6 的边。

因此，您的实现将找到所有边的集合，以便所有节点以最小的成本连接。如上所述，通常称为 a minimum spanning tree，其中存在几种算法，最显著的是 Prim’s algorithm 和 Kruskal’s algorithm 。

我没有详细检查它，但它看起来像你的算法本质上是 Kruskal’s algorithm 的一个实现。所以这不是完全错误的 – 它不是你开始执行的算法。

您可以将您的实现重命名为 KruskalSolverStrategy，然后再次使用 Dijkstra(如果您需要帮助，则 Stackoverflow 将是更好的地方，因为 CodeReview 是关于检查现有代码) 。

次佳解决方案

Nest 和 Link 应实施 IComparable<T>

那么 LinkDistanceComparer 可以使用它们。这是行动中的单一责任原则。

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

并确保实现 IComparable<T> 不是 IComparable 。通用型可以让您安全。

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

实施 IEquatable<Node> 和 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);
}

object.Equals 如何覆盖？再次，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));
}

例外

使用 Exception.Data 来捕获上下文。当事情爆炸时，知道参数值非常方便。

为了方便上述，Node 和 Link 应该覆盖 ToString()。那么你可以这样做

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

重组 DijkstraSolverStrategy.Solve

我看不到森林的树; 它没有结构化。 Solve 是做什么的？这是高级代码，应该这样阅读。

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

测试更深

我的倾向是测试我的基本类中的重要事物，如等于覆盖。

太麻烦了？测试也是关于 future-proofing 的变化。
在这个特殊的代码中，Equals 是至关重要的。如果 Equals 是 FUBARed，没有任何作用。
当您构建系统合成和交互对象时，知道这些部件的工作非常好。
附：在实施 IEquatable 之前编写该测试。

创建自定义集合

这引发了许多 OO 原则，如封装和 Demeter 法，但主要是单一的责任原则。定制系列将对以下内容负责：

不允许重复节点
不允许为空
确保有效的元素加入

优点

客户端代码将被清理。例如 Solve 不会隐藏「大图」，因为这么繁忙的代码循环，并且使用普通的 Collection 对象。
隐藏底层集合的公共接口，使其只执行应该的事情。
创建自定义 Find，Contains 等，所以它只做我们想要的方式。
总体而言，代码更加强大。
我们限制客户端代码中的潜在 WTFery 。客户必须做正确的事情。
收集功能有适当的位置。
- Node.Join
- Links.ConnectsSameNodes
- DijkstraSolverStrategy.AddLinksToSet
- 客户端不能将 foreach 的一个集合添加到另一个。
客户端不必知道如何构建集合
- var orderedLinks = new SortedSet<Link>(new LinkDistanceComparer()); 可以简单地是 new SortedLinkSet()。
- 如果我们有不同的 IComparer 注射，请使用出厂模式。
代码将开始自然地以领域语言表达

。

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 ...
}

参考文献

All your bases are belong to Dijkstra

注：本文内容整合自 Google/Baidu/Bing 辅助翻译的英文资料结果。如果您对结果不满意，可以加入我们改善翻译效果：薇晓朵技术论坛。

WordPress 你所有的基地属于 Dijkstra