c++ - polisuperficies - como unir vertices en maya

Boost.Graph cómo fusionar dos vértices/borde de contrato

Question

¿Cómo combinar dos vértices / borde de contrato en Boost.Graph?

Necesito mover los bordes desde el vértice A al vértice B, y eliminar el vértice A - ¿hay alguna función incorporada? ¿O tal vez hay algo especial para adjacency_list?

Si no hay tal función, ¿por qué? Creo que es una operación gráfica común.

EDITAR : Sé que es posible hacerlo manualmente, pero hay algunos casos de esquina (como preservar las propiedades de los bordes), por eso es un buen candidato para estar en la biblioteca.

Me interesa sobre todo saber si Boost.Graph ya tiene esa operación (¿tal vez con algún nombre de fantasía?). Y si no, ¿por qué esa operación / algoritmo primitivo no está en Graph Library? Tal vez me esté perdiendo algo, y esa operación no es primitiva o rara vez se usa.

No necesito una prueba rápida a medias de conceptos

Answer 1

Al hacerlo manualmente, debes eliminar manualmente cada b borde, no el vértice:

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);
    }
}

da a conocer su {1,3}, {1,4}, deseado {1,3}, {1,4},

No sé por qué no está incluido (en mi conocimiento) en el BGL, pero esta función es lo que lo hace.

Answer 2

No hay una función genérica en la biblioteca porque no es posible que una función genérica sepa qué se debe hacer en los ''casos de esquina''. ¿Qué pasa si el vértice X tiene un borde para ambos vértices A y B? ¿La función simplemente borra XA, o debería eliminar XB y mover XA a X - B? ¿Qué ocurre si el borde de X a A (el vértice que se está eliminando) tiene propiedades que se deben preservar o modificar? Solo el código de la aplicación sabe cómo manejar las propiedades cuando se borra o mueve un borde

''Delegar'' estas decisiones, como sugiere qble, no tiene sentido. Si la decisión sobre qué hacer con las propiedades de los bordes eliminados se ''delega'' al código de la aplicación, entonces el código de la aplicación tendrá que encontrar y recorrer los bordes que se deben eliminar. Entonces tiene que repetir el mismo trabajo que la función genérica. También podría hacer la eliminación de bordes en sí, una vez que haya terminado con las propiedades de cada borde eliminado, y no molestar a llamar a la función genérica.

Answer 3

Prueba de concepto rápida a medio cocer

Puede usar add_edge() y remove_vertex() en un gráfico definido en términos de 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);
}

Ejemplo vivo que imprime

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

La salida no es exactamente la esperada porque el etiquetado de los vértices también se actualiza para reflejar la eliminación de B , lo que hace que los nodos 3 y 4 se etiqueten 2 y 3 ahora.

Requisitos para el código de calidad de la biblioteca

Un algoritmo general de calidad de biblioteca para la contracción de los vértices u v normalmente debe tener en cuenta al menos los siguientes casos de esquina

• eliminar (u, v) y (v, u) bordes;
• fusionar todos los bordes uy v con objetivos comunes;
• fusiona todos los bordes uy v con orígenes comunes;
• mueve el resto de los bordes hacia v;
• mueve el resto de u en los bordes a v;

Boost.Graph proporciona todas las primitivas requeridas para dicha operación: in_edges() , out_edges() , add_edge() , clear_vertex() , remove_vertex() . Para los gráficos no dirigidos, varios de estos elementos se pueden realizar en un solo paso, mientras que para los gráficos dirigidos generalmente se requieren dos pasos.

Además de estos pasos algorítmicos, también se debe definir la semántica de lo que significa fusionar o mover bordes. Por ejemplo, ¿qué debería pasar con sus propiedades? Esto es similar, por ejemplo, a la fusión de dos empresas: ¿bajo qué nombre debe operar la empresa conjunta?

Por qué Boost.Graph no (todavía) proporciona un contract_vertices()

TL; DR , no lo sé. Pero puedo especular. Principalmente, uno debe especificar la interfaz de un supuesto contract_vertices() . Además de los dos vértices que se van a contratar y el tipo de gráfico del que forman parte, también se deben definir las operaciones de fusión y movimiento en las propiedades de los bordes. En teoría, debería ser posible hacer esto con un parámetro de plantilla adecuado para el algoritmo general.