This situation can not use directed graph because these 2 separated capacity was bond together. Graph need to compute a path that can go from source to destination & from destination to source(occupy 2 capacity), or a path only can go from source to destination(occupy only one capacity according to rules). If create sub-graph, that is heavy. Because once you change the path type, you need to re-create the sub-graph. -- View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior... Sent from the Boost - Users mailing list archive at Nabble.com.

Andrew Sutton-2 wrote:

...

For example, a graph's edge have 2 property: weight & capacity. I need to compute a path which have min weight and any edges in this path has bigger capacity than 'x'.

Seems BGL can't do this uniformly because shortest_path function has no place to accept others parameter(constraints). Some functors such as distance_compare seems only work on weight.

That's not entirely true. distance_compare compares the results of lookups on the distance_map provided to the function. A property map is actually very much like a functor except that it supports reads and writes. This means you can build a custom property map that returns (for example) a pair containing the weight and capacity for each edge. The distance_compare function would then compare the resulting pairs.

I mean BGL cope with pure graph theory problem nicely, but when the

...

application gets complex(still can be reduced to pure graph data structure, but more rules restricted on algorithm), BGL fails.

Am I right?

Not really.

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I think self-define weight property is not enough. Because the things you can control is how the way '<' & '+' executed. But you can not control how to reject a edge & examine a edge(only visit). So, base the model I proposed, you may define weight like this: struct SelfWeight { int cost; unsigned int az_capacity; unsigned int za_capacity; }; and implement operator< & operator+ How to use them reject a edge that capacity lower than required, it seems no way. Let alone choose capacity(az or za) you algorithm should use. If I use BGL as the core, I have to re-generate BGL graph when the type(uni or bi direction) of path change. This is bad. If BGL make all visitors to functors... seems possible? -- View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior... Sent from the Boost - Users mailing list archive at Nabble.com.

Dmitry Bufistov wrote:

Li,

Li Ning wrote:

...

Andrew Sutton-2 wrote:

...

...

For example, a graph's edge have 2 property: weight & capacity. I need to compute a path which have min weight and any edges in this path has bigger capacity than 'x'.

Seems BGL can't do this uniformly because shortest_path function has no place to accept others parameter(constraints). Some functors such as distance_compare seems only work on weight.

That's not entirely true. distance_compare compares the results of lookups on the distance_map provided to the function. A property map is actually very much like a functor except that it supports reads and writes. This means you can build a custom property map that returns (for example) a pair containing the weight and capacity for each edge. The distance_compare function would then compare the resulting pairs.

I mean BGL cope with pure graph theory problem nicely, but when the

...

application gets complex(still can be reduced to pure graph data structure, but more rules restricted on algorithm), BGL fails. Am I right?

Not really.

Andrew Sutton andrew.n.sutton@gmail.com

I think self-define weight property is not enough. Because the things you can control is how the way '<' & '+' executed. But you can not control how to reject a edge & examine a edge(only visit).

So, base the model I proposed, you may define weight like this: struct SelfWeight { int cost; unsigned int az_capacity; unsigned int za_capacity; }; and implement operator< & operator+ How to use them reject a edge that capacity lower than required, it seems no way. Let alone choose capacity(az or za) you algorithm should use.

If I use BGL as the core, I have to re-generate BGL graph when the type(uni or bi direction) of path change. This is bad.

If BGL make all visitors to functors... seems possible?

If you provide a formal description of the original problem and a small example, I will try to show you the power of BGL :)

Regards, Dmitry

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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 bi-direction connection means you can send data from A to B AND B to A at max width 5M. A uni-direction 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. BGL have not this. This problem requires graph can not be a directed-graph. Because a bi connection can not go through different "line". This problem requires graph has it runtime type, that is, when routing uni-connection, graph should be a directed-graph. when routing bi-connection, graph should be a undirected-graph. If we need to avoid re-create graph when connection direction type changes, we must...customize BGL. The best solution I can figure out is reduce the problem to a undirect-graph but its edge has complex properties. These properties value affect algorithm behavior. The problem is: how to do this?? re-creation 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. -- View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior... Sent from the Boost - Users mailing list archive at Nabble.com.

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 bi-direction connection means you can send data from A to B AND B to A at max width 5M. A uni-direction 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 directed-graph. Because a bi connection can not go through different "line". This problem requires graph has it runtime type, that is, when routing uni-connection, graph should be a directed-graph. when routing bi-connection, graph should be a undirected-graph. If we need to avoid re-create graph when connection direction type changes, we must...customize BGL.

The best solution I can figure out is reduce the problem to a undirect-graph but its edge has complex properties. These properties value affect algorithm behavior. The problem is: how to do this??

re-creation 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

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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. -- View this message in context: http://www.nabble.com/-BGL--Is-it-possible-to-control-algorithm%27s-behavior... Sent from the Boost - Users mailing list archive at Nabble.com.

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/////b... 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@lists.boost.org 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... Sent from the Boost - Users mailing list archive at Nabble.com.