graph.cpp

#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.dot

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 ;
}

output_graph.dot

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];
}