[boost] boost::graph - incorrect answers with dikjstra_shorts_paths

From: Marc Jacobs (marcja_at_[hidden])
Date: 2002-11-14 14:48:52

I'm using boost::graph to model dependencies between files (much like the
File Dependency example in the documentation.) I've been successfully able
to do topological sorts, traversals with visitors, etc., but I am unable to
get the parallel example to work correctly (that is, assigning time slots to
files that signify the earliest time slot in which they can be executed.)
The code I'm using to calculate parallel tasks looks like:

    /**
     * Outputs all the tasks as a pair that contains both the task name and
an integer that
     * represents the earliest timeslice at which a task can be executed
given its dependency
     * constraints. Effectively, all tasks with the same timeslice can be
executed in paralell.
     *
     * @param iter              an output iterator
     */
    template< class OutputIterator >
    void parallel_tasks( OutputIterator iter )
    {
        using boost::dijkstra_shortest_paths;
        using boost::property_map;
        using boost::vertex_distance;
        using boost::vertex_distance_t;
        using boost::vertices;
        using std::greater;

        // marcja(all): in_degree is a measure of how many edges point into
a particular vertex. If
        // a vertex has in_degree 0, it is a root vertex. We use this
information below when
        // calculating the Dijkstra shortest paths. The following loop
cycles through each vertex
        // and increments the in_degree of any other vertices it points to.

        std::vector< int >              in_degree( num_vertices( graph_ ),
0 );
        Graph::vertex_iterator          i, iend;
        Graph::out_edge_iterator        j, jend;

        for( tie( i, iend ) = boost::vertices( graph_ ); i != iend; ++i )
        {
            for( boost::tie( j, jend ) = out_edges( *i, graph_ ); j != jend;
++j )
            {
                in_degree[ boost::target( *j, graph_ ) ] += 1;
            }
        }

        property_map< Graph, vertex_distance_t >::type  times   = get(
vertex_distance, graph_ );

        for( tie( i, iend ) = vertices( graph_ ); i != iend; ++i )
        {
            if( in_degree[ *i ] == 0 )
            {
                  boost::dijkstra_shortest_paths(
                      graph_,
                      *i,
                      distance_map( times )                     .
                      distance_compare( greater< int >() )      .
                      distance_inf( 0 )                         .
// values other than zero, particularly the default

// of numeric_limits< D >::max(), only seem to change

// the initial value of D for each vertex
                      distance_zero( 0 )
                  );
            }
        }

        using boost::vertex_name;
        using boost::vertex_name_t;

        property_map< Graph, vertex_name_t >::type names = get( vertex_name,
graph_ );

        for( tie( i, iend ) = vertices( graph_ ); i != iend; ++i )
        {
            iter++ = make_pair( names[ *i ], times[ *i ] );
        }
    }

My program outputs, for example:

talisker> load taskfile
Thu Nov 14 14:42:26 2002 info: loading taskfile

tasks (count: 9)
--------------------------------
calibrate_shiftedvol_mtgerate
create_directories
generate_base_and_YCshifted_grids
generate_shiftedvol_grids
get_data_from_crunch
import_yield_curves
run_base_calibration
run_shiftedvol_calibration
set_variables

dependencies (count: 13)
--------------------------------
get_data_from_crunch              depends on create_directories
import_yield_curves               depends on create_directories
calibrate_shiftedvol_mtgerate     depends on generate_shiftedvol_grids
import_yield_curves               depends on get_data_from_crunch
run_base_calibration              depends on get_data_from_crunch
run_shiftedvol_calibration        depends on get_data_from_crunch
generate_base_and_YCshifted_grids depends on import_yield_curves
generate_shiftedvol_grids         depends on import_yield_curves
run_base_calibration              depends on import_yield_curves
run_shiftedvol_calibration        depends on import_yield_curves
generate_base_and_YCshifted_grids depends on run_base_calibration
generate_shiftedvol_grids         depends on run_shiftedvol_calibration
create_directories                depends on set_variables

talisker> show execution plan

sorted tasks
--------------------------------
set_variables
create_directories
get_data_from_crunch
import_yield_curves
run_shiftedvol_calibration
run_base_calibration
generate_shiftedvol_grids
generate_base_and_YCshifted_grids
calibrate_shiftedvol_mtgerate

parallel groups (count: 9)
--------------------------------
set_variables                               0
create_directories                          1
get_data_from_crunch                        2
import_yield_curves                         3
generate_base_and_YCshifted_grids           4
run_base_calibration                        4
run_shiftedvol_calibration                  4
generate_shiftedvol_grids                   5
calibrate_shiftedvol_mtgerate               6

talisker>

However, the task "generate_base_and_YCshifted_grids" depends on
"run_base_calibration", so they can't be in the same timeslot. What's going
on? Everything else seems in the right spot... BTW, if I change the value of
distance_inf to the default of numeric_limits< D >::max(), all tasks except
the root task have a time value equal to numeric_limits< D >::max(), aka
2147483647.
Marc