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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-22 14:02:32

> 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