Re: [Boost-users] [BGL] Searching for a convenient way to combine predicates for filtered_graph (SOLVED)

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