0

我正在尝试使用 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> No constructor could取源类型，或构造函数重载决议不明确”

我这样做对吗？有一个更好的方法吗？

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

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

编辑2：根据耶利米的回应，我将 vertex_distance_t 从 int 更改为 EdgeWeight 但得到了同样的错误

4

2 回答 2

2

顶点距离图value_type需要与算法工作的边权重类型相同。该文档暗示（在描述的第一部分distance_map）但没有明确说明。我（在回答这个问题后）澄清并更正了 Boost 后备箱中的文档。

于 2012-04-11T20:48:43.307 回答
2

Boost 对“Prim 算法”的实现（Jarník 在 Prim 之前将近 30 年发现了该算法）使用 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 似乎没有合同义务在未来不破坏此 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));
}
于 2012-04-14T13:53:17.077 回答