Boost C++ Libraries

libs/graph/example/r_c_shortest_paths_example.cpp

// Copyright Michael Drexl 2005, 2006.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at 
// http://boost.org/LICENSE_1_0.txt)

// Example use of the resource-constrained shortest paths algorithm.
#include <boost/config.hpp>

#ifdef BOOST_MSVC
#  pragma warning(disable: 4267)
#endif

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/r_c_shortest_paths.hpp>
#include <iostream>

using namespace boost;

struct SPPRC_Example_Graph_Vert_Prop
{
  SPPRC_Example_Graph_Vert_Prop( int n = 0, int e = 0, int l = 0 ) 
  : num( n ), eat( e ), lat( l ) {}
  int num;
  // earliest arrival time
  int eat;
  // latest arrival time
  int lat;
};

struct SPPRC_Example_Graph_Arc_Prop
{
  SPPRC_Example_Graph_Arc_Prop( int n = 0, int c = 0, int t = 0 ) 
  : num( n ), cost( c ), time( t ) {}
  int num;
  // traversal cost
  int cost;
  // traversal time
  int time;
};

typedef adjacency_list<vecS, 
                       vecS, 
                       directedS, 
                       SPPRC_Example_Graph_Vert_Prop, 
                       SPPRC_Example_Graph_Arc_Prop> 
  SPPRC_Example_Graph;

// data structures for spp without resource constraints:
// ResourceContainer model
struct spp_no_rc_res_cont
{
  spp_no_rc_res_cont( int c = 0 ) : cost( c ) {};
  spp_no_rc_res_cont& operator=( const spp_no_rc_res_cont& other )
  {
    if( this == &other )
      return *this;
    this->~spp_no_rc_res_cont();
    new( this ) spp_no_rc_res_cont( other );
    return *this;
  }
  int cost;
};

bool operator==( const spp_no_rc_res_cont& res_cont_1, 
                 const spp_no_rc_res_cont& res_cont_2 )
{
  return ( res_cont_1.cost == res_cont_2.cost );
}

bool operator<( const spp_no_rc_res_cont& res_cont_1, 
                const spp_no_rc_res_cont& res_cont_2 )
{
  return ( res_cont_1.cost < res_cont_2.cost );
}

