Как добавить пользовательские свойства к краям grid_graph в Boost Graph Library?
#include "stdafx.h"#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <boost/date_time/gregorian/gregorian.hpp>
#include <boost/chrono.hpp>
#include <algorithm>
#include <ctime>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/test/unit_test.hpp>
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graphviz.hpp>
using namespace std;
using namespace boost;
using namespace boost::gregorian;#define DIMENSIONS 2
typedef grid_graph<2> Graph;
typedef graph_traits<Graph> Traits;
// Define a simple function to print vertices
void print_vertex(Traits::vertex_descriptor vertex_to_print) {
std::cout << "(" << vertex_to_print[0] << ", " << vertex_to_print[1] << ")" << std::endl;
}
int main(int argc, char* argv[]) {
// Define a 3x5 grid_graph where the second dimension doesn't wrap
// boost::array<std::size_t, 2> lengths = { { 3, 5 } };
boost::array<size_t, 2> lengths = { { 3, 5 } };
Graph graph(lengths);
// Do a round-trip test of the vertex index functions
for (Traits::vertices_size_type v_index = 0;
v_index < num_vertices(graph); ++v_index) {
// The two indicies should always be equal
std::cout << "Index of vertex " << v_index << " is " <<
get(boost::vertex_index, graph, vertex(v_index, graph)) << std::endl;
}
// Do a round-trip test of the edge index functions
for (Traits::edges_size_type e_index = 0;
e_index < num_edges(graph); ++e_index) {
// The two indicies should always be equal
std::cout << "Index of edge " << e_index << " is " <<
get(boost::edge_index, graph, edge_at(e_index, graph)) << std::endl;
}// Print number of dimensions
std::cout << graph.dimensions() << std::endl; // prints "3"
// Print dimension lengths (same order as in the lengths array)
std::cout << graph.length(0) << "x" << graph.length(1) << std::endl; // prints "3x5x7"
// Start with the first vertex in the graph
Traits::vertex_descriptor first_vertex = vertex(0, graph);
print_vertex(first_vertex); // prints "(0, 0)"
// Print the next vertex in dimension 0
print_vertex(graph.next(first_vertex, 0)); // prints "(1, 0)"
// Print the next vertex in dimension 1
print_vertex(graph.next(first_vertex, 1)); // prints "(0, 1)"
}
Итак, это Grid-граф библиотеки Boost. Но я не знаю, как реализовать края с весами int. Какое свойство я должен использовать, чтобы сделать это?
Я могу пересекать ребра и узлы, но только их значения, а не их значения.
Решение
Таким образом, вы используете аксессоры, чтобы получить ребра по их индексам, см., Например,
Чтобы также прикрепить свойства, см., Например,
Другие решения
Способ сделать это через внешние свойства. grid_graph поддерживает edge_index а также vertex_index свойства для отображения edge_descriptorс и vertex_descriptorиндексы от 0 до 0 соответственно. Чтобы определить карту свойств внешнего края, вы можете использовать iterator_property_map объединить grid_graphКарта свойств краевого индекса с итератором произвольного доступа.
Вот полный пример:
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/write_dimacs.hpp>
#include <boost/property_map/property_map.hpp>
int main() {
typedef boost::grid_graph<2> Graph;
typedef boost::graph_traits<Graph> Traits;
Graph graph {{3, 5}};
// Create a vector to store the capacity of each edge.
std::vector<int> capacities(num_edges(graph));
// Set the edge capacities. Here, we'll just use iota().
std::iota(capacities.begin(), capacities.end(), 10);
// Utilize iterator_property_map to make a property map for the edge capacities.
boost::property_map<Graph, boost::edge_index_t>::type edge_index_map = get(boost::edge_index, graph);
auto capacities_map = boost::make_iterator_property_map(capacities.begin(), edge_index_map);
// Select the first and the last vertices as the source and sink nodes, respectively.
Traits::vertex_descriptor s = vertex(0, graph),
t = vertex(num_vertices(graph) - 1, graph);
boost::write_dimacs_max_flow(
graph,
capacities_map,
get(boost::vertex_index, graph),
s,
t,
std::cout);
return EXIT_SUCCESS;
}