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: Dave Steenburgh (dave.steenburgh_at_[hidden])
Date: 2008-10-23 10:40:37

>
> 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).
>>
> 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).

Cool, I wondered what the application was.  Now it makes sense.
I figured that your edges would have different cost functions, but thought I
should mention it anyway.

>
>>
> > (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
>> <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.
>> <http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths.html>
>
> 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.

That does imply that they can be different...I'd say one or both of those
statements needs to change.

>  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();
> <       }

Well, the Bellman-Ford algorithm includes the same header, and so probably
uses the same function.  Since it works with negative edges (but not
negative cycles), this patch isn't the way to go.

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

Since nobody else is weighing in on this discussion, and all my knowledge of
the graph library was learned in the last 24 hours, I'd say yes.  Be sure to
mention the discrepancy in the documentation about value types.

This is just wishful thinking on my part, but I wonder if the distance could
be incorporated into the edge descriptor, or the vertex descriptor?  I
imagine that would require even more changes, but it would allow weight_map
to calculate the edge weight, and examine_edge could stay as-is.