// ResourceExtensionFunction model
class ref_no_res_cont
{
public:
  inline bool operator()( const SPPRC_Example_Graph& g, 
                          spp_no_rc_res_cont& new_cont, 
                          const spp_no_rc_res_cont& old_cont, 
                          graph_traits
                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
  {
    new_cont.cost = old_cont.cost + g[ed].cost;
    return true;
  }
};

// DominanceFunction model
class dominance_no_res_cont
{
public:
  inline bool operator()( const spp_no_rc_res_cont& res_cont_1, 
                          const spp_no_rc_res_cont& res_cont_2 ) const
  {
    // must be "<=" here!!!
    // must NOT be "<"!!!
    return res_cont_1.cost <= res_cont_2.cost;
    // this is not a contradiction to the documentation
    // the documentation says:
    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
    // at the same vertex, and if, for each resource, the resource consumption 
    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
    // and if there is at least one resource where $l_1$ has a lower resource 
    // consumption than $l_2$."
    // one can think of a new label with a resource consumption equal to that 
    // of an old label as being dominated by that old label, because the new 
    // one will have a higher number and is created at a later point in time, 
    // so one can implicitly use the number or the creation time as a resource 
    // for tie-breaking
  }
};
// end data structures for spp without resource constraints:

// data structures for shortest path problem with time windows (spptw)
// ResourceContainer model
struct spp_spptw_res_cont
{
  spp_spptw_res_cont( int c = 0, int t = 0 ) : cost( c ), time( t ) {}
  spp_spptw_res_cont& operator=( const spp_spptw_res_cont& other )
  {
    if( this == &other )
      return *this;
    this->~spp_spptw_res_cont();
    new( this ) spp_spptw_res_cont( other );
    return *this;
  }
  int cost;
  int time;
};

bool operator==( const spp_spptw_res_cont& res_cont_1, 
                 const spp_spptw_res_cont& res_cont_2 )
{
  return ( res_cont_1.cost == res_cont_2.cost 
           && res_cont_1.time == res_cont_2.time );
}

bool operator<( const spp_spptw_res_cont& res_cont_1, 
                const spp_spptw_res_cont& res_cont_2 )
{
  if( res_cont_1.cost > res_cont_2.cost )
    return false;
  if( res_cont_1.cost == res_cont_2.cost )
    return res_cont_1.time < res_cont_2.time;
  return true;
}

// ResourceExtensionFunction model
class ref_spptw
{
public:
  inline bool operator()( const SPPRC_Example_Graph& g, 
                          spp_spptw_res_cont& new_cont, 
                          const spp_spptw_res_cont& old_cont, 
                          graph_traits
                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
  {
    const SPPRC_Example_Graph_Arc_Prop& arc_prop = 
      get( edge_bundle, g )[ed];
    const SPPRC_Example_Graph_Vert_Prop& vert_prop = 
      get( vertex_bundle, g )[target( ed, g )];
    new_cont.cost = old_cont.cost + arc_prop.cost;
    int& i_time = new_cont.time;
    i_time = old_cont.time + arc_prop.time;
    i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
    return i_time <= vert_prop.lat ? true : false;
  }
};

// DominanceFunction model
class dominance_spptw
{
public:
  inline bool operator()( const spp_spptw_res_cont& res_cont_1, 
                          const spp_spptw_res_cont& res_cont_2 ) const
  {
    // must be "<=" here!!!
    // must NOT be "<"!!!
    return res_cont_1.cost <= res_cont_2.cost 
           && res_cont_1.time <= res_cont_2.time;
    // this is not a contradiction to the documentation
    // the documentation says:
    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
    // at the same vertex, and if, for each resource, the resource consumption 
    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
    // and if there is at least one resource where $l_1$ has a lower resource 
    // consumption than $l_2$."
    // one can think of a new label with a resource consumption equal to that 
    // of an old label as being dominated by that old label, because the new 
    // one will have a higher number and is created at a later point in time, 
    // so one can implicitly use the number or the creation time as a resource 
    // for tie-breaking
  }
};
// end data structures for shortest path problem with time windows (spptw)

// example graph structure and cost from 
// http://www.boost.org/libs/graph/example/dijkstra-example.cpp
const int num_nodes = 5;
enum nodes { A, B, C, D, E };
char name[] = "ABCDE";

int main()
{
  SPPRC_Example_Graph g;

  add_vertex( SPPRC_Example_Graph_Vert_Prop( A, 0, 0 ), g );
  add_vertex( SPPRC_Example_Graph_Vert_Prop( B, 5, 20 ), g );
  add_vertex( SPPRC_Example_Graph_Vert_Prop( C, 6, 10 ), g );
  add_vertex( SPPRC_Example_Graph_Vert_Prop( D, 3, 12 ), g );
  add_vertex( SPPRC_Example_Graph_Vert_Prop( E, 0, 100 ), g );

  add_edge( A, C, SPPRC_Example_Graph_Arc_Prop( 0, 1, 5 ), g );
  add_edge( B, B, SPPRC_Example_Graph_Arc_Prop( 1, 2, 5 ), g );
  add_edge( B, D, SPPRC_Example_Graph_Arc_Prop( 2, 1, 2 ), g );
  add_edge( B, E, SPPRC_Example_Graph_Arc_Prop( 3, 2, 7 ), g );
  add_edge( C, B, SPPRC_Example_Graph_Arc_Prop( 4, 7, 3 ), g );
  add_edge( C, D, SPPRC_Example_Graph_Arc_Prop( 5, 3, 8 ), g );
  add_edge( D, E, SPPRC_Example_Graph_Arc_Prop( 6, 1, 3 ), g );
  add_edge( E, A, SPPRC_Example_Graph_Arc_Prop( 7, 1, 5 ), g );
  add_edge( E, B, SPPRC_Example_Graph_Arc_Prop( 8, 1, 4 ), g );


  // the unique shortest path from A to E in the dijkstra-example.cpp is 
  // A -> C -> D -> E
  // its length is 5
  // the following code also yields this result

  // with the above time windows, this path is infeasible
  // now, there are two shortest paths that are also feasible with respect to 
  // the vertex time windows:
  // A -> C -> B -> D -> E and 
  // A -> C -> B -> E
  // however, the latter has a longer total travel time and is therefore not 
  // pareto-optimal, i.e., it is dominated by the former path
  // therefore, the code below returns only the former path

  // spp without resource constraints
  graph_traits<SPPRC_Example_Graph>::vertex_descriptor s = A;
  graph_traits<SPPRC_Example_Graph>::vertex_descriptor t = E;

  std::vector
    <std::vector
      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
        opt_solutions;
  std::vector<spp_no_rc_res_cont> pareto_opt_rcs_no_rc;

  r_c_shortest_paths
  ( g, 
    get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
    get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
    s, 
    t, 
    opt_solutions, 
    pareto_opt_rcs_no_rc, 
    spp_no_rc_res_cont( 0 ), 
    ref_no_res_cont(), 
    dominance_no_res_cont(), 
    std::allocator
      <r_c_shortest_paths_label
        <SPPRC_Example_Graph, spp_no_rc_res_cont> >(), 
    default_r_c_shortest_paths_visitor() );

  std::cout << "SPP without resource constraints:" << std::endl;
  std::cout << "Number of optimal solutions: ";
  std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
  for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
  {
    std::cout << "The " << i << "th shortest path from A to E is: ";
    std::cout << std::endl;
    for( int j = static_cast<int>( opt_solutions[i].size() ) - 1; j >= 0; --j )
      std::cout << name[source( opt_solutions[i][j], g )] << std::endl;
    std::cout << "E" << std::endl;
    std::cout << "Length: " << pareto_opt_rcs_no_rc[i].cost << std::endl;
  }
  std::cout << std::endl;

  // spptw
  std::vector
    <std::vector
      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
        opt_solutions_spptw;
  std::vector<spp_spptw_res_cont> pareto_opt_rcs_spptw;

  r_c_shortest_paths
  ( g, 
    get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
    get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
    s, 
    t, 
    opt_solutions_spptw, 
    pareto_opt_rcs_spptw, 
    spp_spptw_res_cont( 0, 0 ), 
    ref_spptw(), 
    dominance_spptw(), 
    std::allocator
      <r_c_shortest_paths_label
        <SPPRC_Example_Graph, spp_spptw_res_cont> >(), 
          default_r_c_shortest_paths_visitor() );

  std::cout << "SPP with time windows:" << std::endl;
  std::cout << "Number of optimal solutions: ";
  std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
  for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
  {
    std::cout << "The " << i << "th shortest path from A to E is: ";
    std::cout << std::endl;
    for( int j = static_cast<int>( opt_solutions_spptw[i].size() ) - 1; 
         j >= 0; 
         --j )
      std::cout << name[source( opt_solutions_spptw[i][j], g )] << std::endl;
    std::cout << "E" << std::endl;
    std::cout << "Length: " << pareto_opt_rcs_spptw[i].cost << std::endl;
    std::cout << "Time: " << pareto_opt_rcs_spptw[i].time << std::endl;
  }

  // utility function check_r_c_path example
  std::cout << std::endl;
  bool b_is_a_path_at_all = false;
  bool b_feasible = false; 
  bool b_correctly_extended = false;
  spp_spptw_res_cont actual_final_resource_levels( 0, 0 );
  graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc;
  check_r_c_path( g, 
                  opt_solutions_spptw[0], 
                  spp_spptw_res_cont( 0, 0 ), 
                  true, 
                  pareto_opt_rcs_spptw[0], 
                  actual_final_resource_levels, 
                  ref_spptw(), 
                  b_is_a_path_at_all, 
                  b_feasible, 
                  b_correctly_extended, 
                  ed_last_extended_arc );
  if( !b_is_a_path_at_all )
    std::cout << "Not a path." << std::endl;
  if( !b_feasible )
    std::cout << "Not a feasible path." << std::endl;
  if( !b_correctly_extended )
    std::cout << "Not correctly extended." << std::endl;
  if( b_is_a_path_at_all && b_feasible && b_correctly_extended )
  {
    std::cout << "Actual final resource levels:" << std::endl;
    std::cout << "Length: " << actual_final_resource_levels.cost << std::endl;
    std::cout << "Time: " << actual_final_resource_levels.time << std::endl;
    std::cout << "OK." << std::endl;
  }

  return 0;
}