[Boost-users] boost graph pruning vertices (nodes)

Subject: [Boost-users] boost graph pruning vertices (nodes)
From: Brian Davis (bitminer_at_[hidden])
Date: 2016-10-12 17:55:08

In reading

http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/adjacency_list.html

regarding Iterator and Descriptor Stability/Invalidation it leaves the
impression that when using vecS there is no real good way to remove nodes.

as example:

typedef adjacency_list<listS, vecS> Graph; // VertexList=vecS

all cases are wrong

and

typedef adjacency_list<listS, listS> Graph; // VertexList=listS

where only one case is correct which leave the programmer walking the mine
field.  Of course same can be said for stl.

My goal to remove graph vertices based on the value of the connected
components.  I currently have a method which uses connected components to
generate a connected components list.  I then generate a histogram of the
connected components values thus giving me how many vertices are connected
and what the connection property value is... assuming I understand
connected components however I have thought I understood portions of boost
only to find through some brain warp and folding my thought process back on
itself like an origami master that I came to understand how certain parts
work.

vertid, component
0 0
1 0
2 0
3 0
4 1
5 1
6 2
7 2
8 2
9 2
10 2
11 2
12 3
13 3

so in this simple example vert ids [0-3] are connected in subnet 0 with a
total of 4, [4-5] are connected in sub net 1 with a total of 2, [6-11] are
connected in subnet 2 with a total of 6, and [12-13] is connected in subnet
3 with a total of 2.

Histogram yields connected component value and number of vertices that have
that value in the bin
component : bin counts
0: ####
1: ##
2: ######
3: ##
etc

for say subnet/subgraph less than 4 would yield the filtered histogram:
1: ##
3: ##
using values 1, and 3 from filtered histogram I can then find the vertex
ids to filter. Yielding vertices 4,5,12, and 15 to be removed which would
remove subnets 1 and 3.

4 1
5 1
12 3
13 3

I tried to use boost::accumulators::density and maybe I have a different
idea of what a histogram really is, but for a typical histogram density is
just plane broken due to the seemingly use of count for number of bins
(seems to ignore tag::density::num_bins) and associated logic.
accumulator_t acc(
        tag::density::num_bins = n_bins,
        tag::density::cache_size = n_bins/2
        );
Sure wish there was a boost::accumulators::histogram that just did what we
need as programmers. I am unsure as to how much boost coolaid to drink
before finding any use for density. I did find this relating to the
seemingly not as advertised implementation of density
http://lists.boost.org/Archives/boost/2008/01/132801.php.  From
http://www.boost.org/doc/libs/1_62_0/doc/html/accumulators/user_s_guide.html
"The tag::density feature returns a histogram of the sample distribution.
For more implementation details, see density_impl." err huh no it does
not... at least in my testing. It would also be great if the abcicissas
(intervals) were some how obtainable to compare to the ordinates  (bin
counts) . Note the histogram.hpp attached there.  So I write by own
histogram code using stl. I digress on that.

So as I said I  then filter the vertex vs connected components data based
on a threshold say 4 to remove all vertices that are not connected to 4 or
more vertices in a subnet/subgraph

So I then have a list of vertices (subnets/subgraphs) that I wish to prune
from the graph thus these questions:

Question 1:
if finding a list of vertices to erase, sorting them, and then using, a
reverse iterator to remove(*itr, g) would this also not work? If this works
why is it now shown as an example of vecS vertex removal working?

Question 2:
Should there not be a  boost graph-ish way of doing this such as coloring
vertices to be pruned by possibly adding property prune = true. then maybe
a future call to prune(g)

Question 3:
Possibly there is a way to get filtered_graph to do the trick?

Statement:
it is unfortunate the use of the term vertex/vertices in stead of node(s)
in boost graph.  As some graphs have a vertex (euclidean geometry) such as
a graph of the center-lines of the vascular network of a brain while other
graphs do not.  It is very confusing in this instance to keep the two
strait in code. Ugh!