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 05:29:31

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_at_[hidden]
>>>
>> 
>> 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_at_[hidden]
> 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-by-visitor--tp23648334p23667202.html
Sent from the Boost - Users mailing list archive at Nabble.com.