带自定义权重的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）的\微软的Visual Studio 10.0 \ VC \包括\限制（92）：错误C2440：'：诠释 '到'无法从转换' D' 1>没有构造函数可以采取源类型，或构造函数重载分辨率模糊“

我正在做这个正确的方式吗？有一个更好的方法吗？

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

编辑：好了，所以我实现了使用军事审判的摄动法求现在的权重，但在将来，我相信我会以某种方式使用上述方法，仍然不知道该怎么办呢

EDIT2：根据耶利米的效应初探我改变了vertex_distance_t从int到EdgeWeight，但得到了同样的错误

Answer 1

Boost的“Prim's”算法的实现（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似乎没有合同义务在未来不打破这种黑客行为。

• 摆脱加法运算符;它没有被使用。

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

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

• 升压需要 “正无穷大”，所以我们需要专门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)); 
  } 
  

Answer 2

的顶点距离地图的value_type需要与t相同他边缘权重类型的算法工作。该文件暗示（在distance_map的描述的第一部分），但没有明确说明。我（自从回答这个问题以来）澄清并更正了Boost主干中的文档。