Re: [Boost-users] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?

Subject: Re: [Boost-users] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
From: Tristram Gräbener (tristramg_at_[hidden])
Date: 2008-10-23 07:22:07

> Well, that's something I didn't consider.  I'm sure you're right.
> Now I'm just being curious.  If your cost function is the same for every
> edge, you could move the real work of the cost function to the combine
> method.  (If it varies between graphs, you could make the function pointer a
> member of the struct.)  The weight_map could then return some other value
> that the cost function uses (or ignores).

Maybe I should explain what I'm doing ;)

I work on multimodal transportation (combining diffrent means of transport):
the time you spend for taking the bus depends on the time you arrive
at the bus stop (waiting time)
the time you spend on a road edge depends on the time of the day (rush
hour or not)
And of course the time depends on the path you took before. Thus you
can't precalculate the weight (and every edge has a different cost
function).

A possible work arround would be a operator()<(float) { return true;}
to my cost functions.

>
>> (the documentation states that the distance_map and weight_map do not need
>> to be of the same type).
>
> Since I just read it, I feel I should correct that.
> http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths.html
> The last sentence describing weight_map says that they should be the same
> type.  However, I think that condition could (and should) be relaxed.

Urg, sorry! Indeed it's quite clear...
I thought about (on the same page):
"The CombineFunction type must be a model of Binary Function. The
first argument type of the binary function must match the value type
of the DistanceMap property map and the second argument type must
match the value type of the WeightMap property map" so I assumed they
can be different.

> As for the discussion of the edge-checking condition, every description of
> Dijkstra's algorithm that I've read says that it only guarantees a correct
> answer when edges have non-negative weights.  Really, we can generalize that
> to "compare(d[u], combine(d[u], w[e])) must be true," as you stated.  I
> don't know how to do that with this library, since examine_edge considers
> the edge, but not the distance.  I suspect that it will require interface
> changes, though they may be minor.  Again, I'm not familiar with the
> library, only with the algorithm.

The following patch could do it (but it changes a more general
function relax, so I'm not sure of the implications on other
algorithms)

diff /usr/include/boost/graph/dijkstra_shortest_paths.hpp
/usr/include/boost/graph_old/dijkstra_shortest_paths.hpp
120a121,122
>         if (m_compare(get(m_weight, e), m_zero))
>           throw negative_edge();
diff /usr/include/boost/graph/relax.hpp /usr/include/boost/graph_old/relax.hpp
16d15
< #include <boost/graph/exception.hpp>
53,55d51
<       if ( compare(combine(d_u, w_e), d_u) ) {
<           throw negative_edge();
<       }

Do you think I should contact the dev mailing list in order to get an
opinion more of the internals ?