CODEWITHSUNDEEP
c++boostgraphboost-graph
Bad_Coder
Bad_Coder

Reputation: 13

Find the child nodes in a graph using boost

I am new to boost library. Is there any way to find all the child nodes of a graph using boost. Or any document which I can refer to for implementing this would be helpful. I thought of using Out_Edge Iterator because no out edge implies child node.

Upvotes: 1

Views: 1538

Answers (1)

sehe
sehe

Reputation: 392843

On first reading I understood your question literally. Only on second reading I suspected you actually meant to look for leaf nodes.

Finding Child Nodes

The question makes sense if you have a given node (say, vertex #5) and want to list the nodes that are reachable using 1 arc (edge).

Given a graph:

boost::adjacency_list<> g(10);

You get the vertex-descriptors of all the children of vertex 5:

for (auto vd : boost::make_iterator_range(adjacent_vertices(5, g)))
{
    std::cout << "vertex " << vd << " is an out-edge of vertex 5\n";
}

Live Demo

To make things a little bit more interesting, let's generate a random graph:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <iostream>
#include <random>

int main() {
    boost::adjacency_list<> g;
    std::mt19937 rng { 42 };

    generate_random_graph(g, 10, 20, rng);

    for (auto vd : boost::make_iterator_range(adjacent_vertices(5, g)))
    {
        std::cout << "vertex " << vd << " is an out-edge of vertex 5\n";
    }
}

Prints

vertex 1 is an out-edge of vertex 5
vertex 6 is an out-edge of vertex 5

And the graph is visualized as:

enter image description here

Finding Nemo Lead Nodes

The number of edges connecting a vertex is called its degree. The number of outgoing edges can be queried with out_degree:

for (auto vd : boost::make_iterator_range(vertices(g)))
    std::cout << "vertex #" << vd << " has out_degree: " << out_degree(vd, g) << "\n";

You'll see that this means that vertices #1 and #2 are leaf nodes.

BONUS:

Visualizing leaf nodes: Live On Coliru

enter image description here

Upvotes: 2

Related Questions