Boost graph list или vec

Question

Я проводил довольно много дней, работая с библиотекой графов ускорения. Насколько я понимаю, при рассмотрении VertexList и хранения EdgeList:

ЗВТА:

• обладает индексом, поэтому может быть доступ с ним
• при удалении вершины, итератор аннулируется

СПИСКИ:

• нет индекса
• не аннулирует итератор

Это немного коротко, но это касается моей проблемы. Мне нужен номер индекса, и я хочу иметь возможность легко удалить вершины позже.

У меня есть алгоритм работы с этой структурой графа:

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

У меня есть пользовательские структуры Intersection_Graph для моих вершин, которые мне нужно использовать. Здесь я использую vecS.

Я хочу использовать listS вместо того, чтобы удалять вершины. Кроме того, я хочу использовать его позже с алгоритмом Дейкстры.

Я понимаю, что мне нужно иметь boost::vertex_index_t в моем списке, но я действительно запутался в том, как это сделать и сохранить свою собственную структуру одновременно.

Я пытался что-то вдоль этих линий:

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; 

Но я даже не могу получить доступ к моей пользовательской-структуре больше. Кроме того, доступ к индексу не работает.

Мне действительно нужна возможность доступа к индексу, так как алгоритм мой график будет зависеть от возврата индекса родительского узла. Я чувствую, что мог бы избежать использования вершин вместо индексов, но это означало бы серьезную переписку кода, и я хочу знать, могу ли я избежать этого.

Итак, мой вопрос: есть ли способ, чтобы listS вел себя как vecS, сохраняя при этом преимущества listS?

Пожалуйста, несите меня, если это звучит глупо. На данный момент я довольно запутан, поэтому я мог бы сказать что-то глупое. Если вам нужна дополнительная информация, просто спросите.

Answer 1

внутренние свойства формулировка:

property<tag, type, next_property> 

Конечно, если вы сделаете Intersection_Graphведут себя как интегрального типа вы не можете использовать его непосредственно в качестве типа из vertex_index собственности. Вероятно, это также не то, что вы хотели.

Это выглядит ближе:

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

И было бы объявить два свойства:

1. интерьера свойство помечено vertex_index_t (тип int)
2. в комплекте поставки имущества (набранный Intersection_Graph). Обратите внимание, что связанные свойства неявно доступны через тег vertex_bundle_t.

Теперь с этим в виду, что все должно быть гладко:

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 << "'"; 
} 

который печатает например, (Случайным образом генерируется каждый прогон)

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' 

Примечания:

• тот факт, что граф "знает" vertex_index Теперь не означает, что она будет поддерживаться; Вы должны заполнить его самостоятельно:

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

• вы на самом деле не нужно иметь vertex_index, связанный с вашим типом графа, потому что вы можете передать его в качестве имени параметра для всех соответствующих алгоритмов AFAIK. Это включает в себя построение полученных карт свойств, которые основаны на vertex_index (например, make_iterator_property_map)

• Я считаю, что также можно связать индекс вершин с помощью графических признаков (но в прошлом я этого не делал). Это похоже на хороший способ пойти, если вы, например. хотел сохранить индекс в члене вашей структуры Intersection_Graph.
• Как я уже говорил в my comment, вы, возможно, не нуждаетесь в этом, если вы сохранили vertex_descriptor s вместо целых индексов.