[boost] Boost Graph Library bug report

From: Nepomnyachiy Pavel (npv_at_[hidden])
Date: 2002-11-05 06:04:06

Greetings!

While using Boost Graph Library's push_relabel_max_flow() algorithm, I've
found the following bugs:

1. In case when source and sink are adjacent vertices the algorithm crashes.

In file boost/graph/push_relabel_max_flow.hpp, lines 197-210
(initialization: push_relabel constructor)

197:    for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          vertex_descriptor u = *u_iter;
          if (u == sink)
            distance[u] = 0;
          else if (u == src && !overflow_detected)
            distance[u] = n;
          else
            distance[u] = 1;

          if (excess_flow[u] > 0)
            add_to_active_list(u, layers[1]);
          else if (distance[u] < n)
            add_to_inactive_list(u, layers[1]);
        }

If sink is adjacent to source then it is added to the list of active nodes, 
because
there is positive excess flow. By definition of the algorithm sink can't be 
active,
so it leads to a crash.

2. Mistype in global_distance_update() function:

In file boost/graph/push_relabel_max_flow.hpp, lines 231-234
global_distance_update()

231:    for (distance_size_type l = 0; l != max_distance; ++l) {
          layers[l].active_vertices.clear();
          layers[l].inactive_vertices.clear();
        }

In this cycle layers[max_distance].active_vertices is never cleared, so it 
leads to a
possibility that two identical vertices will be stored in the same list.

Patch proposed:

*** push_relabel_max_flow_.hpp	Tue Jan 15 01:33:26 2002
--- push_relabel_max_flow.hpp	Tue Nov  5 13:46:44 2002
***************
*** 197,203 ****
--- 197,206 ----
          for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
            vertex_descriptor u = *u_iter;
            if (u == sink)
+           {
              distance[u] = 0;
+             continue;
+           }
            else if (u == src && !overflow_detected)
              distance[u] = n;
            else
***************
*** 228,234 ****
          c
nk] = 0;
          
!         for (distance_size_type l = 0; l != max_distance; ++l) {
            layers[l].active_vertices.clear();
            layers[l].inactive_vertices.clear();
          }
--- 231,237 ----
          color[sink] = ColorTraits::gray();
          distance[sink] = 0;
          
!         for (distance_size_type l = 0; l <= max_distance; ++l) {
            layers[l].active_vertices.clear();
            layers[l].inactive_vertices.clear();
          }

The following examples in DIMACS format, processes by max_flow.cpp example 
provided
in Boost Graph Library are solved correctly by patched version and crash 
unpatched
version.

1. Adjacent source and sink.

p max 2 1
n 1 s
n 2 t
a 1 2 5

2. global_distance_update()

p max	12	43
n	10 s
n	11 t
a	1	6	43
a	1	3	18
a	1	2	66
a	1	8	115
a	2	6	22
a	2	5	41
a	2	4	42
a	2	3	84
a	2	1	66
a	2	9	163
a	3	4	41
a	3	7	60
a	3	9	79
a	3	2	84
a	3	1	18
a	4	5	84
a	4	2	42
a	4	9	121
a	4	3	41
a	4	7	102
a	5	6	64
a	5	2	41
a	5	4	84
a	6	8	158
a	6	1	43
a	6	2	22
a	6	5	64
a	6	11	701
a	7	4	102
a	7	3	60
a	8	6	158
a	8	1	115
a	9	4	121
a	9	3	79
a	9	2	163
a	10	12	701
a	12	1	100
a	12	3	100
a	12	4	100
a	12	5	100
a	12	6	100
a	12	7	100
a	12	8	100



Best regards,
    Pavel V. Nepomnyaschy
    npv_at_[hidden]