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

Subject: Re: [Boost-users] boost graph pruning vertices (nodes)
From: Daniel Hofmann (daniel_at_[hidden])
Date: 2016-10-13 06:58:40

On 10/12/2016 11:55 PM, Brian Davis wrote:
> 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.

Yes, you have to be careful wrt. iterator invalidation using different
selectors. What I would do instead is the following:

Ditch the adjacency_list type completely. It doesn't scale well at all
for any graphs of sizes larger than what's in the examples. You'll see
this especially in memory usage since a lot of nested containers will be
created resulting in (over-) allocation on multiple levels.

Use the static (!) graph type compressed_sparse_row_graph instead:
iteration invalidation problems gone and memory efficient.

For filtering either use a filtered_graph on top of that, but keep in
mind the type then will be filtered_graph<G> and not G. If you want to
filter your graph G and get a type G back, you have to create a second
static graph doing the filtering yourself (sounds harder than it is, I
often prefer this approach).

Here is a small self-contained working example for small components:

https://gist.github.com/daniel-j-h/5010fc704bdb24a68d7f9cd50a3d441a

You could further abstract the component search and histogram building
into a function taking any graph type and writing color values into a
ColorMap property map. This would be the idiomatic way following
Boost.Graph's design.

Hint: check how edmonds_karp writes boost::black_color or
boost::white_color for all vertices into a color property map depending
on left side or right side of the cut. You probably want to do the same.

Cheers,
Daniel J H

> 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!
> 
> 
> 
> 
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>