Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] need suggestion
From: srinivas boppu (srinivas.fau_at_[hidden])
Date: 2012-01-06 12:12:20

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)
    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)),
here G is my original Graph.

please let me know where I am doing wrong.


On Tue, Jan 3, 2012 at 6:49 AM, Cedric Laczny <cedric.laczny_at_[hidden]> 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
> >
> > )
> >
> > Regards,
> > Srinivas
> Hope that helps.
> Best,
> Cedric
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

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