Boost Graph: Running DFS again on a subgraph

user_1362499 0
Viewed 42

I'm using a boost::directed_graph and am running DFS on it to determine the dependencies of a particular node. I pass the name of the node I'm interested in to the visitor implementation. My issue is that during the DFS if I, for example, enumerate the left subtree of the graph and then in the right subtree come across a cross edge back to the left subtree, DFS will not re-enumerate those nodes because it has already visited them. I'd like to run DFS again with the node pointed to by the cross edge as the root. Example:

enter image description here

The node I want to find dependencies for is C (which is enumerated 4th). I want to get back A and B as dependencies, so it seems to me that when I get a cross edge like this I should run DFS on the subgraph with A as the root to get those nodes.

typedef boost::directed_graph<Plugin> graph;
typedef graph::edge_descriptor graph_e_des;
typedef std::vector<std::wstring> DependencyVector;

class DependencyVisitor : public boost::default_dfs_visitor
{
public:

    DependencyVisitor(DependencyVector& dependencies, std::wstring& name) :
        m_dependencies(dependencies),
        m_name(name)
    {
    }

    void forward_or_cross_edge(graph_e_des e, const graph& g)
    {
        DependencyVector dependencies;
        std::wstring name = g[e.m_target].name;
        DependencyVisitor v(dependencies, name);

        boost::depth_first_search(g[e.m_target], boost::visitor(v));

        m_dependencies.insert(std::end(m_dependencies), std::begin(dependencies), std::begin(dependencies));
    }

private:
    DependencyVector& m_dependencies;
    std::wstring m_name;
};

I tried calling boost::depth_first_search again using what forward_or_cross_edge provides but I don't know how to get a new graph at the desired node. I was reading about boost::filtered_graph or boost::subgraph but it wasn't clear of those were the right solutions.

Thanks in advance.

boost-graph boost c++
1 Answers

  1. First off,

    I tried calling boost::depth_first_search again using what forward_or_cross_edge provides but I don't know how to get a new graph at the desired node.

    boost::depth_first_search(g[e.m_target], boost::visitor(v));

    looks like a mistake. g[vd] results in the vertex bundle (Plugin& in your case). You need a vertex descriptor, so you likely meant something like:

    depth_first_search(e.m_target, boost::visitor(v));

    Although m_target should tip you off that you're using undocumented implementation details. Prefer the concept interface:

    depth_first_search(target(e, g), boost::visitor(v));

  2. Secondly, there's definitely a typo here:

    m_dependencies.insert(end(m_dependencies), begin(dependencies), begin(dependencies));

    You most likely meant

    m_dependencies.insert(end(m_dependencies), begin(dependencies), end(dependencies));

  3. On to the meat of the question, it seems to me that you "just" want to get all transitive dependencies. How you best achieve that depends a lot on your input, like whether it contains cycles or constitutes a tree or a forest.

    In the simplest of cases, all you want is a topological_sort:

    The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then v comes before u in the ordering. The graph must be a directed acyclic graph (DAG). The implementation consists mainly of a call to depth_first_search().

    Of course, this only gives you the "net" ordering.

  4. There are simpler ways to compose a visitor that records the predecessors on the fly. For inspiration here's a short sample that shows how to record predecessors:

    #include <boost/graph/depth_first_search.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/bimap.hpp>
#include <iostream>

using Name = std::string; // std::wstring?
struct Plugin{ Name name; };

using G    = boost::directed_graph<Plugin>;
using V    = G::vertex_descriptor;
using E    = G::edge_descriptor;
using Deps = std::vector<Name>;

int main() {
    G g;
    auto v1 = add_vertex(Plugin{"Root"}, g);
    auto v2 = add_vertex(Plugin{"A"}, g);
    auto v3 = add_vertex(Plugin{"B"}, g);
    auto v4 = add_vertex(Plugin{"C"}, g);

    add_edge(v1, v2, g);
    add_edge(v1, v4, g);
    add_edge(v2, v3, g);
    add_edge(v4, v2, g);

    print_graph(g, get(&Plugin::name, g));

    std::vector<V> pred(num_vertices(g));

    auto vidx = get(boost::vertex_index, g);
    auto name = get(&Plugin::name, g);
    auto pmap = make_iterator_property_map(pred.begin(), vidx);

    depth_first_search( //
        g,
        boost::visitor(make_dfs_visitor(
            record_predecessors(pmap, boost::on_forward_or_cross_edge{}))));

    for (V cur = v2, p; (p = pred.at(vidx[cur])) != g.null_vertex(); cur   = p) {
        std::cout << "predecessor of " << name[cur] << " is " << name[p] << "\n";
    }
}

    Printing

    Root --> A C 
A --> B 
B --> 
C --> A 
predecessor of A is C

  5. Topological sort assumes a DAG. The predecessor mapping there assumes only 1 predecessor per vertex (so a multi-root tree/forest).

    If you actually want all the dependencies, arguably the graph itself is the best source. A simple helper would be all_dependencies:

    Live On Coliru

    #include <boost/graph/depth_first_search.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fmt/ranges.h>
#include <ranges>
#include <iostream>

using boost::make_iterator_range;
using std::views::transform;

using Name = std::string; // std::wstring?
struct Plugin{ Name name; };

using G    = boost::directed_graph<Plugin>;
using V    = G::vertex_descriptor;
using E    = G::edge_descriptor;
using Deps = std::vector<Name>;

template <typename OutputIterator>
static OutputIterator all_dependencies(G const& g, V v, OutputIterator out) {
    for (auto e : make_iterator_range(out_edges(v, g))) {
        auto dep = target(e, g);
        *out++   = dep;
        out      = all_dependencies(g, dep, out);
    }
    return out;
}

int main() {
    G g;
    auto v1 = add_vertex(Plugin{"Root"}, g);
    auto v2 = add_vertex(Plugin{"A"}, g);
    auto v3 = add_vertex(Plugin{"B"}, g);
    auto v4 = add_vertex(Plugin{"C"}, g);

    add_edge(v1, v2, g);
    add_edge(v1, v4, g);
    add_edge(v2, v3, g);
    add_edge(v4, v2, g);

    auto name = get(&Plugin::name, g);
    print_graph(g, name);

    std::vector<V> deps;
    all_dependencies(g, v4, back_inserter(deps));

    fmt::print("Deps of {} are {}\n", //
               name[v4],              //
               deps | transform([name](V v) { return name[v]; }));
}

    Prints

    Root --> A C 
A --> B 
B --> 
C --> A 
Deps of C are ["A", "B"]
user_853710
Related