Граф Дейкстры с таблицей весов на каждом ребре

У меня есть график повышения с несколькими весами для каждого ребра (представьте один набор весов в час дня). Каждое из этих весовых значений хранится в классе propretyEdge:

class propretyEdge {
std::map<std::string,double> weights; // Date indexed
}

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

void Dijkstra (string date, parameters ... )

Что бы использовать

weights[date]

значение для каждого края графа.

Я перечитывал документацию снова и снова, и у меня не было четкого представления о том, что я должен делать. Мне, конечно, нужно написать что-то вроде этого, но я понятия не имею, с чего начать

boost::dijkstra_shortest_paths (
(*graph_m),
vertex_origin_num_l,
// weight_map (get (edge_weight, (*graph_m)))
// predecessor_map(boost::make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, (*graph_m)))).
// distance_map(boost::make_iterator_property_map(distances.begin (), get(vertex_index,(*graph_m) )))
predecessor_map(predecessorMap).
distance_map(distanceMap)
);

Спасибо за помощь.

редактировать

Благодаря замечательным Ответ Сехе, Я мог делать именно то, что хотел на MacOS и Ubuntu.

Но когда мы попытались скомпилировать этот фрагмент кода в Visual Studio 2012, оказалось, что VS не очень хорошо разбирается в функции указателя boost. Итак, мы изменили часть Сехе:

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

от :

class dated_weight_f {
public:
dated_weight_f(Graph* graph_p,std::string date_p){
graph_m=graph_p;
date_m=date_p;
}
typedef double result_type;
result_type operator()(Edge edge_p) const{
return (*graph_m)[edge_p].weights.at(date_m);
}
private:
Graph* graph_m;
std::string date_m;
};

const auto dated_weight_map = make_function_property_map<Edge>(dated_weight_f(graph_m,date_l));

Который имел преимущество в том, что не использовал функцию указателя.

6

Решение

Поскольку, очевидно, не сразу понятно, что этот вопрос ответили в другом ответе, Я объясню.

Все вы действительно нужно это обычай weight_map параметр, который является «с состоянием» и может выбрать определенное значение для данной даты.

Вы можете сделать это настолько сложным, насколько пожелаете so, так что вы даже можете интерполировать / экстраполировать вес, учитывая неизвестную дату ², но давайте для целей этой демонстрации сделаем это простым.

Давайте определим тип графика (примерно) как указано выше:

struct propretyEdge {
std::map<std::string, double> weights; // Date indexed
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;

Теперь давайте сгенерируем случайный граф со случайными весами для 3 разных дат:

int main() {
Graph g;
std::mt19937 prng { std::random_device{}() };
generate_random_graph(g, 8, 12, prng);

uniform_real<double> weight_dist(10,42);
for (auto e : make_iterator_range(edges(g)))
for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
g[e].weights[date] = weight_dist(prng);

И, прыгнув к цели:

    for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
Dijkstra(date, g, 0);
}
}

Теперь, как вы реализуете Dijkstra(...)? Исходя из примера документации, вы бы сделали что-то вроде

void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {

// magic postponed ...

std::vector<Graph::vertex_descriptor> p(num_vertices(g));
std::vector<double>                   d(num_vertices(g));
std::vector<default_color_type>       color_map(num_vertices(g));

boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated

dijkstra_shortest_paths(g, vertex_origin_num_l,
weight_map(dated_weight_map).
predecessor_map(make_iterator_property_map(p.data(),   vid)).
distance_map(make_iterator_property_map(d.data(),      vid)).
color_map(make_iterator_property_map(color_map.data(), vid))
);

Теперь единственный неясный момент здесь должен быть dated_weight_map,

Войти Увеличить карту недвижимости

Как я показал в связанном Можно ли иметь несколько карт свойств веса ребер для одного графа BOOST?, Вы можете иметь все виды карт свойств ³, включая вызов пользовательских функций. Это недостающий кусок:

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

Вуаля: сделано

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

Жить на Колиру

#include <boost/property_map/property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/property_map_iterator.hpp>

#include <random>
#include <boost/graph/random.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <fstream>

using namespace boost;

struct propretyEdge {
std::map<std::string, double> weights; // Date indexed
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;

void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

std::vector<Graph::vertex_descriptor> p(num_vertices(g));
std::vector<double>                   d(num_vertices(g));
std::vector<default_color_type>       color_map(num_vertices(g));

boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated

dijkstra_shortest_paths(g, vertex_origin_num_l,
weight_map(dated_weight_map).
predecessor_map(make_iterator_property_map(p.data(),   vid)).
distance_map(make_iterator_property_map(d.data(),      vid)).
color_map(make_iterator_property_map(color_map.data(), vid))
);

std::cout << "distances and parents for '" + date + "':" << std::endl;
for (auto vd : make_iterator_range(vertices(g)))
{
std::cout << "distance(" << vd << ") = " << d[vd] << ", ";
std::cout << "parent(" << vd << ") = " << p[vd] << std::endl;
}
std::cout << std::endl;

std::ofstream dot_file("dijkstra-eg-" + date + ".dot");

dot_file << "digraph D {\n""  rankdir=LR\n""  size=\"6,4\"\n""  ratio=\"fill\"\n""  graph[label=\"shortest path on " + date + "\"];\n""  edge[style=\"bold\"]\n""  node[shape=\"circle\"]\n";

for (auto ed : make_iterator_range(edges(g))) {
auto u = source(ed, g),
v = target(ed, g);

dot_file
<< u << " -> " << v << "[label=\"" << get(dated_weight_map, ed) << "\""<< (p[v] == u?", color=\"black\"" : ", color=\"grey\"")
<< "]";
}
dot_file << "}";
}

int main() {
Graph g;
std::mt19937 prng { std::random_device{}() };
generate_random_graph(g, 8, 12, prng);

uniform_real<double> weight_dist(10,42);
for (auto e : make_iterator_range(edges(g)))
for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
g[e].weights[date] = weight_dist(prng);

for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
Dijkstra(date, g, 0);
}

}

Выход, например

введите описание изображения здесь


Keep Пока вы сохраняете инварианты, требуемые алгоритмом, который вы вызываете. В частности, вы должны последовательно возвращать один и тот же вес во время выполнения, учитывая то же преимущество. Кроме того, некоторые алгоритмы не поддерживают отрицательный вес и т. Д.

² Я бы настоятельно рекомендовал использовать Boost ICL interval_map в таком случае но я отвлекся

³ смотрите также карта устанавливает / получает запросы в C ++ изменения класса / структуры

13

Другие решения


По вопросам рекламы [email protected]