Boost.Graph how to merge two vertices/contract edge

Question

How to merge two vertices/contract edge at Boost.Graph?

I need to move edges from vertex A to vertex B, and delete vertex A - is there any built-in function? Or maybe there is something special for adjacency_list?

If there is no such function - then why? I think it is common graph operation.

EDIT: I do know that it is possible to do it manually, but there are some corner cases (like preserving edges properties), that why it is good candidate to be in library.

I mostly interested to know if Boost.Graph have already that operation (maybe with some fancy name?). And if not - why such primitive operation/algorithm is not in Graph Library. Maybe I am missing something, and that operation is not-primitive or rarely used.

I do not need half-baked quick proof-of-concepts

Answer 1

Half-baked quick proof-of-concept

You can use add_edge() and remove_vertex() on a graph defined in terms of adjacency_list

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

using V = unsigned;
using E = std::pair<V, V>;
using G = boost::adjacency_list<boost::vecS, boost::vecS>;

void print_graph(G const& g)
{
    auto vs = boost::vertices(g);
    for (auto vit = vs.first; vit != vs.second; ++vit) {
        auto neighbors = boost::adjacent_vertices(*vit, g);
        for (auto nit = neighbors.first; nit != neighbors.second; ++nit)
            std::cout << "{" << *vit << "," << *nit << "}" << ", ";
    }
    std::cout << "\n";
}

void contract_vertices(V b, V a, G& g)
{
    auto be = boost::adjacent_vertices(b, g);
    for (auto beit = be.first; beit != be.second; ++beit)
        add_edge(a, *beit, g);
    remove_vertex(b, g);
}

int main()
{
    // named vertices
    auto const A = V { 1 };
    auto const B = V { 2 };

    // construct the graph
    auto e = std::vector<E> { { A, 3 }, { B, 4 } };
    auto g = G { std::begin(e), std::end(e), 4 };

    print_graph(g);
    contract_vertices(B, A, g);    
    print_graph(g);
}

Live example that prints

{1,3}, {2,4},
{1,2}, {1,3},

The output is not quite what you expect because the labelling of vertices is also updated to reflect the removal of B, which cause nodes 3 and 4 to be labelled 2 and 3 now.

Requirements for library-quality code

A general library-quality algorithm for contraction of vertices u and v should typically take into account at least the following corner cases

• remove (u,v) and (v,u) edges;
• merge all u and v out-edges with common targets;
• merge all u and v in-edges with common sources;
• move the rest of u out-edges to v;
• move the rest of u in-edges to v;

Boost.Graph provides all the required primitives for such an operation: in_edges(), out_edges(), add_edge(), clear_vertex(), remove_vertex(). For undirected graphs several of these items can be done in a single step, whereas for directed graphs typically two steps are required.

In addition to these algorithmic steps, one should also define the semantics of what it means to merge or move edges. E.g. what should happen to their properties? This is similar to e.g. merging two corporations: under which name should the joint firm operate?

Why Boost.Graph does not (yet) provide a contract_vertices()

TL;DR I don't know. But I can speculate. Mainly, one should specify the interface of a putative contract_vertices(). Apart from the two vertices to be contracted, and the type of graph they are a part of, one should also define the merge and move operations on the edge properties. In theory, it should be possible to do this with suitable template parameter to the general algorithm.