
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 13:52:54
Dmitry Bufistov wrote:
>
> [snip]
>>
>> 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.
>
> At this point you still have not stated the problem!
> Is it something like this? :
> Given a graph G=(V,E,T,C), V is a set of vertices; E is the set of
> edges. Each edge has two integer properties: edge type T: E > {UNI, BI}
> and edge capacity C: E > INT. Given two vertices: "s" (start vertex)
> and "f" (finish vertex) and a path_type (uni or bi). Your task is to
> find a shortest path P from start vertex "s" to finish vertex "f" (the
> weight map is C ??) such that all edges of this path are of the
> corresponding type (uni or bi), i.e., for each edge e \in P, T(e) ==
> path_type.
>
> It is quite strange to be true. First of all because we are trying to
> find a path with the smallest bandwidth. Something should be added to
> this formulation. Does your graph have cycles? Please, provide a small
> example (a graph with several vertices and edges).
>
>> 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.
>
> Dmitry
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
>
Sorry. I should give a example. Note that edge has no uni or bi type. All
edge is bi, az capacity for data from source to target, za capacity for data
from target to source. It is different from undirect graph edge: If edge
has capacity 5 and I go through it from source to target with 3 capacity & 2
capacity in reverse. This edge will be dead. But in telecom model, this edge
still can accommodate 2 capacity from source to target and 3 capacity in
reverse.
D====E
 
A====B====C
Above is a graph. line 1 connect A & B, line 2 connect B & C. line 1 has
cost 1, capacity 5. line 2 has cost 2, capacity 10.
Now, I want to send data from A to B at bandwidth 5, so I establish a uni
connection c1(it is uni because all I want is send, no receive). from A to
B. This c1 connection direction is from A to B and line 1 direction is from
A to B, they are identical. Notice that line has 2 separated capacity, that
means: if a line has capacity x, this line can transmit data from source to
destination at bandwidth x AND from destination to source at bandwidth x. So
we say az direction capacity of line 1 was used by c1.
After established c1, we can establish a c2 from B to A at bandwidth 5. This
c2 will use za capacity of line 1.
More step, we assume line 2's source is vertex C & destination vertex is B.
Then we can establish a uni connection c3 from A to C(forget c1 & c2 at this
moment), this c3 will use line 1's az capacity and line 2's za capacity(c3's
direction contradict with line 2).
Above is the rule of capacity usage. Cost is same as weight, the weight of
edge. A shortest path is the lowest cost path. This is same as Graph Theory.
Also, we can establish a connection used to BOTH send & receive data between
two vertex. This connection is biconnection. biconnection will use a
line's az & za capaciy together. It requires both az & za must belong to
same line. That means biconnection's send data path & receive data path
MUST have same edge sequence.
Now clear all connections and edge properties in this graph. Let reassign
them:
line(ab): cost 1, capacity 5
line(bc): cost 10, capacity 5
line(bd): cost 1, capacity 5
line(de): cost 1, capacity 5
line(ec): cost 1, capacity 5
line(xy) means edge's source vertex is x, target vertex is y.
A biconnection c1 with bandwidth 4 from A to C is: abdec,
cost 4. smaller than abc, cost 11.
After c1, can we establish a uni connection c2 from C to A with bandwidth 1?
OK
After c2, can we establish a uni connection c3 from B to A? No, because
line(ab)'s za capacity is full. They are 4(used by c1) + 1(used by c2) = 5.
Now, the capacity of line(ab) is: only az capacity has 1 available.
So biconnection actually a path in undirected graph. uniconnection is
path in directed graph. Of course a path can not contain any cycle, that is
meaningless.
If we only routing uniconnection, then it is a classical finding path
problem in directed graph.
If we only routing biconnection, then it is a classical finding path
problem in undirected graph.
What if sometimes we need to routing uniconnection, sometimes we need to
routing biconnection in a single graph?
The only solution I can figure out is reduce them to a undirected graph
with complex decision policy.
However I found BGL is hard to deal with these policy.
If you has problem about my explain, contact me.
 View this message in context: http://www.nabble.com/BGLIsitpossibletocontrolalgorithm%27sbehaviorbyvisitortp23648334p23675280.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