Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Is it possible to control algorithm's behavior by visitor?
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2009-05-21 05:55:03

Li Ning 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.

What about to create a sub-graph that filters out all edges with
capacities less than x ?

> More step, a undirected graph with special edge which has 2 separated
> capacity. One for source--->target, other for target---->source. If a path
> go through this edge from edge's source vertex to target vertex, capacity of
> "source--->target" will decrease. (note undirected graph edge has no
> direction but it still has source & target vertex). The usage of capacity is
> ruled by identity of edge's direction and path's direction.

Probably you should consider to use a directed graph instead :)

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

I think that some algorithms of BGL are easy to extend.


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