c++ - How does boost::subgraph work? Can we use filtered graph? -

i use boost::subgraph, , wanted know how works.

graph g; add_vertex(a, g); add_vertex(b, g); add_vertex(c, g); add_edge(a, b, g); add_edge(a, c, g); add_edge(c, b, g); graph &g0 = g.createsubgraph(); add_vertex(a, g0); add_vertex(b, g0); 

what memory cost of g0? guess g0 has store vertices added g0. g0 need store edges on g0.

when traversing g0, traverse on g? each edge, need check if target node on g0. if not, skip node. have additional check cost. how works?

boost has filtered graph http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/filtered_graph.html how o decide using subgraph or filtered graph?

thank you,

your problem reference c++ problem , has nothing boost graph.

you can not create unbound reference (and cannot rebind either. assignment assigns the object referred to.

so in principle had, fixed:

graph g; add_vertex(a, g); add_vertex(b, g); add_vertex(c, g); add_edge(a, b, g); add_edge(a, c, g); add_edge(c, b, g);  graph& g0 = g.createsubgraph(); add_vertex(a, g0); add_vertex(b, g0); 

i suggest read bit more c++ because not knowing language essentials going cause lot of trouble when use advanced generic library boost graph.

suggested reading: the definitive c++ book guide , list

update

the algorithmic complexities aren't affected, constants can expected increase linearly depth of tree of subgraphs.

the mechanism in subgraphs work not complicated (it's lot of proxying). key in way mappings stored inside non-root subgraphs:

graph m_graph; subgraph<graph>* m_parent; edge_index_type m_edge_counter; // generating unique edge indices childrenlist m_children; globalvertexlist m_global_vertex; // local -> global localvertexmap m_local_vertex;  // global -> local globaledgelist m_global_edge;              // local -> global localedgemap m_local_edge; // global -> local 

as can see there considerable overhead mapping subgraph descriptors parent ("locally global") descriptors.

exactly how bad things depends on use-cases , want profile it:

• as subgraphs nested more deeply, performance suffer more
• as subgraphs larger relative parent, memory consumption rise more proportionately
• as properties smaller, difference in memory usage more visible

• if mutations happen on lower-nested subgraphs, ripple effect going have more slowdown effect. interestingly

  • using vecs on root graph's vertexcontainer should lead worse insertion/deletion times;
  • however iteration advantage vecs memory locality

  i think both effects lessened:

  • the lookup/translation maps hurt locality anyways , cannot customized
  • child graphs use vector storage collections regardless; invalidation/reallocation costs associated vectors there