[Graph] need suggestion
Hello All, 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". I should be able to access all the Graphs in each stage and my original graph information should be untouched. What is the best way to do it ? Any suggestions ? (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/control-flow-ana-2.pdf ) Regards, Srinivas
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 time-expensive 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/control-flow-ana-2.pdf )
Regards, Srinivas
Hope that helps. Best, Cedric
Hi Cedric, Thanks. I have decided to use "filter_graph" and as you suggested I will copy the relevant vertices. I need one more small favour. Here is my problem: All of my vertices have a property called "select". Which is set during my algorithm run. After the algorithm is completed, I have some vertices which are having this "select" property as "0" or "1". now, I want to filter my original graph based on the "select" property and "copy" it. I was looking at the example in installation, "filtered-copy-example.cpp" and I tried to write some simple code as pasted below, but it gives me a lot of errors. Can some one have a look at it.? Here is my template function. --------------------------------------------------------------------------------- template <typename Graph> struct select_vertex { select_vertex() { } // has to have a default constructor! select_vertex(const Graph& g) : g(&g) { } bool operator()(typename boost::graph_traits<Graph>::vertex_descriptor v) const { return get(boost::vertex_select,v,*g) != 0; } const Graph* g; }; --------------------------------------------------------------------------------- I am calling this function as below. ----------------------------------------------------------------------------------------- graph_t G_copy2; copy_graph(make_filtered_graph(G, keep_all(), select_vertex<graph_t>(G)), G_copy2); ---------------------------------------------------------------------------------------- here G is my original Graph. please let me know where I am doing wrong. Regards, Srinivas On Tue, Jan 3, 2012 at 6:49 AM, Cedric Laczny <cedric.laczny@gmx.de> wrote:
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 time-expensive 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/control-flow-ana-2.pdf )
Regards, Srinivas
Hope that helps.
Best,
Cedric _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Cedric Laczny
-
srinivas boppu