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 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 un-direct 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 bi-connection. bi-connection will use a
>> line's az & za capaciy together. It requires both az & za must belong to
>> same line. That means bi-connection's send data path & receive data path
>> MUST have same edge sequence.
>>
>> Now clear all connections and edge properties in this graph. Let
>> re-assign
>> 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 bi-connection c1 with bandwidth 4 from A to C is: a---b---d----e----c,
>> cost 4. smaller than a----b----c, 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 bi-connection actually a path in un-directed graph. uni-connection is
>> path in directed graph. Of course a path can not contain any cycle, that
>> is
>> meaningless.
>> If we only routing uni-connection, then it is a classical finding path
>> problem in directed graph.
>> If we only routing bi-connection, then it is a classical finding path
>> problem in un-directed graph.
>> What if sometimes we need to routing uni-connection, sometimes we need to
>> routing bi-connection in a single graph?
>> The only solution I can figure out is reduce them to a un-directed 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 max-flow 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 shortest-path algorithm or 
> something else.
> 
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> 

Yes, it is a shortest path problem with complex capacity usage. The path I
need to find is lowest cost path. So max-flow won't help because it gives
you a distribution rather than a path.
-- 
View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior-by-visitor--tp23648334p23680978.html
Sent from the Boost - Users mailing list archive at Nabble.com.