Re: [Boost-users] [graph] Implementing turn restrictions

Subject: Re: [Boost-users] [graph] Implementing turn restrictions
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-11-04 11:28:15

on Thu Nov 03 2011, Stephen Woodbridge <woodbri-AT-swoodbridge.com> wrote:

> Hi all,
>
> I need to solve Dijkstra shortest path with turn restrictions. I am
> wondering if anyone has an example of how to implement this?
>
> I'm thinking that this can be done something like this:
>
> 1. a restriction(s) could be represented as: at a given node X if my
> ancestry is some list of of nodes, then restrict going forward to a
> node or list of nodes.
>
> 2. any given node can optionally have a list of restrictions attached to it
>
> 3. a visitor function would then get the list of restrictions for the
> visited node and compare ancestor list of each restriction to the
> current path ancestry and then filter forward nodes if there is an
> ancestry match(s).
>
> Does this sound like a reasonable approach?

I don't think that's enough.  Dijkstra depends on the idea that any path
that reaches a node X can be joined to any path that proceeds from node
X.  IMO your underlying graph G=(V,E) isn't the appropriate one to which
to apply Dijkstra.  IMO you need to produce a different graph G' having
a distinct vertex descriptor for each distinct pair (v,S) where v ∋ V
and S is a set of available outgoing edges in of v.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com