# Boost :

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

The helper dfs routine is a good addition.

-Jonathan

> 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
>
> - Volodya
>
>
>
>
>
> ------------------------------------------------------------------------
>
>
> #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;
>
>
> 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