[BGL] Searching for a convenient way to combine predicates for filtered_graph
Hi, 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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe? Best, Cedric
On Mon, Nov 29, 2010 at 10:43 AM, Cedric Laczny <cedric.laczny@gmx.de>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?
Have you considered Phoenix? (thought I'd mention it before OvermindDL1 this time)
Hi, On Monday, 29. November 2010 18:27:43 Nat Linden wrote:
On Mon, Nov 29, 2010 at 10:43 AM, Cedric Laczny <cedric.laczny@gmx.de>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?
Have you considered Phoenix? (thought I'd mention it before OvermindDL1 this time)
Thank you. No, this is entirely new to me. I had a quick look on it and it definitely seems to be a possible solution. Because it is a quite broad topic and there are different things to take care of, do you have any particular topics that are covering solution to my intention (Actors, Operators etc.)? I am concerned actually about the type that such a combination of predicates might have, because the type has to be provided to the filtered_graph- template... Best, Cedric
On Monday, 29. November 2010 18:27:43 Nat Linden wrote:
On Mon, Nov 29, 2010 at 10:43 AM, Cedric Laczny <cedric.laczny@gmx.de>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_objec... // 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_objec... // 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
Hi, in case someone might ask "Is it possible to create some sort of "nested" combined predicates"? Or incrementally construct a predicate? Actually, it is! Let's say, we have got the positive_edge_weight predicate(functor) from the filtered_graph example again and also the negative_edge_weight predicate(functor). Then we can do something like this: // HERE we define the type for our combined predicate typedef boost::function< bool( Edge ) > CombinedPred; // First predicate CombinedPred combined_pred = (boost::bind(pos_filter, _1) ); // Second predicate combined_pred = boost::bind(combined_pred, _1) || boost::bind(neg_filter, _1); This would then _hide_ all the edges having an edge weight of zero of course. This solution allows the arbitrary combination of predicates and also an incremental construction of even more complex predicates. One scenario I could think of is a vector (or any other container) of integers representing edge_weights of interest. Then the definion of a single predicate(functor) having a single integer as argument, would be enough, using this approach, to create a predicate covering _all_ the edge_weights of interest. Of course, one could also define a predicate directly that takes this vector as an argument. But this would not be very flexible IMHO. However, I don't know which solution would perform better when being applied to a filtered_graph. Maybe the overhead of all that binding would cost, although I could imagine that going over the vector for each edge might also cost something when compared to simply checking a combination of logical operations. Best, Cedric
On Mon, 29 Nov 2010, Cedric Laczny wrote:
Hi,
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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe?
If you don't want to use Boost.Lambda, Boost.Bind also has some operators overloaded (<URL:http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#operators>) to provide the syntax you wanted. -- Jeremiah Willcock
On Tuesday, 30. November 2010 16:57:17 Jeremiah Willcock wrote:
On Mon, 29 Nov 2010, Cedric Laczny wrote:
Hi,
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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe?
If you don't want to use Boost.Lambda, Boost.Bind also has some operators overloaded (<URL:http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#operators>) to provide the syntax you wanted.
Thanks for the hint. Unfortunately, I'm still hanging at the point where the type of the specified predicate(s) comes into play. Let's look at an example: struct VPred1{ VPred1() {}; // etc.... template< V > bool operator( const V& v) {return true;} } struct Vpred2{ // s. Vpred1 but operator() returns false } Vpred1 pred1; Vpred2 pred2; typedef adjacency_list<> Graph; Graph g; // fill graph g filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), ???); In the example above I would like to provide both vpred-structs to the filtered_graph like so: filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), pred1 && pred2); This is not supposed to work out-of-the-box, it should just demonstrate the idea a bit more into detail. Concerning the "???" in the template-specification, I have no idea how this should be specifed. All the examples I have found so far, either for phoenix or bind, are direct applications and do not involve the specification of templates. Therefore I have nowhere to start learning how to do this.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
On Tue, 30 Nov 2010, Cedric Laczny wrote:
On Tuesday, 30. November 2010 16:57:17 Jeremiah Willcock wrote:
On Mon, 29 Nov 2010, Cedric Laczny wrote:
Hi,
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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe?
If you don't want to use Boost.Lambda, Boost.Bind also has some operators overloaded (<URL:http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#operators>) to provide the syntax you wanted.
Thanks for the hint. Unfortunately, I'm still hanging at the point where the type of the specified predicate(s) comes into play. Let's look at an example:
struct VPred1{ VPred1() {}; // etc.... template< V > bool operator( const V& v) {return true;} } struct Vpred2{ // s. Vpred1 but operator() returns false }
Vpred1 pred1; Vpred2 pred2; typedef adjacency_list<> Graph; Graph g; // fill graph g filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), ???);
In the example above I would like to provide both vpred-structs to the filtered_graph like so: filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), pred1 && pred2);
This is not supposed to work out-of-the-box, it should just demonstrate the idea a bit more into detail.
Concerning the "???" in the template-specification, I have no idea how this should be specifed. All the examples I have found so far, either for phoenix or bind, are direct applications and do not involve the specification of templates. Therefore I have nowhere to start learning how to do this.
Yes, that's the hard part. If you have C++0x (or are willing to use compiler extensions), you can use decltype/auto or typeof to infer the return type of the operator. Another technique (that would make your code messy) is to split the function after the construction of the predicate into a separate function template; that template can then take the predicate as a parameter and its type as a template parameter. You could also try asking the bind developers if the return types of the operators are documented, or if they would fix and document particular types for them. -- Jeremiah Willcock
On Tuesday, 30. November 2010 17:41:13 Jeremiah Willcock wrote:
On Tue, 30 Nov 2010, Cedric Laczny wrote:
On Tuesday, 30. November 2010 16:57:17 Jeremiah Willcock wrote:
On Mon, 29 Nov 2010, Cedric Laczny wrote:
Hi,
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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe?
If you don't want to use Boost.Lambda, Boost.Bind also has some operators overloaded (<URL:http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#operators
) to provide the syntax you wanted.
Thanks for the hint. Unfortunately, I'm still hanging at the point where the type of the specified predicate(s) comes into play. Let's look at an example:
struct VPred1{
VPred1() {}; // etc.... template< V > bool operator( const V& v) {return true;}
} struct Vpred2{ // s. Vpred1 but operator() returns false }
Vpred1 pred1; Vpred2 pred2; typedef adjacency_list<> Graph; Graph g; // fill graph g filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), ???);
In the example above I would like to provide both vpred-structs to the filtered_graph like so: filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), pred1 && pred2);
This is not supposed to work out-of-the-box, it should just demonstrate the idea a bit more into detail.
Concerning the "???" in the template-specification, I have no idea how this should be specifed. All the examples I have found so far, either for phoenix or bind, are direct applications and do not involve the specification of templates. Therefore I have nowhere to start learning how to do this.
Yes, that's the hard part. If you have C++0x (or are willing to use compiler extensions), you can use decltype/auto or typeof to infer the return type of the operator. Another technique (that would make your code messy) is to split the function after the construction of the predicate into a separate function template; that template can then take the predicate as a parameter and its type as a template parameter. You could also try asking the bind developers if the return types of the operators are documented, or if they would fix and document particular types for them.
Ok, I will do that then. But let's say, the return types were known, am I right that a solution to combine the predicates would have to look like this? filtered_graph<> fg(g, keep_all(), bind<bool>(pred1, _1) && bind<bool>(pred2, _1)); Thank you so far.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
On Tue, 30 Nov 2010, Cedric Laczny wrote:
On Tuesday, 30. November 2010 17:41:13 Jeremiah Willcock wrote:
On Tue, 30 Nov 2010, Cedric Laczny wrote:
On Tuesday, 30. November 2010 16:57:17 Jeremiah Willcock wrote:
On Mon, 29 Nov 2010, Cedric Laczny wrote:
Hi,
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. Of course, the predicates should be specific to vertices or edges, respectively, when being combined. When using std::vector or such, they would need to be all of the same type which does not seem very nice/feasible IMHO. Also defining a "big" predicate having a multitude of "smaller" predicates as members is not really an option as this is very restricted. Something like big_predicate = predicate1 || predicate2 || predicate3 (syntax should just illustrate the idea) maybe?
If you don't want to use Boost.Lambda, Boost.Bind also has some operators overloaded (<URL:http://www.boost.org/doc/libs/1_45_0/libs/bind/bind.html#operators
) to provide the syntax you wanted.
Thanks for the hint. Unfortunately, I'm still hanging at the point where the type of the specified predicate(s) comes into play. Let's look at an example:
struct VPred1{
VPred1() {}; // etc.... template< V > bool operator( const V& v) {return true;}
} struct Vpred2{ // s. Vpred1 but operator() returns false }
Vpred1 pred1; Vpred2 pred2; typedef adjacency_list<> Graph; Graph g; // fill graph g filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), ???);
In the example above I would like to provide both vpred-structs to the filtered_graph like so: filtered_graph< Graph, keep_all, ??? > fg( g, keep_all(), pred1 && pred2);
This is not supposed to work out-of-the-box, it should just demonstrate the idea a bit more into detail.
Concerning the "???" in the template-specification, I have no idea how this should be specifed. All the examples I have found so far, either for phoenix or bind, are direct applications and do not involve the specification of templates. Therefore I have nowhere to start learning how to do this.
Yes, that's the hard part. If you have C++0x (or are willing to use compiler extensions), you can use decltype/auto or typeof to infer the return type of the operator. Another technique (that would make your code messy) is to split the function after the construction of the predicate into a separate function template; that template can then take the predicate as a parameter and its type as a template parameter. You could also try asking the bind developers if the return types of the operators are documented, or if they would fix and document particular types for them.
Ok, I will do that then. But let's say, the return types were known, am I right that a solution to combine the predicates would have to look like this?
filtered_graph<> fg(g, keep_all(), bind<bool>(pred1, _1) && bind<bool>(pred2, _1));
Yes, probably, unless you made pred1 and pred2 look like bind-produced predicates (I don't know how to do that; it might be in the bind manual but I haven't checked). -- Jeremiah Willcock
participants (2)
-
Cedric Laczny -
Jeremiah Willcock -
Nat Linden