
Boost Users : 
Subject: Re: [Boostusers] [BGL] Is it possible to control algorithm's behavior by visitor?
From: Li Ning (Ning.c.Li_at_[hidden])
Date: 20090522 05:29:31
Dmitry Bufistov wrote:
>
> 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 mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
>
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 bidirection connection means you can send data from A to B AND B to A at
max width 5M.
A unidirection 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 directedgraph. Because a bi
connection can not go through different "line".
This problem requires graph has it runtime type, that is, when routing
uniconnection, graph should be a directedgraph. when routing
biconnection, graph should be a undirectedgraph. If we need to avoid
recreate graph when connection direction type changes, we must...customize
BGL.
The best solution I can figure out is reduce the problem to a undirectgraph
but its edge has complex properties. These properties value affect algorithm
behavior.
The problem is: how to do this??
recreation 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/BGLIsitpossibletocontrolalgorithm%27sbehaviorbyvisitortp23648334p23667202.html Sent from the Boost  Users mailing list archive at Nabble.com.
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