Subject: [Boost-commit] svn:boost r85387 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2013-08-17 18:21:16
Author: jewillco
Date: 2013-08-17 18:21:16 EDT (Sat, 17 Aug 2013)
New Revision: 85387
URL: http://svn.boost.org/trac/boost/changeset/85387
Log:
Simplified negative-edge test; refs #9012
Text files modified:
trunk/boost/graph/dijkstra_shortest_paths.hpp | 13 ++++++-------
1 files changed, 6 insertions(+), 7 deletions(-)
Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp Sat Aug 17 18:12:20 2013 (r85386)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp 2013-08-17 18:21:16 EDT (Sat, 17 Aug 2013) (r85387)
@@ -162,7 +162,7 @@
void examine_edge(Edge e, Graph& g) {
// Test for negative-weight edges:
//
- // Reasons that simpler comparisons do not work:
+ // Reasons that other comparisons do not work:
//
// m_compare(e_weight, D(0)):
// m_compare only needs to work on distances, not weights, and those
@@ -179,16 +179,15 @@
// m_combine be able to take a distance and a weight (in that order)
// and return a distance.
- D source_dist = get(m_distance, source(e, g));
- W e_weight = get(m_weight, e);
+ // W e_weight = get(m_weight, e);
// sd_plus_ew = source_dist + e_weight.
- D sd_plus_ew = m_combine(source_dist, e_weight);
+ // D sd_plus_ew = m_combine(source_dist, e_weight);
// sd_plus_2ew = source_dist + 2 * e_weight.
- D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
+ // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
// The test here is equivalent to e_weight < 0 if m_combine has a
// cancellation law, but always returns false when m_combine is a
- // projection operator or is idempotent.
- if (m_compare(sd_plus_2ew, sd_plus_ew))
+ // projection operator.
+ if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero))
boost::throw_exception(negative_edge());
// End of test for negative-weight edges.