boostのグラフを使って経路探索するサンプル
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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