CODEWITHSUNDEEP
boostboost-graph
Shivam Goyal
Shivam Goyal

Reputation: 91

Boost size of largest connected component

I know how to calculate the total number of connected components in Boost, but is there an efficient way to compute the size of the largest connected component using the boost's graph library.

Upvotes: 1

Views: 162

Answers (1)

sehe
sehe

Reputation: 393134

I think the most efficient way is to replace the component map with a custom type.

I created a small WritePropertyMap to do that:

template <typename V>
struct Mapper {
    using Id          = int; // component id
    using Cardinality = int;

    using Map   = boost::container::flat_map<Id, Cardinality>;
    using Value = Map::value_type;
    Map& storage;

    friend void put(Mapper& m, V const& /*v*/, Id id) { m.storage[id] += 1; }

    Value largest() const {
        return not storage.empty()
            ? *max_element(begin(storage), end(storage),
                   [](Value const& a, Value const& b) {
                       return a.second < b.second;
                   })
            : Value{};
    }
};

We need to tell Boost about our property map:

template <typename V> struct boost::property_traits<Mapper<V>> {
    using category   = boost::writable_property_map_tag;
    using key_type   = V;
    using value_type = int;
};

Note

The separation between storage and property map is because property maps are passed by value - and should be cheap to copy.

Now we can use it, adapting the library example slightly:

Live On Coliru

Mapper<V>::Map result;
Mapper<V> mapper{result};
int num = connected_components(g, mapper);

auto [id, cardinality] = mapper.largest();
std::cout << "Largest component #" << id << " (out of " << num
          << " components) has " << cardinality << " vertices\n";

Prints

Largest component #0 (out of 3 components) has 3 vertices

This matches the expected output.

BONUS

If you have an expected number of components, you may be able to optimize storage by using small_vector/static_vector, e.g.

using Value = std::pair<Id, Cardinality>;
using Map = boost::container::flat_map<
    Id, Cardinality, std::less<>,
    boost::container::small_vector<Value, 10>>;

This way, unless you have more than 10 components, you will never see a dynamic allocation for the mapper storage.

Upvotes: 2

Related Questions