
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 23:09:31
Jeremiah Willcock wrote:
>
>> 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.
>
> Are you sure you don't want a maxflow algorithm instead? Some algorithm
> that finds optimal flows with costs for edges? Are you trying to find the
> shortest path by adding up the costs of the edges? If you are trying to
> find the shortest path using only edges with a certain capacity left, you
> can ignore directions; using both directions of an undirected edge would
> create a cycle in the output path, which is not possible with only
> positive edge weights.
>
> You might want to look through
> http://stuff.mit.edu/afs/athena.mit.edu/course/other/urban_or_book/www/////book/chapter6/contents6.html
> to see if any of those problems match what you are trying to do. I am not
> completely sure whether you really want a shortestpath algorithm or
> something else.
>
>  Jeremiah Willcock
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
>
Yes, it is a shortest path problem with complex capacity usage. The path I
need to find is lowest cost path. So maxflow won't help because it gives
you a distribution rather than a path.
 View this message in context: http://www.nabble.com/BGLIsitpossibletocontrolalgorithm%27sbehaviorbyvisitortp23648334p23680978.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