c++ - Boost graph list o vec

algorithm boost-graph

Question

Estuve pasando unos días trabajando con la biblioteca de gráficos de impulso. Por lo que yo entiendo, al considerar el almacenamiento de VertexList y EdgeList:

vecS:

• posee un índice, por lo que se puede acceder con él
• al eliminar vértices, el iterador se invalida

listS:

• sin índice
• no invalida el iterador

Es un poco corto, pero ese es el punto de mi problema. Necesito esos números de índice y quiero poder quitar vértices más adelante.

Tengo un algoritmo de trabajo con esta estructura de gráfico:

typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS, 
        topologicalmap::Intersection_Graph ,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

Tengo una estructura personalizada Intersection_Graph para mis vértices que necesito usar. Aquí uso vecS.

Quiero usar listS en su lugar para poder eliminar vértices. Además, quiero poder usarlo más tarde con el algoritmo de Dijkstra.

Entiendo que necesito tener boost::vertex_index_t en mi lista, pero estoy realmente confundido sobre cómo hacerlo y mantener mi estructura personalizada al mismo tiempo.

Intenté algo así:

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

Pero ya no puedo acceder a mi estructura personalizada. Además, el acceso al índice no funciona.

Realmente necesito esa capacidad de acceso al índice ya que el algoritmo del que mi gráfico dependerá devolverá el índice del nodo padre. Siento que podría salirse con la suya usando un Vertex en lugar de índices, pero implicaría una importante reescritura del código y quiero saber si puedo evitarlo.

Entonces mi pregunta es: ¿hay alguna forma de que las listas se comporten de la misma manera mientras se mantienen las ventajas de las listas?

Por favor, tengan paciencia si suena estúpido. Estoy bastante confundido en este momento, así que podría haber dicho algo estúpido. Si necesita más información, solo pregunte.

Answer 1

La formulación de propiedades interiores es:

property<tag, type, next_property>

Por supuesto, a menos que haga que Intersection_Graph comporte como un tipo integral, no puede usarlo directamente como el tipo de la propiedad vertex_index . También es probable que no sea lo que querías.

Esto se ve más cerca:

boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>

Y declararía dos propiedades:

1. una propiedad interior etiquetada como vertex_index_t (tipo int )
2. una propiedad empaquetada (mecanografiada Intersection_Graph ). Tenga en cuenta que las propiedades incluidas son implícitamente accesibles a través de la etiqueta vertex_bundle_t .

Ahora, con esto en mente, todo debería ser sencillo:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>

#include <random>
#include <iostream>

using namespace boost;

namespace topologicalmap {
    struct Intersection_Graph {
        std::string bundled;
    };
}

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

int main() {

    std::mt19937 prng { std::random_device {} () };
    Graph_boost g;

    generate_random_graph(g, 10, 20, prng);

    // assign indices
    int i = 0;
    BGL_FORALL_VERTICES(v, g, Graph_boost) { 
        get(vertex_index, g)[v] = i; 
        g[v].bundled = "id:" + std::to_string(i);

        i++;
    }

    // print the graph using the `bundled` property as a label:
    print_graph(g, get(&topologicalmap::Intersection_Graph::bundled, g));

    // do some index accesses:
    for (int i : {1,7})
        std::cout << "/nVertex at index #" << i << " has a bundled property of ''" << g[vertex(i,g)].bundled << "''";
}

Que imprime, por ejemplo, (generado aleatoriamente cada ejecución)

id:0 <--> id:8 id:8 id:7 id:6 id:1 
id:1 <--> id:3 id:4 id:4 id:3 id:0 id:2 
id:2 <--> id:7 id:1 
id:3 <--> id:1 id:7 id:1 id:9 id:4 
id:4 <--> id:1 id:1 id:5 id:6 id:3 
id:5 <--> id:4 id:9 
id:6 <--> id:0 id:9 id:4 id:8 
id:7 <--> id:3 id:0 id:2 id:9 
id:8 <--> id:0 id:0 id:6 
id:9 <--> id:7 id:6 id:3 id:5 

Vertex at index #1 has a bundled property of ''id:1''
Vertex at index #7 has a bundled property of ''id:7''

Notas:

• el hecho de que el gráfico "sepa" vertex_index ahora no significa que se mantenga; tienes que llenarlo tú mismo:

  int i = 0;
  BGL_FORALL_VERTICES(v, g, Graph_boost) get(vertex_index, g)[v] = i++; 

• en realidad no necesita tener vertex_index asociado con su tipo de gráfico, porque puede pasarlo como un parámetro nombrado a todos los algoritmos relevantes AFAIK. Esto incluye la construcción de mapas de propiedades derivadas que se basan en un vertex_index (por ejemplo, make_iterator_property_map )

• Creo que también es posible asociar un índice de vértice utilizando rasgos de gráfico (pero no lo he hecho en el pasado). Esto parece una buena forma de hacerlo si, por ejemplo, desea almacenar el índice en un miembro de su estructura Intersection_Graph .
• Como dije en mi comentario , probablemente no podría requerir nada de esto si almacenó vertex_descriptor s en lugar de índices integrales.