
Boost : 
From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 20051207 11:31:41
On Wed, Dec 07, 2005 at 09:38:28AM 0500, Douglas Gregor wrote:
>
> On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
> > is there any interest in including an algorithm for solving the
> > shortest
> > path problem with resource constraints (SPPRC) in the Boost Graph
> > library?
>
> Yes!
>
I would second it; many more algorithms are needed.
> > I've implemented an exact algorithm for this NPhard problem. The
> > algorithm is basically a labelsetting algorithm based on dynamic
> > programming. It is parameterized on the graph type (of course) and the
> > type of the resource container (data structures specifying what
> > resources there are and how they are to be managed in the course of
> > the
> > algorithm).
For such hard problems there is an enormous design space (and an even
bigger algorithm space) to be considered, so a good dose of genericity
in the implementation would be appreciated (hopefully it comes with
concepts?).
Since it's NPhard, it would be good to have also a reduction from
some wellknown NPcomplete problem to SPPRC (for example graph
colouring), which would be very useful for testing (using some
established implementation for that NPcomplete problem).
Oliver
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk