Увеличить граф bellman_ford_shortest_paths с меткой - PullRequest
Новая
       37

Увеличить граф bellman_ford_shortest_paths с меткой

0 голосов
/ 05 января 2019

Я пытаюсь запустить алгоритм Беллмана-Форда с помощью библиотеки повышения. У меня есть помеченный график, но я получаю исключение invalid conversion from ‘void*’ to ‘int. Любая помощь будет только приветствоваться. Вот мой код: 

// g++ -std=c++17 -Wall test.c++ -l boost_system && ./a.out 

#include <iostream>                  // for cout
#include <utility>                   // for pair
#include <algorithm>                 // for for_each
#include <vector>                    // For dist[] and pred[]
#include <limits>                    // To reliably indicate infinity
#include <map>
#include <list>

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>

using namespace boost;
using namespace std;

class Node
{
  public:
    int id;
    int group;
};

struct EdgeProperties {
  double weight;

  EdgeProperties(){}
  EdgeProperties(double w){ weight = w; }
};

typedef labeled_graph<adjacency_list<hash_setS, hash_setS, directedS, Node, EdgeProperties>, int> Graph;

int main(){

    cout << "Calling main()" << endl;

    Graph g;

    // populate the graph
    {
        add_vertex( 0, g );
        g[0].id  = 0;
        g[0].group = 10;
        add_vertex( 1, g );
        g[1].id  = 1;
        g[1].group = 20;
        add_edge_by_label( 0, 1, EdgeProperties(110), g);
        add_edge_by_label( 1, 0, EdgeProperties(222), g);
        print_graph(g, get(&Node::id, g));
        cout << "There are " << num_vertices(g) << " nodes and " << num_edges(g) << " edges in the graph" << endl;
    }

    // number of verticies in the graph
    auto n = num_vertices(g);

    // weight map
    auto ewp = weight_map(get(&EdgeProperties::weight, g.graph()));

    const int source = 0;
    const int target = 1;

    // Distance Map (with n elements of value infinity; source's value is 0)
    auto inf = numeric_limits<double>::max();
    vector<double> dist(n, inf);
    dist[source] = 0.0;

    // Predecessor Map (with n elements)
    vector<int> pred(n);

    bellman_ford_shortest_paths(
        g.graph(), 
        n, 
        ewp
            .distance_map(make_iterator_property_map(dist.begin(), get(&Node::id, g)))
            .predecessor_map(make_iterator_property_map(pred.begin(), get(&Node::id, g)))
    );

    return 0;
}

Я видел пример на https://www.boost.org/doc/libs/1_53_0/libs/graph/example/bellman-example.cpp, но в примере используется не помеченный график.

Вот предварительный просмотр моего кода:

https://wandbox.org/permlink/WsQA8A0IyRvGWTIj

Спасибо

1 Ответ

0 голосов
/ 06 января 2019

Источник проблемы был затронут в принятом вами ответе.

Однако это еще не все.

Во-первых, вы в значительной степени «по праву» хотите использовать Node::id в качестве индекса вершины, и может быть много веских причин для использования чего-то другого, кроме vector, в качестве селектора вершинного контейнера ¹.

Во-вторых, этот материал должен был ... наверное, сработать. bellman_ford документы :

Тип PredecessorMap должен представлять собой карту свойств чтения / записи, тип ключа и вершины которой совпадает с типом дескриптора вершины графа.

А iterator_property_map документы :

Эта карта свойств представляет собой адаптер, который преобразует любой итератор произвольного доступа в карту свойств Lvalue. Тип OffsetMap отвечает за преобразование ключевых объектов в целые числа, которые можно использовать как смещения с помощью итератора произвольного доступа.

Теперь LValuePropertyMap может фактически быть только для чтения, но в данном случае это явно не должно быть.

При использовании make_iterator_property_map с дополнительным параметром id-map он должен фактически вести себя как любая ассоциативная карта свойств как для типа ключа, так и для типа значения vertex_descriptor, как того требует алгоритм.

ОБНОВЛЕНИЕ См. "БОНУС" ниже

Я мог бы немного подробнее остановиться позже, чтобы понять, почему это не сработало, но сейчас давайте просто обойдем проблему, не изменяя модель графа:

Live On Coliru 

auto gg = g.graph();
auto id = get(&Node::id, gg);
std::map<Graph::vertex_descriptor, Graph::vertex_descriptor> assoc_pred;

bellman_ford_shortest_paths(gg, n,
    weight_map(get(&EdgeProperties::weight, gg))
    .distance_map(make_iterator_property_map(dist.begin(), id))
    .predecessor_map(make_assoc_property_map(assoc_pred))
    );

Это работает как следует и как ожидалось: 

Calling main()
1 --> 0 
0 --> 1 
There are 2 nodes and 2 edges in the graph

БОНУС

Я нашел недостающую ссылку: карта предшественника была определена с неправильным типом значения: 

vector<Graph::vertex_descriptor> pred(n);

Очевидно, будет работать: Live On Coliru

¹ это немного отличается от дескриптора вершины, но связано в том смысле, что выбор контейнера вершин обычно предсказывает фактический тип дескриптора вершины

...