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