Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Searching for a convenient way to combine predicates for filtered_graph (SOLVED)
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-12-01 07:27:05


On Monday, 29. November 2010 18:27:43 Nat Linden wrote:
> On Mon, Nov 29, 2010 at 10:43 AM, Cedric Laczny
> <cedric.laczny_at_[hidden]>wrote:
>
> I was wondering if there is a convenient (and to some extent intuitive) way
>
> > to
> > combine several predicates used in filtering a graph?
> > The idea is to have some predicates defined and arbitrarily combine them
> > so that the filtered_graph will check for compliance of each individual
> > predicate
> > and either make this vertex/edge visible or not.
> > Something like
> > big_predicate = predicate1 || predicate2 || predicate3
> > (syntax should just illustrate the idea) maybe?

I was able to find a solution using boost::bind and boost::function.
The example is based on the boost example on filtered_graphs and this link
http://stackoverflow.com/questions/1044703/how-do-you-pass-boostbind-objects-
to-a-function/1044732#1044732

Let's explain the example a bit.

The predicates should only make edges visible with a positive edge weight or
with a negative one(positive_edge_weight or negative_edge_weight). So one
might want to use those separately, which is the regular case IMHO.

But, in case one now wants to filter on the edges that do NOT satisfy either of
the predicates, defining a new predicate that simply tests if the edge_weight
is actually zero would be a feasible solution.

In order to recycle code, my prefered solution would be to combine these
predicates. For complex predicates it might be way easier to combine them and
at the same time likelihood decreases to introduce some programming error in
the new predicate.

Thanks to the overloaded operators from boost::bind this is fairly straight-
forward:

!boost::bind(pos_filter, _1) && !boost::bind(neg_filter, _1))

Please note that the "!" negates the predicate, because, after all, we only
want the edges with a weight of zero.
You will probably find such examples quite often, but usually they will be used
directly, making the specification of a return type obsolete.
However, for some purposes, especially filtered_graph, it is necessary to
provide a (return) type.
And this is where boost::function comes into play. Details on that library can
be found in the boost documentation and I only want to demonstrate the usage
here.
boost::function allows us to define a return type for our combined function
objects. Because these function objects only have one member function
(operator()) which returns a bool-type, we can combine them with the
operator&& and still will have the same return type, which is "bool".

If we now look at

typedef boost::function< bool( Edge ) > CombinedPred;

we see the return type in the template-specification of boost::function. "Edge"
represents the input parameter type of our function object's operator().
One could translate that definition into: Create a "function" that returns and
object of "bool" on an argument of type "Edge". And because our both
predicates here behave equally (concerning input type and return type) we can
nicely combine them.
Furhter usage of this combined predicate is analogous to the usage of function
objects in filtered_graph.

Here's the complete, working example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/bind.hpp>
#include <boost/function.hpp>

#include <iostream>

template <typename EdgeWeightMap>
struct positive_edge_weight {
  positive_edge_weight() { }
  positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }

  // Purpose of this, please see
http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#with_function_objects
  // in "struct F2"
  typedef bool result_type;

  template <typename Edge>
  result_type operator()(const Edge& e) const {
    return 0 < get(m_weight, e);
  }
  EdgeWeightMap m_weight;
};

template <typename EdgeWeightMap>
struct negative_edge_weight {
  negative_edge_weight() { }
  negative_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }

  // Purpose of this, please see
http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#with_function_objects
  // in "struct F2"
  typedef bool result_type;

  template <typename Edge>
  result_type operator()(const Edge& e) const {
    return 0 > get(m_weight, e);
  }
  EdgeWeightMap m_weight;
};

int main()
{
  using namespace boost;
  
  typedef adjacency_list<vecS, vecS, directedS,
    no_property, property<edge_weight_t, int> > Graph;
  typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap;

  enum { A, B, C, D, E, N };
  const char* name = "ABCDE";
  Graph g(N);
  add_edge(A, B, 2, g);
  add_edge(A, C, 0, g);
  add_edge(C, D, 1, g);
  add_edge(C, E, 0, g);
  add_edge(D, B, 3, g);
  add_edge(E, C, 0, g);

  typedef Graph::edge_descriptor Edge;

  typedef positive_edge_weight<EdgeWeightMap> PosEW;
  typedef negative_edge_weight<EdgeWeightMap> NegEW;

  PosEW pos_filter(get(edge_weight, g));
  NegEW neg_filter(get(edge_weight, g));
  
  // HERE we define the type for our combined predicate
  typedef boost::function< bool( Edge ) > CombinedPred;

  // This is where we actually combine the separate predicates
  // Please note the ! before "boost". It negates the applied filter
  // This results in a combined filter/predicate that only makes edges visible
with a weight of zero
  CombinedPred combined_pred = (!boost::bind(pos_filter, _1) &&
!boost::bind(neg_filter, _1));

  // See the type of the combined predicate?!
  filtered_graph<Graph, CombinedPred >
    fg(g, combined_pred);

  //Only the edges between A and C, between C and E and between E and C should
be printed!
  std::cout << "filtered edge set: ";
  print_edges(fg, name);

  std::cout << "filtered out-edges:" << std::endl;
  print_graph(fg, name);
  
  return 0;
}

Thanks again to all who made suggestions, directly or indirectly.

Best,

Cedric


Boost-users 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