Signed integer overflow in successive_shortest_path_nonnegative_weights()

[grievejia@…]

Buiding and running the following program with UndefinedBehaviorSanitizer will generate a report on signed integer overflow error:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/successive_shortest_path_nonnegative_weights.hpp>
#include <iostream>

using namespace boost;

using Traits = adjacency_list_traits<vecS, vecS, directedS>;
using Graph = adjacency_list<
    vecS, vecS, directedS, no_property,
    property<edge_capacity_t, int,
             property<edge_residual_capacity_t, int,
                      property<edge_reverse_t, Traits::edge_descriptor,
                               property<edge_weight_t, int>>>>>;

template <typename Map, typename Edge>
void fill_capacity(Map &m, Edge e, Edge er, int c) {
  put(m, e, c);
  put(m, er, 0);
}

template <typename Map, typename Edge> void fill_rev(Map &m, Edge e, Edge er) {
  put(m, e, er);
  put(m, er, e);
}

template <typename Map, typename Edge>
void fill_weight(Map &m, Edge e, Edge er, int w) {
  put(m, e, w);
  put(m, er, -w);
}

int main() {
  Graph g(4);
  auto capacity = get(edge_capacity, g);
  auto rev = get(edge_reverse, g);
  auto weight = get(edge_weight, g);

  auto e0 = add_edge(0, 1, g).first;
  auto e0r = add_edge(1, 0, g).first;
  auto e1 = add_edge(0, 2, g).first;
  auto e1r = add_edge(2, 0, g).first;
  auto e2 = add_edge(1, 2, g).first;
  auto e2r = add_edge(2, 1, g).first;

  // What the weights and capacities are don't really matter as long as they are all positive
  fill_capacity(capacity, e0, e0r, 1);
  fill_capacity(capacity, e1, e1r, 1);
  fill_capacity(capacity, e2, e2r, 1);
  fill_rev(rev, e0, e0r);
  fill_rev(rev, e1, e1r);
  fill_rev(rev, e2, e2r);
  fill_weight(weight, e0, e0r, 1);
  fill_weight(weight, e1, e1r, 1);
  fill_weight(weight, e2, e2r, 1);

  successive_shortest_path_nonnegative_weights(g, 0, 2);
}

Here's the stacktrace collected by UBSan (simplified for readability):

/usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57: runtime error: signed integer overflow: 2147483647 + 2147483647 cannot be represented in type 'int'
    #0 0x43fccd in void boost::successive_shortest_path_nonnegative_weights<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57
    #1 0x43d7dc in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch3<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:148:5
    #2 0x43bf40 in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch2<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:186:5
    #3 0x43b2ba in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch1<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:223:5
    #4 0x43b018 in void boost::successive_shortest_path_nonnegative_weights<boost::adjacency_list<...>, int, boost::buffer_param_t, boost::no_property>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:238:12
    #5 0x42b046 in void boost::successive_shortest_path_nonnegative_weights<...>(boost::adjacency_list<...>&, boost::graph_traits<...>::vertex_descriptor, boost::graph_traits<...>::vertex_descriptor) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:255:5
    #6 0x42a520 in main /home/grieve/Research/Testing/boost/reduced.cpp:56:3
    #7 0x7f7cb22e3f69 in __libc_start_main (/usr/lib/libc.so.6+0x20f69)
    #8 0x4039b9 in _start (/home/grieve/Research/Testing/boost/reduced+0x4039b9)

The problem here is that function successive_shortest_path_nonnegative_weights() does not take into account the fact that its input graph might be disconnected and therefore it is possible for some shortest path distances to be infinity.