Li, Li Ning wrote:
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@gmail.com
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?
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