Skip to content

Instantly share code, notes, and snippets.

@amedama41
Created December 10, 2013 11:45
Show Gist options
  • Save amedama41/7889380 to your computer and use it in GitHub Desktop.
Save amedama41/7889380 to your computer and use it in GitHub Desktop.
#include <fstream>
#include <iterator>
#include <limits>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/algorithm/for_each.hpp>
namespace Canard {
template <class ParentMap, class Tag>
struct parent_recorder : boost::base_visitor<parent_recorder<ParentMap, Tag>> {
using event_filter = Tag;
explicit parent_recorder(ParentMap const parent_map)
: parent_map_(parent_map)
{}
template <class Edge, class Graph>
void operator()(Edge const e, Graph const& g) const {
auto value = get(parent_map_, source(e, g));
put(parent_map_, target(e, g), value);
}
private:
ParentMap const parent_map_;
};
template <class ParentMap, class Tag>
parent_recorder<ParentMap, Tag>
record_parent(ParentMap parent_map, Tag) {
return parent_recorder<ParentMap, Tag>{parent_map};
}
}
int main()
{
using Graph = boost::adjacency_list<
boost::vecS
, boost::listS
, boost::undirectedS
, boost::property<boost::vertex_index_t, std::size_t>
, boost::property<boost::edge_color_t, std::string>>;
Graph graph;
// input from dot file
{
std::ifstream ifs("graph.dot");
boost::dynamic_properties dp;
dp.property("label", get(boost::vertex_index, graph));
boost::read_graphviz(ifs, graph, dp, "label");
}
auto const index_map = get(boost::vertex_index, graph);
auto const parent_map = boost::make_vector_property_map<std::string>(index_map);
auto const root_vertices = {
boost::vertex(0, graph),
boost::vertex(12, graph),
boost::vertex(13, graph),
};
// set parent(root) color
{
std::string const colors[] = {"red", "green", "blue"};
auto color = colors;
std::cout << "root vertices:" << std::endl;
for (auto const root : root_vertices) {
std::cout << '\t' << get(index_map, root) << std::endl;
put(parent_map, root, *color++);
}
}
boost::dijkstra_shortest_paths(
graph
// root vertices
, begin(root_vertices), end(root_vertices)
// predecessor map(non used)
, boost::dummy_property_map{}
// distance map
, boost::make_vector_property_map<std::size_t>(index_map)
// edge weight map(all edge weights is 1)
, boost::make_constant_property<boost::graph_traits<Graph>::edge_descriptor>(1)
, index_map
, std::less<std::size_t>{}
, boost::closed_plus<std::size_t>{}
, std::numeric_limits<std::size_t>::max()
, std::size_t{0}
, boost::make_dijkstra_visitor(
Canard::record_parent(parent_map, boost::on_edge_relaxed{})));
// set edge color
boost::for_each(edges(graph),
[&](boost::graph_traits<Graph>::edge_descriptor const e) {
put(boost::edge_color, graph, e,
get(parent_map, source(e, graph)) == get(parent_map, target(e, graph))
? get(parent_map, source(e, graph))
: "gray");
});
// output to dot file
{
std::ofstream ofs{"output_grpah.dot"};
boost::dynamic_properties dp;
dp
.property("label", index_map)
.property("fillcolor", parent_map)
.property("color", get(boost::edge_color, graph));
boost::write_graphviz_dp(ofs, graph, dp, "label");
}
}
graph G {
0[label=0];
1[label=1];
2[label=2];
3[label=3];
4[label=4];
5[label=5];
6[label=6];
7[label=7];
8[label=8];
9[label=9];
10[label=10];
11[label=11];
12[label=12];
13[label=13];
14[label=14];
10--5 ;
8--14 ;
7--12 ;
1--9 ;
0--1 ;
10--4 ;
11--7 ;
1--3 ;
2--11 ;
3--9 ;
6--10 ;
5--4 ;
12--9 ;
10--7 ;
9--6 ;
9--0 ;
5--13 ;
4--8 ;
7--13 ;
6--13 ;
9--7 ;
8--5 ;
5--6 ;
4--6 ;
7--6 ;
14--6 ;
13--10 ;
14--10 ;
}
graph G {
0 [fillcolor=red];
1 [fillcolor=red];
10 [fillcolor=green];
11 [fillcolor=green];
12 [fillcolor=green];
13 [fillcolor=green];
14 [fillcolor=blue];
2 [fillcolor=green];
3 [fillcolor=red];
4 [fillcolor=blue];
5 [fillcolor=blue];
6 [fillcolor=green];
7 [fillcolor=green];
8 [fillcolor=blue];
9 [fillcolor=red];
10--5 [color=gray];
8--14 [color=blue];
7--12 [color=green];
1--9 [color=red];
0--1 [color=red];
10--4 [color=gray];
11--7 [color=green];
1--3 [color=red];
2--11 [color=green];
3--9 [color=red];
6--10 [color=green];
5--4 [color=blue];
12--9 [color=gray];
10--7 [color=green];
9--6 [color=gray];
9--0 [color=red];
5--13 [color=gray];
4--8 [color=blue];
7--13 [color=green];
6--13 [color=green];
9--7 [color=gray];
8--5 [color=blue];
5--6 [color=gray];
4--6 [color=gray];
7--6 [color=green];
14--6 [color=gray];
13--10 [color=green];
14--10 [color=gray];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment