Re: [Boost-users] [BGL] Is it possible to control algorithm's behavior by visitor?

Subject: Re: [Boost-users] [BGL] Is it possible to control algorithm's behavior by visitor?
From: Li Ning (Ning.c.Li_at_[hidden])
Date: 2009-05-22 03:29:44

Andrew Sutton-2 wrote:
> 
>> For example, a graph's edge have 2 property: weight & capacity. I need to
>> compute a path which have min weight and any edges in this path has
>> bigger
>> capacity than 'x'.
>>
>> Seems BGL can't do this uniformly because shortest_path function has no
>> place to accept others parameter(constraints). Some functors such as
>> distance_compare seems only work on weight.
> 
> 
> That's not entirely true. distance_compare compares the results of lookups
> on the distance_map provided to the function. A property map is actually
> very much like a functor except that it supports reads and writes. This
> means you can build a custom property map that returns (for example) a
> pair
> containing the weight and capacity for each edge. The distance_compare
> function would then compare the resulting pairs.
> 
> I mean BGL cope with pure graph theory problem nicely, but when the
>> application gets complex(still can be reduced to pure graph data
>> structure,
>> but more rules restricted on algorithm), BGL fails.
> 
> Am I right?
> 
> 
> Not really.
> 
> Andrew Sutton
> andrew.n.sutton_at_[hidden]
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 

I think self-define weight property is not enough. Because the things you
can control is how the way '<' & '+' executed. But you can not control how
to reject a edge & examine a edge(only visit). 

So, base the model I proposed, you may define weight like this:
struct SelfWeight
{
    int cost;
    unsigned int az_capacity;
    unsigned int za_capacity;
};
and implement operator< & operator+
How to use them reject a edge that capacity lower than required, it seems no
way.
Let alone choose capacity(az or za) you algorithm should use.

If I use BGL as the core, I have to re-generate BGL graph when the type(uni
or bi direction) of path change. This is bad.

If BGL make all visitors to functors... seems possible?
-- 
View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior-by-visitor--tp23648334p23665853.html
Sent from the Boost - Users mailing list archive at Nabble.com.