Boost C++ Libraries: Ticket #776: libs/graph/example/file_dependencies.cpp broken

holler — Wed, 15 Nov 2006 14:17:07 GMT

Logged In: YES
user_id=241424
Originator: YES
It seems I've found the reason. First the parameters for m_zero is sometimes wrong, second I had to disable the relaxed_heap, otherwise I've got wrong results.
After disabling relaxed_heap (is there a way to do this without modifying dijkstra_shortest_paths.hpp?) the following call to dijkstra_shortest_paths_no_init() in file_dependencies.cpp (from 1.29) works with boost 1.33.1 to compute which files can be build in parallel:
       dijkstra_shortest_paths_no_init
         (g, *i, &pred[0], &time[0], weight, indexmap,
           compare, combine,
           (std::numeric_limits<int>::max)(), // Since we are using > instead of <, we flip 0 and inf.
           default_dijkstra_visitor());
Because I've saw that dgregor has implemented relaxed_heap, I've changed assigned to.

holler — Wed, 15 Nov 2006 14:28:45 GMT

Logged In: YES
user_id=241424
Originator: YES
I've just seen, that relaxed_heap seems to work sometimes (at least for the test case). To get wrong results, I've used the following simple testcase:
enum files_e { autoconf_213, autoconf_wrapper, autoconf_259, N };
const char* name[] = { "autoconf 2.13", "autoconf-wrapper", "autoconf 2.59" };
  Edge used_by[] = {
      Edge(autoconf_259, autoconf_wrapper),
      Edge(autoconf_259, autoconf_213),
      Edge(autoconf_wrapper, autoconf_213)
    };
With relaxed_heap:
vertices with same group number can be made in parallel
time_slot[autoconf 2.13] = 1
time_slot[autoconf-wrapper] = 1
time_slot[autoconf 2.59] = 0
Without relaxed_heap:
vertices with same group number can be made in parallel
time_slot[autoconf 2.13] = 2
time_slot[autoconf-wrapper] = 1
time_slot[autoconf 2.59] = 0
Only the second case is correct. For visualizing the deps, I've put a small picture online: http://pleaseinstall.de/deptreeAutoconf.png

holler — Wed, 15 Nov 2006 20:03:43 GMT

Logged In: YES
user_id=241424
Originator: YES
Because I've found some other (closed) bugs against relaxed_heap, I've just tested the current HEAD. It is still defect. I'm attaching the test file (modified file_dependencies.cpp from 1.29) for easier debugging.
I've tested it now on three linux systems (gcc 4.03 x86, gcc 3.3.4 x86 and gcc 3.4.3 x86_64) and got always the same wrong result. So I don't think it is a rounding problem as suggested in another bug related to relaxed_heap.

Douglas Gregor — Mon, 20 Nov 2006 15:55:06 GMT

Logged In: YES
user_id=249098
Originator: NO
Looking into this further... it isn't a problem with the relaxed heap, but with the example itself. One cannot use Dijkstra's shortest paths algorithm for longest paths in this manner; we got (unlucky) with the original formulation, because with the binary heap we just happened to visit the vertices in the just the right order to make it work. With the submitter's small test case, for instance, permuting the order of the edge insertions can also make the example fail with the binary heap.
Interestingly, the BGL book's version of this example is correct. The BGL documentation and example should revert to what is in the book.

holler — Tue, 21 Nov 2006 03:34:23 GMT

Logged In: YES
user_id=241424
Originator: YES
I've just posted a working example to the boost-users mailing-list. It might not be as elegant as the original, but at least it works. I hope this was the right way to submit such but I though it might be better in the list where it could be easier found by others than than here.

status changed

Douglas Gregor — Fri, 15 Dec 2006 21:08:14 GMT

status assigned → closed

Logged In: YES
user_id=249098
Originator: NO
I have fixed this for Boost 1.34.0, with help from Alexander Holler. Thank you Alexander!