Dmitry Bufistov wrote:
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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
OK! Well, the problem come from telecom. In telecom, network element can be viewed as vertex. network element is a device that can be plug in "lines"(optic, ethernet or anything can transmit data). These "lines" have a character: composited by 2 transmition medium. So if 2 network element was connected by a line, you can send data from source to target or from target to source. But notice that 2 direction has independent band width. For example, a 5M line connect vertex A & B, you can establish a connection between A & B. This connection have 2 type: uni or bi. A bi-direction connection means you can send data from A to B AND B to A at max width 5M. A uni-direction connection means you can ONLY send data from A to B OR B to A(depend on connection's source & destination), the line between A & B has been used only one capacity. That is, only one transmition medium in this line has been used. So, a line can contain 2 uni connection(one is A to B, another is B to A) or 1 bi connection. This problem requires dijkstra algorithm accept one more parameter: Path's Direction. BGL have not this. This problem requires graph can not be a directed-graph. Because a bi connection can not go through different "line". This problem requires graph has it runtime type, that is, when routing uni-connection, graph should be a directed-graph. when routing bi-connection, graph should be a undirected-graph. If we need to avoid re-create graph when connection direction type changes, we must...customize BGL. The best solution I can figure out is reduce the problem to a undirect-graph but its edge has complex properties. These properties value affect algorithm behavior. The problem is: how to do this?? re-creation graph is easy. But this creation cost is high: based on a graph, routing 100,000 connections need to create graph 100,000 times in worst case. -- View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior... Sent from the Boost - Users mailing list archive at Nabble.com.