Clever Geek Handbook

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

I am using boost :: subgraph and want 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 cost of G0 memory? I think G0 should store all the vertices added for G0. Does G0 need to store edges on G0.

When we intersect G0, do we really intersect on G? For each edge, you need to check if its target node is on G0. If not, we'll skip node. So we have this additional verification cost. How it works?

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

Thank,

+3


source to share


1 answer


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

You cannot create an unrelated link (and you cannot rebuild it either). Assignment designates the referenced object.

So basically 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 reading a little more about C ++ because not knowing what language requirements will cause a problem a lot when you are using an extended shared library like Boost Graph.

Recommended Reading: The Ultimate C ++ Guide and Book List

UPDATE



Algorithmic complexities are not affected, but the constants can be expected to increase linearly with the depth of the subgraph tree.

The mechanism in which the subgraphs work is not very complicated (it's just a lot of proxying). The key is that 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 are significant overhead subgraph descriptors for parent ("local global") descriptors.

Exactly how bad things are depends on the use case and you want to profile it:

  • since the subgraphs are nested more deeply, the performance will be better
  • as the subgraphs grow in relation to the parent, memory consumption will increase more proportionally.
  • since the properties are smaller, the difference in memory usage will be more noticeable.

  • if mutations occur on lower nested subgraphs, the ripple effect will have a slower effect. Interesting

    • using a vecS

      VertexContainer in the root graph should usually result in worse insert / delete times;
    • However, for iteration, the advantage is vecS

      for memory locality

    I think both effects will be reduced:

    • search / translation maps damage location anyway and cannot be customized.
    • child graphs use vector storage for some collections; so the invalidation / reallocation costs associated with vectors exist
+2


source






More articles:


All Articles