Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
boostのグラフを使って経路探索するサンプル
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
struct ver_prop_t {
std::string name;
};
struct edge_prop_t {
std::string name;
int distance;
};
typedef boost::adjacency_list<
boost::listS,
boost::vecS,
boost::bidirectionalS,
ver_prop_t,
edge_prop_t
> graph_t;
typedef std::pair<int, int> edge_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;
namespace {
vertex_t add_ver(graph_t& graph, std::string name)
{
typedef boost::graph_traits<graph_t>::vertex_iterator vertex_it_t;
//登録済みかどうか確認
vertex_t vret;
bool ret = false;
std::pair<vertex_it_t, vertex_it_t> ver_it = boost::vertices(graph);
for (vertex_it_t it = ver_it.first, et = ver_it.second; it != et; it++) {
if (graph[*it].name == name) {
ret = true;
vret = *it;
break;
}
}
if (!ret) {
vret = boost::add_vertex(graph);
graph[vret].name = name;
}
return vret;
}
void add_edge(graph_t& graph, vertex_t v1, vertex_t v2, int distance12, int distance21)
{
bool inserted;
graph_t::edge_descriptor e1, e2;
boost::tie(e1, inserted) = boost::add_edge(v1, v2, graph);
graph[e1].distance = distance21;
boost::tie(e2, inserted) = boost::add_edge(v2, v1, graph);
graph[e2].distance = distance12;
}
}
int main()
{
graph_t graph;
vertex_t va = add_ver(graph, "Asia");
vertex_t vb = add_ver(graph, "Beer");
vertex_t vc = add_ver(graph, "Cool");
vertex_t vd = add_ver(graph, "Devel");
vertex_t ve = add_ver(graph, "Estimate");
vertex_t vf = add_ver(graph, "Foobar");
vertex_t vs = add_ver(graph, "START");
vertex_t vz = add_ver(graph, "GOAL");
add_edge(graph, vs, va, 3, 3);
add_edge(graph, va, vb, 1, 1);
add_edge(graph, vb, vc, 2, 2);
add_edge(graph, vb, vd, 3, 3);
add_edge(graph, vc, ve, 7, 7);
add_edge(graph, vc, vf, 12, 12);
add_edge(graph, vd, vf, 2, 2);
add_edge(graph, ve, vd, 11, 11);
add_edge(graph, vf, ve, 3, 3);
add_edge(graph, ve, vz, 2, 2);
add_edge(graph, vf, vz, 2, 2);
// 最短経路を計算
std::vector<vertex_t> parents(boost::num_vertices(graph));
std::vector<int> distance(boost::num_vertices(graph));
boost::dijkstra_shortest_paths(graph, vs,
boost::weight_map(boost::get(&edge_prop_t::distance, graph)).
predecessor_map(&parents[0]).
distance_map(&distance[0]));
// 経路なし
if (parents[vz] == vz) {
std::cout << "no path" << std::endl;
return 1;
}
// 距離
std::cout << "distance: " << distance[vz] << std::endl;
// 経路の並べ直し
std::deque<vertex_t> route;
for (vertex_t v = vz; v != vs; v = parents[v]) {
route.push_front(v);
}
route.push_front(vs);
std::deque<vertex_t>::iterator it = route.begin();
while (true) {
std::cout << graph[*it].name;
it++;
if (it != route.end()) {
std::cout << " --> ";
} else {
std::cout << std::endl;
break;
}
}
// graphviz用
// $ dot -T png dijkstra-graph.dot -o graph.png
std::ofstream dot_file("dijkstra-graph.dot");
dot_file << "digraph D {\n"
<< " rankdir=LR\n"
<< " ratio=\"fill\"\n"
<< " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
boost::graph_traits < graph_t >::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei) {
boost::graph_traits < graph_t >::edge_descriptor e = *ei;
vertex_t u = source(e, graph), v = target(e, graph);
dot_file << graph[u].name << " -> " << graph[v].name << "[label=\"" << graph[e].distance << "\"";
if (parents[v] == u) {
dot_file << ", color=\"black\"";
} else {
dot_file << ", color=\"grey\"";
}
dot_file << "]";
}
dot_file << "}";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment