c++ - Boost graph list or vec -

i've been spending quite few days working boost graph library. far understand, when considering vertexlist , edgelist storage :

vecs :

• possess index, can access it
• when removing vertices, iterator invalidated

lists :

• no index
• does not invalidate iterator

it's bit short that's point problem. need index number , want able remove vertices later on.

i have working algorithm graph structure :

typedef boost::adjacency_list<         boost::vecs, boost::vecs, boost::undirecteds,          topologicalmap::intersection_graph ,         boost::edge_weight_t,          boost::no_property > graph_boost; 

i have custom structure intersection_graph vertices need use. here use vecs.

i want use lists instead able remove vertices. well, want able use later dijkstra algorithm.

i kind of understand need have boost::vertex_index_t in list confused how , keep custom struct @ same time.

i tried along lines :

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; 

but can't access custom struct anymore. plus, index access don't work.

i need index access capability since algorithm graph depend on return index of parent node. feel away using vertex instead of indexes imply major re-writing of code , want know if can avoid it.

so question : there way have lists behaving in vecs manner while keeping advantages of lists ?

please, bear me if sounds stupid. i'm quite confuse @ moment, might have stupid. if need more information, ask.

the interior properties formulation is:

property<tag, type, next_property> 

of course, unless make intersection_graph behave integral type cannot use directly type of vertex_index property. it's not wanted.

this looks closer:

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

and declare two properties:

1. an interior property tagged vertex_index_t (type int)
2. a bundled property (typed intersection_graph). note bundled properties implicitly accessible through vertex_bundle_t tag.

now in mind, should plain sailing:

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 = 0;     bgl_forall_vertices(v, g, graph_boost) {          get(vertex_index, g)[v] = i;          g[v].bundled = "id:" + std::to_string(i);          i++;     }      // print graph using `bundled` property label:     print_graph(g, get(&topologicalmap::intersection_graph::bundled, g));      // index accesses:     (int : {1,7})         std::cout << "\nvertex @ index #" << << " has bundled property of '" << g[vertex(i,g)].bundled << "'"; } 

which prints e.g. (random generated each run)

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 @ index #1 has bundled property of 'id:1' vertex @ index #7 has bundled property of 'id:7' 

notes:

• the fact graph "knows" vertex_index doesn't mean gets maintained; have fill yourself:

  int = 0; bgl_forall_vertices(v, g, graph_boost) get(vertex_index, g)[v] = i++;  

• you don't need have vertex_index associated graph type, because can pass in named parameter relevant algorithms afaik. includes constructing derived property maps rely on vertex_index (e.g. make_iterator_property_map)

• i believe it's possible associate vertex index using graph traits (but haven't done in past). seems nice way go if e.g. wanted store index in member of intersection_graph struct.
• like said in my comment not require of if stored vertex_descriptors instead of integral indexes.