[Boost-users] Some questions about vertex removal in subgraph

Subject: [Boost-users] Some questions about vertex removal in subgraph
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2013-03-29 08:00:47

Hi all,

In the last few days I have been implementing partial I/O for a subgraph by
saving and loading a subgraph (although actually it is only partial if we
see it from the parent graph's point of view). So far, by modifying some
code in Boost, I managed to save a child graph to a file, and also load two
subgraphs which share a vertex without having that vertex duplicated.
However, in addition to save and load, I also need to clear (i.e. remove
all nodes and edges from) a subgraph, and I found that remove_vertex is not
implemented; only remove_edge is.

I noticed that as of now (March 2013) there is no plan to implement it [1].
I cannot use Jeremiah's suggestion there (and also in [2]) to use
filtered_graph, because I need to physically remove the nodes and edges
from memory, so I am thinking to implement it myself. I have a few
questions about this.

1) Jeremiah said that "In particular, local vertex descriptors in subgraphs
are indices into an std::vector, and so removing a vertex would invalidate
many other vertex descriptors." [1] Am I right to assume that this
statement is about m_global_vertex, which is of
std::vector<vertex_descriptor> type?

2) Removing a vertex from a regular graph involves calling
g.m_vertices.erase(..) (adjacency_list.hpp, line 1951). I found that
m_vertices is also of type std::vector. So why does vertex removal work for
regular graph, but supposedly not for subgraph?

I use Boost version 1.53.0, and my subgraph configuration is

typedef adjacency_list<vecS, vecS, undirectedS,
                       property<vertex_index_t, int, VertexProperty>,
                       property<edge_index_t, int, EdgeProperty> >
RegularGraph;
typedef subgraph<RegularGraph> Subgraph;

where VertexProperty and EdgeProperty are respectively bundled properties
for vertex and edge.

Thank you very much!

Best regards,
Nicholas Mario Wardhana

References:
[1] https://svn.boost.org/trac/boost/ticket/4752
[2]
http://boost.2283326.n4.nabble.com/Can-t-link-subgraphs-because-remove-vertex-is-a-TODO-td2994646.html