
Boost Users : 
Subject: Re: [Boostusers] [BGL] Is it possible to control algorithm's behavior by visitor?
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 20090522 04:57:29
Li,
Li Ning wrote:
>
>
> Andrew Sutton2 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]
>>
>
> I think selfdefine 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 regenerate BGL graph when the type(uni
> or bi direction) of path change. This is bad.
>
> If BGL make all visitors to functors... seems possible?
If you provide a formal description of the original problem and a small
example, I will try to show you the power of BGL :)
Regards,
Dmitry
Boostusers 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