Search code examples
c++boostboost-graph

Iterating over boost graph vertexes based on maximal depth

I would like to iterate over the vertexes of a graph based on the maximum depth of the vertex from any of the root vertexes.

Fore example the maximal depth of the vertex I is 3 (and is this annotated with this value in the graph below). Therefore any of the orderings would be acceptable: {A , B , C , D} , {E , F , G} , {H}, {I}, where any of the vertexes in curly braces {} can be ordered arbitrarily.

I have come across a somewhat similar question but it is geared towards getting the maximum depth of a single vertex and appears to assume a single root node.

enter image description here

I am quite new to boost graph but here is my feeble attempt at what a solution might resemble

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace boost;

class depth_visitor : public default_dfs_visitor
{
public:
    template <typename Vertex , typename Graph >
    void discover_vertex(Vertex v , const Graph & g) const
    {
        // update 'depth' of vertex 
    }
};


int main()
{
  enum { A , B, C, D, E, F, G , H , I , COUNT };
  const char* name[] = { "A" , "B" , "C" , "D" , "E" , "F" , "G" , "H" , "I" };

  typedef std::pair <int, int >Edge;
  Edge edge_array[] = { Edge(D, G), Edge(C, G), Edge(C, F), Edge(B, F), Edge(B, E), Edge(A, E),
                        Edge(G, H), Edge(F, I), Edge(E, H), Edge(H, I) };

    typedef adjacency_list < vecS, vecS, directedS > graph_t;
    graph_t g( edge_array , edge_array + sizeof(edge_array) / sizeof(E), COUNT );

    depth_visitor vis;
    depth_first_search( g , visitor( vis ) );
}
Solution

  • What Andy said: you can traverse the out-edges manually.

    Alternatively you can use BFS with a custom visitor. You already had a similar idea.

    Here's a realization of it:

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

    Now, let's define our types:

    using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

    Let's create our own maximum distance recorder. This is roughly based on the distance_recorder<> class from Boost, which is an EventVisitor.

    In our case, we'll have it filter for the on_tree_edge event only (because we don't care about non-tree graphs here).

    using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto s = source(e, g), t = target(e, g);
        std::cout << "TREE EDGE " << g[s] << " -> " << g[t] << "\n";

        auto srcit = _ref.find(s);
        auto depth = srcit!=_ref.end()? srcit->second+1: 1;

        if (auto [it, isnew] = _ref.emplace(t, depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

    You can see it basically just updates a std::map but with the following special treatments:

    • when updating an existing value, it updates with the maximum of the current distance and the previously recorded distance.
    • it does not insert depths for vertices not traveled to by a tree edge (basically, it doesn't use operator[source_vertex] which would insert entries with depth 0)

    With that out of the way, all we need is to invoke the algorithm:

    std::vector roots { A, B, C, D };

Depths depths;
Recorder r{depths};

for (auto root : roots)
    boost::breadth_first_search(
        g, root,
        queue, boost::make_bfs_visitor(r), color_map);

for (auto [v,d] : depths)
    std::cout << g[v] << " at " << d << "\n";

    Important Notes:

    • use breadth_first_search as opposed to breadth_first_visit because otherwise the color_map would not be re-initialized on each root node. This would make already-discovered nodes always be skipped, which means we would not correctly get the maximum distance

    • this is also the reason we couldn't use the multi-source overload like so:

      // WARNING BROKEN!
boost::breadth_first_search(
        g, begin(roots), end(roots),
        queue, boost::make_bfs_visitor(r), color_map);

      the effect would be the same because there's no re-initialization of the color-map for each root node.

    LIVE DEMO

    Live On Coliru

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto s = source(e, g), t = target(e, g);
        std::cout << "TREE EDGE " << g[s] << " -> " << g[t] << "\n";

        auto srcit = _ref.find(s);
        auto depth = srcit!=_ref.end()? srcit->second+1: 1;

        if (auto [it, isnew] = _ref.emplace(t, depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

int main() {
    enum : Vertex { A, B, C, D, E, F, G, H, I, COUNT };
    Graph g(COUNT);

    // give names
    for (auto v : boost::make_iterator_range(vertices(g)))
        g[v] = 'A' + v;

    // add edges
    for (auto [s,t] : {
            std::pair(D,G), {D, G}, {C, G}, {C, F}, {B, F}, {B, E}, {A, E},
            {G, H}, {F, I}, {E, H},
            {H, I} })
    {
        add_edge(s, t, g);
    }

    std::vector roots { A, B, C, D };
    boost::queue<Vertex> queue;
    std::vector<boost::default_color_type> colors(num_vertices(g));
    auto color_map = boost::make_iterator_property_map(begin(colors), get(boost::vertex_index, g));

    Depths depths;
    Recorder r{depths};

    for (auto root : roots)
        boost::breadth_first_search(
            g, root,
            queue, boost::make_bfs_visitor(r), color_map);

    for (auto [v,d] : depths)
        std::cout << g[v] << " at " << d << "\n";
}

    Which prints

    TREE EDGE A -> E
TREE EDGE E -> H
TREE EDGE H -> I
TREE EDGE B -> F
TREE EDGE B -> E
TREE EDGE F -> I
TREE EDGE E -> H
TREE EDGE C -> G
TREE EDGE C -> F
TREE EDGE G -> H
TREE EDGE F -> I
TREE EDGE D -> G
TREE EDGE G -> H
TREE EDGE H -> I
E at 1
F at 1
G at 1
H at 2
I at 3

    UPDATE

    Slightly altered to detect roots "by brute force":

    Live On Coliru

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

using boost::make_iterator_range;
using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto depth = 1 + _ref[source(e, g)];

        if (auto [it, isnew] = _ref.emplace(target(e, g), depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

int main() {
    enum : Vertex { A, B, C, D, E, F, G, H, I, COUNT };
    Graph g(COUNT);

    // give names
    for (auto v : make_iterator_range(vertices(g)))
        g[v] = 'A' + v;

    // add edges
    for (auto [s,t] : {
            std::pair(D,G), {D, G}, {C, G}, {C, F}, {B, F}, {B, E}, {A, E},
            {G, H}, {F, I}, {E, H},
            {H, I} })
    {
        add_edge(s, t, g);
    }

    boost::queue<Vertex> queue;
    std::vector<boost::default_color_type> colors(num_vertices(g));
    auto color_map = boost::make_iterator_property_map(begin(colors), get(boost::vertex_index, g));

    Depths depths;
    Recorder r{depths};

    for (auto v : make_iterator_range(vertices(g))) {
        boost::breadth_first_search(g, v, queue, boost::make_bfs_visitor(r), color_map);
    }

    std::map<size_t, std::set<Vertex> > by_depth;
    for (auto [v,d] : depths)
        by_depth[d].insert(v);

    for (auto& [d,vs] : by_depth) {
        std::cout << "depth:" << d;
        for (auto v : vs) std::cout << " " << g[v];
        std::cout << "\n";
    }
}

    Prints

    depth:0 A B C D
depth:1 E F G
depth:2 H
depth:3 I