C++ 使用自定义权重 boost prim 的算法？

Question

我正在尝试使用 boost 的 prim 算法，使用边权重和 id 编号而不只是边权重来找到最小生成树。

例如，如果两个边权重均为 1，则将比较 id，以较小者为准打破平局。

我创建了一个 EdgeWeight 类并重载了 < 和 + 运算符来执行此操作，然后将 edge_weight_t 属性从 int 更改为 EdgeWeight，希望它能起作用。

// TestPrim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

using namespace std;

class EdgeWeight{
    public:
    EdgeWeight(){}
    EdgeWeight(int weightIn, int destinationIdIn){
        weight = weightIn;
        destinationId = destinationIdIn;
    }

        bool operator<(const EdgeWeight& rhs) const {
        if (weight < rhs.weight)
            return true;
        else if(weight == rhs.weight){
            if (destinationId < rhs.destinationId)
                return true;
            else
                return false;
        }
        else
            return false;
        }

    EdgeWeight operator+(const EdgeWeight& rhs) const {
        EdgeWeight temp;
        temp.weight = weight + rhs.weight;
        temp.destinationId = destinationId + rhs.destinationId;
        return temp;
        }

    int weight;
    int destinationId;
};


int _tmain(int argc, _TCHAR* argv[])
{
  using namespace boost;
  typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, EdgeWeight>,      property < edge_weight_t, EdgeWeight > > Graph;
  typedef std::pair < int, int >E;
  const int num_nodes = 5;
  E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
    E(3, 4), E(4, 0)
  };
  EdgeWeight weights[] = { EdgeWeight(1, 2), EdgeWeight(1, 3), EdgeWeight(2, 4), 
      EdgeWeight(7, 1), EdgeWeight(3, 3), EdgeWeight(1, 4), EdgeWeight(1, 0) };
  Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
  std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
  prim_minimum_spanning_tree(g, &p[0]);

  for (std::size_t i = 0; i != p.size(); ++i)
    if (p[i] != i)
      std::cout << "parent[" << i << "] = " << p[i] << std::endl;
    else
      std::cout << "parent[" << i << "] = no parent" << std::endl;

  return EXIT_SUCCESS;
}

我得到一个错误，“c:\program files (x86)\microsoft visual studio 10.0\vc\include\limits(92): error C2440: '' : cannot convert from 'int' to 'D'1> 没有构造函数可以采用源类型，或者构造函数重载决策不明确”

我这样做是否正确？有更好的方法吗？

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.htmlhttp://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

编辑:好的，所以我现在使用 cjm 的扰动方法实现了权重，但我相信将来我将不得不以某种方式使用上述方法，但仍然想知道如何去做

edit2:根据 Jeremiah 的回复，我将 vertex_distance_t 从 int 更改为 EdgeWeight，但得到了同样的错误

Answer 1

Boost 对“Prim 算法”的实现(Jarník 在 Prim 之前近三十年发现了该算法)使用 Dijkstra 算法的通用实现作为子例程。我敢肯定有人认为这真的很聪明。

Dijkstra 算法需要支持加法和比较的非负权重，并且这些操作必须兼容(对于所有 x、y、z，如果 x <= y，则 x + z <= y + z)。在实践中， 实例化这些操作的唯一有用方法是常规方法 (我收回这一点；可以用相同的方式打破 Dijkstra 算法)，因此 Boost 对 Dijkstra 算法的实现明智地假设存在“无限”(std::numeric_limits<vertex_distance_t>::max())。它还断言所有权重都是非负的。

相比之下，Prim 的算法需要仅支持比较的权重。您可能想知道“最小生成树”中的“最小值”在不加法的情况下是什么意思，但是最小生成树的另一种表征是，对于从顶点 u 到顶点 v 的每条路径 P，P 中的最长边位于至少与从 u 到 v 的树路径中最长的边一样长。

结果是 Boost 对 Prim 算法的实现做了一些没有根据的假设。您可以按如下方式围绕它们进行编码，但 Boost 似乎没有契约(Contract)义务在未来不破解此 hack。

• 去掉加法运算符；它没有被使用。

• 由于 Boost 将断言您的所有权重均不小于默认构造值，因此让我们将默认值设置为“负无穷大”。

  #include <limits>
  ...
  EdgeWeight() : weight(numeric_limits<int>::min()),
                 destinationId(numeric_limits<int>::min()) {}
  

• Boost 需要“正无穷大”，所以我们需要特化 std::numeric_limits .

  namespace std {
  template<>
  struct numeric_limits<EdgeWeight> {
      static EdgeWeight max() { return EdgeWeight(numeric_limits<int>::max(),
                                                  numeric_limits<int>::max()); }
  };
  }
  

• 您可以简化比较。

  bool operator<(const EdgeWeight& rhs) const {
      return (weight < rhs.weight ||
              (weight == rhs.weight && destinationId < rhs.destinationId));
  }