Boost logo

Boost Users :

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
> 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:

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.

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
> From
> "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]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at