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

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 Graph; // VertexList=vecS

all cases are wrong

and

typedef adjacency_list 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users