Boost.Graph how to merge two vertices/contract edg

问题:

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

回答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.

回答2:

Doing it manually, you should manually remove each b edge, not the vertex:

void collapse_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_edge(b, *beit, g);
    }
}

gives out your wanted {1,3}, {1,4},.

I don't know why it isn't included (in my knowledge) in the BGL, but this function is what does it.

回答3:

There is no generic function in the library because it is not possible for a generic function to know what needs to be done in the 'corner cases'. What if vertex X has an edge to both vertex A and B? Should the function simply delete X-A, or should it delete X-B and move X-A to X--B? What if the edge from X to A ( the vertex being deleted ) has properties that must be preserved or modified? Only the application code knows how to handle properties when an edge is deleted or moved

'Delegating' these decisions, as qble suggests, makes no sense. If the decision about what to do with the properties of deleted edges is 'delegated' to the application code, then the application code is going to have to find and loop over the edges that must be deleted. So it has to repeat the same work that the generic function does. It might as well do the edge deletion itself, once it has finished with the properties of each deleted edge, and not bother calling the generic function.