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

Question

I use boost::subgraph, and wanted to know how it 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 is the memory cost of G0? I guess G0 has to store all vertices added for G0. Does G0 also need to store edges on G0.

When traversing G0, do we actually traverse on G? For each edge, we need to check if its target node is on G0. If not, we skip the node. So we have this additional check cost. Is it how it works?

Boost also has the filtered graph http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/filtered_graph.html How o we decide using a subgraph or a filtered graph?

Thank you,

Answer 1

Your problem with the reference is a C++ problem and has nothing to do with Boost Graph.

You can not create an unbound reference (and you cannot rebind it either. Assignment assigns the object referred to.

So in principle what you had, but 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 to read a bit more about C++ because not knowing the language essentials is going to cause you a lot of trouble when you use an advanced generic library like Boost Graph.

Suggested reading: The Definitive C++ Book Guide and List

UPDATE

The algorithmic complexities aren't affected, but the constants can be expected to increase linearly with the depth of the tree of subgraphs.

The mechanism in which the subgraphs work is not very complicated (it's just a lot of proxying). The key is in the way mappings are stored inside non-root subgraphs:

Graph m_graph;
subgraph<Graph>* m_parent;
edge_index_type m_edge_counter; // for 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 you can see there is considerable overhead mapping subgraph descriptors to parent ("locally global") descriptors.

Exactly how bad things are depends on use-cases and you will want to profile it:

• as subgraphs are nested more deeply, performance will suffer more
• as subgraphs get larger relative to the parent, memory consumption will rise more proportionately
• as properties are smaller, the difference in memory usage will be more visible

• if mutations happen on lower-nested subgraphs, the ripple effect is going to have more slowdown effect. Interestingly

  • using vecS on the root graph's VertexContainer should usually lead to worse insertion/deletion times;
  • However for iteration the advantage is with vecS for memory locality

  I think both effects will be lessened:

  • the lookup/translation maps hurt locality anyways and cannot be customized
  • child graphs use vector storage for some collections regardless; so the invalidation/reallocation costs associated with the vectors are there