[boost] Re: [BGL] dag_shortest_paths broken?

From: Jonathan Graehl (jonathan_at_[hidden])
Date: 2004-10-11 01:17:59

The algorithm wasn't broken, but your improvement is superb.

Why not also fix closed_plus (so that it handles negative overflow as 
well as positive? - or is it documented that it doesn't handle negative 
weights?)  This should make the old dag_shortest_paths give the correct 
answer, as well as your new version.

The helper dfs routine is a good addition.

-Jonathan

Vladimir Prus wrote:
> Hello,
> it appears that the dag_shortest_paths algorithm is broken. The attached 
> program tries to find the longest path by changing inf/comparison operators. 
> The graph is
> 
> 0  ----->   1  ------>  2
>                 ^
>                 |
> 3 ----------/
> 
> The edge weights are 1 for  0->1 and 1->2 and 2 for 3->1 and I'm searching for 
> the longest path starting from '0'. The final result for '2' is 0x7FFFFFFF, 
> while I'd expect to get '2'.
> 
> The problem is two-fold. First, the algorithm runs topological sort on the 
> graph, and process the vertices in topological order -- which include the '3' 
> vertex. That vertex is not reachable from '0', so it should not be included 
> in the search at all.
> 
> The second problem is that the distance to that vertex is set to -inf. When 
> combining that distance with edge weight, due to a bug we get +inf. Here's 
> the code:
> 
>     template <class T>
>     struct closed_plus
>     {
>       // std::abs just isn't portable :(
>       template <class X>
>       inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
> 
>       T operator()(const T& a, const T& b) const {
>         using namespace std;
>         T inf = (numeric_limits<T>::max)();
>         if (b > 0 && my_abs(inf - a) < b)
>           return inf;
>         return a + b;
>       }
>     };
> 
> When 'a' is -inf (as is for '3') inf - a overflows and gives -1, and when b is 
> greater than 1, "inf" is returned.
> 
> I think that the right solution is to change the algorithm so that it does not 
> traverse the vertices not reachable from the start one. Besides fixing my 
> problem, this will also speed up the algorithm. For example, if you have a 
> forest and call dag_shortest_path on the root of just one tree, the algorithm 
> will travese all trees, setting pretty useless values for all of them.
> 
> I would like to commit the attached patch. All tests still pass on gcc when 
> it's applied. Comments? 
> 
> - Volodya
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> 
> #include <boost/graph/adjacency_list.hpp>
> #include <boost/graph/dag_shortest_paths.hpp>
> #include <boost/vector_property_map.hpp>
> using namespace boost;
> 
> #include <iostream>
> using namespace std;
> 
> int main()
> {
>     typedef adjacency_list<vecS, vecS, directedS, no_property,
>         property<edge_weight_t, int> > Graph;
> 
>     Graph graph;
>     Graph::vertex_descriptor v1, v2, v3, v4;
> 
>     v1 = add_vertex(graph);
>     v2 = add_vertex(graph);
>     v3 = add_vertex(graph);
>     v4 = add_vertex(graph);
> 
>     Graph::edge_descriptor e;
>     
>     e = add_edge(0, 1, graph).first;
>     put(edge_weight, graph, e, 1);
> 
>     e = add_edge(1, 2, graph).first;
>     put(edge_weight, graph, e, 1);
> 
>     e = add_edge(3, 1, graph).first;
>     put(edge_weight, graph, e, 5);
> 
>     vector_property_map<int> distance;
> 
>     dag_shortest_paths(graph, 0,
>                        distance_map(distance)
>                        .distance_compare(std::greater<int>())
>                        .distance_inf(std::numeric_limits<int>::min())
>                        .distance_zero(0));
> 
>     cout << distance[2] << "\n";
> 
> 
> 
> }
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> Index: dag_shortest_paths.hpp
> ===================================================================
> RCS file: /cvsroot/boost/boost/boost/graph/dag_shortest_paths.hpp,v
> retrieving revision 1.13
> diff -u -r1.13 dag_shortest_paths.hpp
> --- dag_shortest_paths.hpp	26 Feb 2004 18:26:47 -0000	1.13
> +++ dag_shortest_paths.hpp	7 Oct 2004 14:05:38 -0000
> @@ -49,7 +49,16 @@
>      typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
>      std::vector<Vertex> rev_topo_order;
>      rev_topo_order.reserve(num_vertices(g));
> -    topological_sort(g, std::back_inserter(rev_topo_order));
> +
> +    // Call 'depth_first_visit', not 'topological_sort', because we don't
> +    // want to traverse the entire graph, only vertices reachable from 's',
> +    // and 'topological_sort' will traverse everything. The logic below
> +    // is the same as for 'topological_sort', only we call 'depth_first_visit'
> +    // and 'topological_sort' calls 'depth_first_search'.
> +    topo_sort_visitor<std::back_insert_iterator<std::vector<Vertex> > >
> +        topo_visitor(std::back_inserter(rev_topo_order));
> +    depth_first_visit(g, s, topo_visitor);
> +
>  
>      typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
>      for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
> Index: depth_first_search.hpp
> ===================================================================
> RCS file: /cvsroot/boost/boost/boost/graph/depth_first_search.hpp,v
> retrieving revision 1.41
> diff -u -r1.41 depth_first_search.hpp
> --- depth_first_search.hpp	26 Mar 2004 16:25:08 -0000	1.41
> +++ depth_first_search.hpp	7 Oct 2004 14:05:38 -0000
> @@ -379,6 +379,19 @@
>      detail::depth_first_visit_impl(g, u, vis, color, func);
>    }
>  
> +  template<class IncidenceGraph, class DFSVisitor>
> +  void depth_first_visit(
> +      const IncidenceGraph& g,
> +      typename graph_traits<IncidenceGraph>::vertex_descriptor u,
> +      DFSVisitor vis)
> +  {
> +    std::vector<default_color_type> color_map(num_vertices(g));
> +
> +    depth_first_visit(g, u, vis, 
> +                      make_iterator_property_map(&color_map[0],
> +                                                 get(vertex_index, g)));
> +  }
> +
>  
>  } // namespace boost
>  
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost