Boost logo

Boost Users :

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
> 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]

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:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at