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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
