
Boost Users : 
Subject: Re: [Boostusers] [Graph] need suggestion
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 20120103 00:49:01
On Monday, January 02, 2012 11:18 PM, srinivas boppu wrote:
> Hello All,
>
Hi
> I need a graph structure as follows. (Here my input is a Graph which I call
> it as " Control Flow Graph".)
>
> On this "Control Flow Graph", I run a algorithm it creates another graph,
> and on that I will run again
> the algorithm, it will create another "Graph" and it continues until it
> become a "Single Node".
>
Out of the box, I would recommend you to have a look at filtered_graph<>, that
can be applied to an adjacency_list<>. It can be seen as a mask that you put
over your original graph, leaving the original graph untouched. What you need
to provide filtered_graph<> with is a predicate that decides if an edge/vertex
should be visible or not. Here, I could think of a map that is updated at each
run and hence directly keeps track of the edges/vertices to be visible.
This seems to be the most elegant solution using the BGL IMHO.
If you have an idea how to allow for constant access of the visible/non
visible property, this would greatly speed up this solution.
> I should be able to access all the Graphs in each stage and my original
> graph information should be
> untouched.
>
The above suggestion leaves you with exactly two graphs: the original as
adjacency_list<> and the filtered one as filtered_graph<>. So if you need the
intermediate graphs, you could copy the filtered_graph<> to an adjacency_list<>
which is of course potentially timeexpensive as it will copy all the visible
vertices and edges. But since you said that you need the intermediates you
probably won't be able to avoid something like this; after all, these graphs
need to be created. Please correct me if I'm wrong.
> What is the best way to do it ? Any suggestions ?
>
Don't know if it is the best way, but definitely one feasible way, closely
oriented on the functionality of BGL.
> (Actually, I am trying to solve one problem using "Interval Based
> Analysis" of Control Flow Graphs. I would like to divide the given
> main control flow graph into disjoint intervals. You can have a look at the
> following link for more information
> http://nptel.iitm.ac.in/courses/106108052/module9/controlflowana2.pdf
> )
>
> Regards,
> Srinivas
Hope that helps.
Best,
Cedric
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net