Login
[x]
Log in using an account from:
Fedora Account System
Red Hat Associate
Red Hat Customer
Or login using a Red Hat Bugzilla account
Forgot Password
Login:
Hide Forgot
Create an Account
Red Hat Bugzilla – Attachment 913792 Details for
Bug 1115124
prim_minimum_spanning_tree throwing negative_edge exception
[?]
New
Simple Search
Advanced Search
My Links
Browse
Requests
Reports
Current State
Search
Tabular reports
Graphical reports
Duplicates
Other Reports
User Changes
Plotly Reports
Bug Status
Bug Severity
Non-Defaults
|
Product Dashboard
Help
Page Help!
Bug Writing Guidelines
What's new
Browser Support Policy
5.0.4.rh83 Release notes
FAQ
Guides index
User guide
Web Services
Contact
Legal
This site requires JavaScript to be enabled to function correctly, please enable it.
[patch]
update boost/graph/dijkstra_shortest_paths.hpp to 1.55.0
dijkstra_1_55_0.patch (text/plain), 12.96 KB, created by
Thomas Sailer
on 2014-07-01 15:25:06 UTC
(
hide
)
Description:
update boost/graph/dijkstra_shortest_paths.hpp to 1.55.0
Filename:
MIME Type:
Creator:
Thomas Sailer
Created:
2014-07-01 15:25:06 UTC
Size:
12.96 KB
patch
obsolete
>--- boost_1_54_0/boost/graph/dijkstra_shortest_paths.hpp 2013-05-16 17:38:05.000000000 +0200 >+++ boost_1_55_0/boost/graph/dijkstra_shortest_paths.hpp 2013-09-21 22:17:00.000000000 +0200 >@@ -118,6 +118,7 @@ > struct dijkstra_bfs_visitor > { > typedef typename property_traits<DistanceMap>::value_type D; >+ typedef typename property_traits<WeightMap>::value_type W; > > dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q, > WeightMap w, PredecessorMap p, DistanceMap d, >@@ -159,13 +160,39 @@ > void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); } > template <class Edge, class Graph> > void examine_edge(Edge e, Graph& g) { >- // Comparison needs to be more complicated because distance and weight >- // types may not be the same; see bug 8398 >- // (https://svn.boost.org/trac/boost/ticket/8398) >- D source_dist = get(m_distance, source(e, g)); >- if (m_compare(m_combine(source_dist, get(m_weight, e)), source_dist)) >+ // Test for negative-weight edges: >+ // >+ // 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 >+ // types do not need to be the same (bug 8398, >+ // https://svn.boost.org/trac/boost/ticket/8398). >+ // m_compare(m_combine(source_dist, e_weight), source_dist): >+ // if m_combine is project2nd (as in prim_minimum_spanning_tree), >+ // this test will claim that the edge weight is negative whenever >+ // the edge weight is less than source_dist, even if both of those >+ // are positive (bug 9012, >+ // https://svn.boost.org/trac/boost/ticket/9012). >+ // m_compare(m_combine(e_weight, source_dist), source_dist): >+ // would fix project2nd issue, but documentation only requires that >+ // m_combine be able to take a distance and a weight (in that order) >+ // and return a distance. >+ >+ // W e_weight = get(m_weight, e); >+ // sd_plus_ew = 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); >+ // 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. >+ 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. >+ > m_vis.examine_edge(e, g); >+ > } > template <class Edge, class Graph> > void black_target(Edge, Graph&) { } >@@ -256,14 +283,14 @@ > } > > // Call breadth first search with default color map. >- template <class Graph, class DijkstraVisitor, >+ template <class Graph, class SourceInputIter, class DijkstraVisitor, > class PredecessorMap, class DistanceMap, > class WeightMap, class IndexMap, class Compare, class Combine, > class DistZero> > inline void > dijkstra_shortest_paths_no_init > (const Graph& g, >- typename graph_traits<Graph>::vertex_descriptor s, >+ SourceInputIter s_begin, SourceInputIter s_end, > PredecessorMap predecessor, DistanceMap distance, WeightMap weight, > IndexMap index_map, > Compare compare, Combine combine, DistZero zero, >@@ -275,16 +302,16 @@ > typedef typename ColorMapHelper::type ColorMap; > ColorMap color = > ColorMapHelper::build(g, index_map); >- dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight, >+ dijkstra_shortest_paths_no_init( g, s_begin, s_end, predecessor, distance, weight, > index_map, compare, combine, zero, vis, > color); > } > >- // Call breadth first search >+ // Call breadth first search with default color map. > template <class Graph, class DijkstraVisitor, > class PredecessorMap, class DistanceMap, > class WeightMap, class IndexMap, class Compare, class Combine, >- class DistZero, class ColorMap> >+ class DistZero> > inline void > dijkstra_shortest_paths_no_init > (const Graph& g, >@@ -292,6 +319,25 @@ > PredecessorMap predecessor, DistanceMap distance, WeightMap weight, > IndexMap index_map, > Compare compare, Combine combine, DistZero zero, >+ DijkstraVisitor vis) >+ { >+ dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance, >+ weight, index_map, compare, combine, zero, >+ vis); >+ } >+ >+ // Call breadth first search >+ template <class Graph, class SourceInputIter, class DijkstraVisitor, >+ class PredecessorMap, class DistanceMap, >+ class WeightMap, class IndexMap, class Compare, class Combine, >+ class DistZero, class ColorMap> >+ inline void >+ dijkstra_shortest_paths_no_init >+ (const Graph& g, >+ SourceInputIter s_begin, SourceInputIter s_end, >+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight, >+ IndexMap index_map, >+ Compare compare, Combine combine, DistZero zero, > DijkstraVisitor vis, ColorMap color) > { > typedef indirect_cmp<DistanceMap, Compare> IndirectCmp; >@@ -309,7 +355,7 @@ > PredecessorMap, DistanceMap, Combine, Compare> > bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); > >- breadth_first_visit(g, s, Q, bfs_vis, color); >+ breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); > return; > } > #endif // BOOST_GRAPH_DIJKSTRA_TESTING >@@ -334,11 +380,30 @@ > PredecessorMap, DistanceMap, Combine, Compare> > bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); > >- breadth_first_visit(g, s, Q, bfs_vis, color); >+ breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); >+ } >+ >+ // Call breadth first search >+ template <class Graph, class DijkstraVisitor, >+ class PredecessorMap, class DistanceMap, >+ class WeightMap, class IndexMap, class Compare, class Combine, >+ class DistZero, class ColorMap> >+ inline void >+ dijkstra_shortest_paths_no_init >+ (const Graph& g, >+ typename graph_traits<Graph>::vertex_descriptor s, >+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight, >+ IndexMap index_map, >+ Compare compare, Combine combine, DistZero zero, >+ DijkstraVisitor vis, ColorMap color) >+ { >+ dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance, >+ weight, index_map, compare, combine, >+ zero, vis, color); > } > > // Initialize distances and call breadth first search with default color map >- template <class VertexListGraph, class DijkstraVisitor, >+ template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor, > class PredecessorMap, class DistanceMap, > class WeightMap, class IndexMap, class Compare, class Combine, > class DistInf, class DistZero, typename T, typename Tag, >@@ -346,7 +411,7 @@ > inline void > dijkstra_shortest_paths > (const VertexListGraph& g, >- typename graph_traits<VertexListGraph>::vertex_descriptor s, >+ SourceInputIter s_begin, SourceInputIter s_end, > PredecessorMap predecessor, DistanceMap distance, WeightMap weight, > IndexMap index_map, > Compare compare, Combine combine, DistInf inf, DistZero zero, >@@ -355,16 +420,17 @@ > BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) > { > boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map); >- dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, >- compare, combine, inf, zero, vis, >+ dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight, >+ index_map, compare, combine, inf, zero, vis, > color); > } > >- // Initialize distances and call breadth first search >+ // Initialize distances and call breadth first search with default color map > template <class VertexListGraph, class DijkstraVisitor, > class PredecessorMap, class DistanceMap, > class WeightMap, class IndexMap, class Compare, class Combine, >- class DistInf, class DistZero, class ColorMap> >+ class DistInf, class DistZero, typename T, typename Tag, >+ typename Base> > inline void > dijkstra_shortest_paths > (const VertexListGraph& g, >@@ -372,6 +438,26 @@ > PredecessorMap predecessor, DistanceMap distance, WeightMap weight, > IndexMap index_map, > Compare compare, Combine combine, DistInf inf, DistZero zero, >+ DijkstraVisitor vis, >+ const bgl_named_params<T, Tag, Base>& >+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) >+ { >+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, >+ index_map, compare, combine, inf, zero, vis); >+ } >+ >+ // Initialize distances and call breadth first search >+ template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor, >+ class PredecessorMap, class DistanceMap, >+ class WeightMap, class IndexMap, class Compare, class Combine, >+ class DistInf, class DistZero, class ColorMap> >+ inline void >+ dijkstra_shortest_paths >+ (const VertexListGraph& g, >+ SourceInputIter s_begin, SourceInputIter s_end, >+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight, >+ IndexMap index_map, >+ Compare compare, Combine combine, DistInf inf, DistZero zero, > DijkstraVisitor vis, ColorMap color) > { > typedef typename property_traits<ColorMap>::value_type ColorValue; >@@ -383,17 +469,20 @@ > put(predecessor, *ui, *ui); > put(color, *ui, Color::white()); > } >- put(distance, s, zero); >+ for (SourceInputIter it = s_begin; it != s_end; ++it) { >+ put(distance, *it, zero); >+ } > >- dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight, >- index_map, compare, combine, zero, vis, color); >+ dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance, >+ weight, index_map, compare, combine, zero, vis, >+ color); > } > > // Initialize distances and call breadth first search > template <class VertexListGraph, class DijkstraVisitor, > class PredecessorMap, class DistanceMap, > class WeightMap, class IndexMap, class Compare, class Combine, >- class DistInf, class DistZero> >+ class DistInf, class DistZero, class ColorMap> > inline void > dijkstra_shortest_paths > (const VertexListGraph& g, >@@ -401,13 +490,53 @@ > PredecessorMap predecessor, DistanceMap distance, WeightMap weight, > IndexMap index_map, > Compare compare, Combine combine, DistInf inf, DistZero zero, >+ DijkstraVisitor vis, ColorMap color) >+ { >+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, >+ index_map, compare, combine, inf, zero, >+ vis, color); >+ } >+ >+ // Initialize distances and call breadth first search >+ template <class VertexListGraph, class SourceInputIter, >+ class DijkstraVisitor, >+ class PredecessorMap, class DistanceMap, >+ class WeightMap, class IndexMap, class Compare, class Combine, >+ class DistInf, class DistZero> >+ inline void >+ dijkstra_shortest_paths >+ (const VertexListGraph& g, >+ SourceInputIter s_begin, SourceInputIter s_end, >+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight, >+ IndexMap index_map, >+ Compare compare, Combine combine, DistInf inf, DistZero zero, > DijkstraVisitor vis) > { >- dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, >+ dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, >+ weight, index_map, > compare, combine, inf, zero, vis, > no_named_parameters()); > } > >+ // Initialize distances and call breadth first search >+ template <class VertexListGraph, class DijkstraVisitor, >+ class PredecessorMap, class DistanceMap, >+ class WeightMap, class IndexMap, class Compare, class Combine, >+ class DistInf, class DistZero> >+ inline void >+ dijkstra_shortest_paths >+ (const VertexListGraph& g, >+ typename graph_traits<VertexListGraph>::vertex_descriptor s, >+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight, >+ IndexMap index_map, >+ Compare compare, Combine combine, DistInf inf, DistZero zero, >+ DijkstraVisitor vis) >+ { >+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, >+ weight, index_map, >+ compare, combine, inf, zero, vis); >+ } >+ > namespace detail { > > // Handle defaults for PredecessorMap and
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Diff
View Attachment As Raw
Actions:
View
|
Diff
Attachments on
bug 1115124
: 913792