Алгоритм C++ boost prim с пользовательскими весами?

Question

Я пытаюсь использовать алгоритм Prim's prim, чтобы найти минимальное остовное дерево с использованием веса кромки и идентификационного номера вместо веса края.

Например, если оба веса ребер были равны 1, идентификатор сравнивался бы, в зависимости от того, что меньше было бы сломать галстук.

Я создал класс 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: \ файлы программы (x86) \ Microsoft Visual Studio 10.0 \ VC \ включить \ пределы (92): ошибка C2440: '': не удается преобразовать из 'Int' в ' 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

редактировать: хорошо, так что я реализовал веса с использованием метода возмущенный CJM для теперь, но в в будущем, я считаю, что я должен буду использовать вышеупомянутый метод как-то, до сих пор интересно, как сделать это

edit2: на основе réponse Иеремии Я изменил vertex_distance_t от ИНТ к EdgeWeight но получил ту же ошибку

Answer 1

Реализация алгоритма «Прима» в программе Boost (Jarník обнаружил алгоритм почти за тридцать лет до Prim) использует обобщенную реализацию алгоритма Дейкстры в качестве подпрограммы. Я уверен, что кто-то подумал, что это действительно умный.

Алгоритм Дейкстры нуждается в неотрицательных весах, которые поддерживают добавление с идентичностью и сравнением, и эти операции должны быть совместимы (для всех x, y, z, если x < = y, то x + z < = y + z). На практике - единственный полезный способ для создания этих операций - это обычная версия (я беру это обратно, так же, как и алгоритм Тайбэна Дийкстры), поэтому реализация алгоритма Дейкстры в Boost разумно предполагает существование «бесконечности» (std::numeric_limits<vertex_distance_t>::max()). Он также утверждает, что все веса неотрицательны.

Напротив, алгоритм Prim требует весов, которые поддерживают только сравнение. Вы можете задаться вопросом, что означает «минимум» в «минимальном остовном дереве» без добавления, но альтернативная характеристика минимального связующего дерева заключается в том, что для каждого пути P от вершины u до вершины v самое длинное ребро в P находится в по крайней мере, до тех пор, пока самый длинный край на пути дерева от u до v.

Результатом является то, что реализация Boost алгоритма Prim's делает некоторые необоснованные предположения. Вы можете закодировать вокруг них, как показано ниже, но 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

Вершины расстояние map value_type должен быть таким же, как t он имеет тип крайнего веса для работы алгоритма. Документация подразумевает, что (в первой части описания distance_map), но не говорит об этом явно. Я (после ответа на этот вопрос) уточнил и исправил документацию в стволе Boost.