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

Я пытаюсь использовать алгоритм 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, но получил ту же ошибку


person stack356    schedule 11.04.2012    source источник
comment
Не похоже, что эта ошибка имеет какое-то отношение к алгоритму? Что находится в строке 92 этого файла? Можете ли вы сосредоточиться на том, где появляется эта ошибка?   -  person Nathaniel Ford    schedule 11.04.2012
comment
Я думаю, что более простой способ разорвать связи — просто изменить вес ребер на очень небольшое число. Например. если ваши веса ребер изначально являются целыми числами, то для двух ребер, имеющих вес 5, сделайте одно из них весом 4,9, а другое — 5,1. То, как вы возмущаете вещи, очевидно, зависит от того, сколько связей вы ожидаете/домен ваших краевых весов.   -  person cjm    schedule 11.04.2012
comment
Я мог бы сделать это, я думаю. Я пытался сделать это правильно, используя типы.   -  person stack356    schedule 11.04.2012
comment
Я не уверен, в чем проблема с вашим кодом, но метод возмущения является довольно общепринятым решением для произвольного разрыва связей в графовых алгоритмах. Я, конечно, не назвал бы это «неправильным».   -  person cjm    schedule 11.04.2012
comment
Я не согласен с тем, что возмущение тварей — хорошая альтернатива, и я поддерживаю идею использования id для разрыва связей в таких случаях. Однако я не думаю, что это проблема в этом фрагменте кода. Я никогда не пытался реализовать алгоритм prim с помощью boost, но, честно говоря, выполнение этого с нуля приведет к более короткому коду, и я считаю, что он будет не менее эффективным.   -  person Ivaylo Strandjev    schedule 11.04.2012
comment
Да, я мог бы реализовать алгоритм, но я думал, что смысл гибкого prim API заключается в том, чтобы я мог изменить сравнение вместо того, чтобы переписывать алгоритм.   -  person stack356    schedule 11.04.2012


Ответы (2)


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

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

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

В результате реализация алгоритма Prim в Boost делает некоторые необоснованные предположения. Вы можете кодировать их следующим образом, но Boost не обязан по контракту не нарушать этот хак в будущем.

  • Избавьтесь от оператора сложения; он не используется.

  • Поскольку 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));
    }
    
person oldboy    schedule 14.04.2012
comment
P.S.: если вы не являетесь опытным пользователем C++ или вам не нужен один из более сложных алгоритмов (например, проверка планарности), я думаю, вы в конечном итоге будете счастливее, не используя BGL. - person oldboy; 14.04.2012
comment
Спасибо за подробный полный ответ! Это кажется хакерским, но если вы не можете использовать свой собственный пользовательский объект, то какой смысл вводить алгоритм? Возможно, пример реализации пользовательского объекта в документации сделает это более понятным. Причина, по которой я выбрал этот алгоритм, заключается в том, что он считается быстрым, а boost — это хорошо известная гибкая библиотека. И только потому, что я могу быть слаб с шаблонами, не означает, что я буду уклоняться от проблемы, которая требует этого, так я учусь. В любом случае, спасибо. - person stack356; 15.04.2012

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

person Jeremiah Willcock    schedule 11.04.2012
comment
Я изменил vertex_distance_t с int на EdgeWeight, но получил ту же ошибку. Не могли бы вы указать мне пример реализации того, что я пытаюсь сделать, или помочь мне в дальнейшем? - person stack356; 13.04.2012
comment
Знаете ли вы, из какой строки вашей программы исходит ошибка? - person Jeremiah Willcock; 13.04.2012