Я пытаюсь использовать алгоритм boost'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:\program files (x86)\microsoft visual studio 10.0\vc\include\limits(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: на основе ответа Иеремии я изменил vertex_distance_t с int на EdgeWeight, но получил ту же ошибку