For http://lists.boost.org/boost-users/2016/10/86809.php [Boost-users] boost graph pruning vertices (nodes)

small_components.cc

#include <iostream>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/property_map/property_map.hpp>

#include <boost/range/algorithm/for_each.hpp>

using graph = boost::compressed_sparse_row_graph</*Directed=*/boost::directedS,
                                                 /*VertexProperty=*/boost::no_property,
                                                 /*EdgeProperty=*/boost::no_property,
                                                 /*GraphProperty=*/boost::no_property,
                                                 /*Vertex=*/std::uint32_t,
                                                 /*EdgeIndex=*/std::uint32_t>;

using vertex = typename boost::graph_traits<graph>::vertex_descriptor;
using edge = typename boost::graph_traits<graph>::edge_descriptor;

using component_id = std::int32_t;

graph make_graph() {
  /*
   * 0 <-> 1 <-> 3
   *       ^     ^
   *       '     '
   *       '     v
   *       ' --> 2 -> 4 <-> 5 -> 6 <-> 7
   *
   * .............    .......    .......
   */
  auto num_vertices = 8;
  std::vector<vertex> sources{0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7};
  std::vector<vertex> targets{1, 0, 2, 3, 1, 3, 4, 1, 2, 5, 4, 6, 7, 6};
  return graph(boost::construct_inplace_from_sources_and_targets, sources, targets, num_vertices);
}

template <typename Graph> auto make_components(const Graph& g) {
  std::vector<component_id> components(boost::num_vertices(g));
  auto map = boost::make_iterator_property_map(begin(components), get(boost::vertex_index, g));
  boost::strong_components(g, map);
  return components;
}

template <typename Iter> auto make_histogram(Iter first, Iter last) {
  using value_type = typename std::iterator_traits<Iter>::value_type;
  std::unordered_map<value_type, std::int32_t> histogram;

  for (auto it = first; it != last; ++it)
    histogram[*it] += 1;

  return histogram;
}

int main() {
  auto g = make_graph();

  std::cout << "Initial Graph:\n";
  print_graph(g);

  auto components = make_components(g);

  auto histogram = make_histogram(begin(components), end(components));

  std::cout << "Component : Number of Vertices\n";

  for (auto each : histogram)
    std::cout << each.first << " : " << each.second << "\n";

  std::unordered_set<component_id> small_components;
  auto threshold = 3;

  for (auto each : histogram)
    if (each.second < threshold)
      small_components.insert(each.first);

  boost::for_each(vertices(g), [&](auto v) {
    if (small_components.count(components[v]) > 0)
      std::cout << v << " in small component\n";
    else
      std::cout << v << " in big component\n";
  });
}

/*
Initial Graph:
0 --> 1 
1 --> 0 2 3 
2 --> 1 3 4 
3 --> 1 2 
4 --> 5 
5 --> 4 6 
6 --> 7 
7 --> 6 
Component : Number of Vertices
0 : 2
1 : 2
2 : 4
0 in big component
1 in big component
2 in big component
3 in big component
4 in small component
5 in small component
6 in small component
7 in small component
*/