libs/graph/example/file_dependencies.cpp broken

[holler]

libs/graph/example/file_dependencies.cpp seems to be broken for some years. Additionally it is totally out of sync with the documentation.

I don't excactly since which version it is broken, but the example from 1.25 works (with 1.25) and 1.29 doesn't.

The actual (stable) version is still broken. I don't know exactly whats going on, but because I have some code which refused to work too (with newer versions of the bgl) I'm in the process of examine the changes done to the code of dijkstra_shortest_paths.

Either this example doesn't compile at all, or it will end with negative_edge exception.

What makes me wonder is that this was not found by some regression tests as many of the examples are having a .expected too. I thought that these are used to verify the examples.

[holler]

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]

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]

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]

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]

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.

[Douglas Gregor]

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!