Reputation: 47

make sub graph from boost graph using particular parent

I want sub graph like C, F, H and D, G using boost library. I have all the parents like in above example C and D.

Upvotes: 1

Answers (1)

sehe

Reputation: 393789

I struggled to make sense of the description. I think I've figured it out. Please consider specifying the requirements instead of merely giving one incomplete example next time.

Starting From The Root

First I thought that you meant to find the root (zero in-edges) and treat each child node as a subgraph.

However, this results in:

// roots are nodes with a zero in-degree (no parents)
Vertices roots;
boost::remove_copy_if(vertices(g), back_inserter(roots), [&](Vertex v) { return boost::size(in_edges(v, g)); });

std::vector<Graph> subs;
for (Vertex root : roots) {
    for (Vertex subroot : boost::make_iterator_range(adjacent_vertices(root, g))) {

        std::set<Vertex> include;
        std::vector<boost::default_color_type> colors(n);

        boost::depth_first_visit(g, subroot, 
                boost::make_dfs_visitor(
                        boost::write_property(
                            boost::identity_property_map{},
                            inserter(include, include.end()),
                            boost::on_discover_vertex())
                    ),
                colors.data());

        std::cout << "Root " << g[root].name << ": Subtree rooted at " << g[subroot].name << " includes " << include.size() << " nodes\n";

        Filtered fg(g, boost::keep_all{}, [&](Vertex v) { return include.count(v); });
        print_graph(fg, names);
    }
}

Printing Live On Coliru

Root A: Subtree rooted at B includes 4 nodes
B --> D E 
D --> G 
E --> 
G --> 
Root A: Subtree rooted at C includes 3 nodes
C --> F 
F --> H 
H -->

Indeed, D is obviously not a child of A so would not count.

Back to the drawing board.

Starting From The Leafs

All sub-trees containing single-degree children or leaf nodes?

This would indeed seem to describe the "linear" subgraphs given as an example. Obviously, the "linear" (vertical) layout is an arbitrary layout choice. All three of the representations below are exactly equivalent to the question graph:

Looking at this the opposite way suddenly makes a lot more sense: you may want to list all the linear dependencies starting from each leaf node, until you reach a node that also participates in another branch.

This naturally involves doing a topological search and listing each branch in the DAG from the leaf-node back:

Live On Coliru

Vertices reverse_topological;
boost::topological_sort(g, back_inserter(reverse_topological));

bool in_path = true;
for (auto v : reverse_topological) {
    if (0 == out_degree(v, g)) { // is leaf?
        in_path = true;
        std::cout << "\nLeaf:";
    }

    in_path &= (1 == in_degree(v, g));

    if (in_path)
        std::cout << " " << names[v];
    else
        std::cout << " [" << names[v] << "]";
}

Prints:

Leaf: G D
Leaf: E B
Leaf: H F C [A]

Minor Variation:

You can indicate that B doubles in two paths, depending on your requirements:

Live On Coliru

Vertices reverse_topological;
boost::topological_sort(g, back_inserter(reverse_topological));

bool in_path = true;
for (auto v : reverse_topological) {
    switch (out_degree(v, g)) {
        case 0:
            // start a new path
            in_path = true;
            std::cout << "\nLeaf:";
            break;
        case 1: 
            break; // still single-degree
        default: in_path = false;
    }

    if (in_path)
        std::cout << " " << names[v];
    else
        std::cout << " [" << names[v] << "]";
}

Prints

Leaf: G D
Leaf: E [B]
Leaf: H F C [A]

Full Listings

To preserve against bitrot:

Starting from the root (first assumption)

#include <boost/graph/adjacency_list.hpp>

struct GraphItem {
    std::string name;
};

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, GraphItem>;
using Vertex = Graph::vertex_descriptor;
using Vertices = std::vector<Vertex>;

#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>
using Filtered = boost::filtered_graph<Graph, boost::keep_all, boost::function<bool(Vertex)>>;

#include <boost/graph/graphviz.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>

int main() {

    Graph g;
    auto names = get(&GraphItem::name, g);

    enum {A,B,C,D,E,F,G,H,n};
    Vertices vs {
        add_vertex({"A"}, g),
        add_vertex({"B"}, g),
        add_vertex({"C"}, g),
        add_vertex({"D"}, g),
        add_vertex({"E"}, g),
        add_vertex({"F"}, g),
        add_vertex({"G"}, g),
        add_vertex({"H"}, g),
    };

    assert(num_vertices(g) == n); 
    add_edge(vs[A], vs[B], g);
    add_edge(vs[A], vs[C], g);

    add_edge(vs[B], vs[D], g);
    add_edge(vs[B], vs[E], g);

    add_edge(vs[D], vs[G], g);

    add_edge(vs[C], vs[F], g);
    add_edge(vs[F], vs[H], g);

    // write_graphviz(std::cout, g, make_label_writer(names));

    // roots are nodes with a zero in-degree (no parents)
    Vertices roots;
    boost::remove_copy_if(vertices(g), back_inserter(roots), [&](Vertex v) { return boost::size(in_edges(v, g)); });

    std::vector<Graph> subs;
    for (Vertex root : roots) {
        for (Vertex subroot : boost::make_iterator_range(adjacent_vertices(root, g))) {

            std::set<Vertex> include;
            std::vector<boost::default_color_type> colors(n);

            boost::depth_first_visit(g, subroot, 
                    boost::make_dfs_visitor(
                            boost::write_property(
                                boost::identity_property_map{},
                                inserter(include, include.end()),
                                boost::on_discover_vertex())
                        ),
                    colors.data());

            std::cout << "Root " << g[root].name << ": Subtree rooted at " << g[subroot].name << " includes " << include.size() << " nodes\n";

            Filtered fg(g, boost::keep_all{}, [&](Vertex v) { return include.count(v); });
            print_graph(fg, names);
        }
    }
}

Starting from the leaves (second assumption, topological-sort)

#include <boost/graph/adjacency_list.hpp>

struct GraphItem {
    std::string name;
};

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, GraphItem>;
using Vertex = Graph::vertex_descriptor;
using Vertices = std::vector<Vertex>;

#include <boost/graph/topological_sort.hpp>
#include <iostream>

int main() {

    Graph g;
    auto names = get(&GraphItem::name, g);

    {
        enum {A,B,C,D,E,F,G,H,n};
        Vertices vs {
            add_vertex({"A"}, g),
            add_vertex({"B"}, g),
            add_vertex({"C"}, g),
            add_vertex({"D"}, g),
            add_vertex({"E"}, g),
            add_vertex({"F"}, g),
            add_vertex({"G"}, g),
            add_vertex({"H"}, g),
        };

        assert(num_vertices(g) == n); 
        add_edge(vs[A], vs[B], g);
        add_edge(vs[A], vs[C], g);

        add_edge(vs[B], vs[D], g);
        add_edge(vs[B], vs[E], g);

        add_edge(vs[D], vs[G], g);

        add_edge(vs[C], vs[F], g);
        add_edge(vs[F], vs[H], g);
    }

    Vertices reverse_topological;
    boost::topological_sort(g, back_inserter(reverse_topological));

    bool in_path = true;
    for (auto v : reverse_topological) {
        if (0 == out_degree(v, g)) { // is leaf?
            in_path = true;
            std::cout << "\nLeaf:";
        }

        in_path &= (1 == in_degree(v, g));

        if (in_path)
            std::cout << " " << names[v];
        else
            std::cout << " [" << names[v] << "]";
    }
}

Upvotes: 3