Program Listing for File Paths.h

↰ Return to documentation for file (ADS/graph/Paths.h)

/*--------------------------------------------------------------------------*/
/*------------------------------ File Paths.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_Paths
 #define __ADS_Paths
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/graph/Graph.h"
#include "ADS/graph/Visit.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <set>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

namespace detail {

template< class G >
struct EdgeLength { using type = int; };

template< class G >
 requires requires { typename G::Weight; } &&
          ( ! std::is_same_v< typename G::Weight , std::monostate > )
struct EdgeLength< G > { using type = typename G::Weight; };

}  // end( namespace detail )

template< class G >
using PathLength = typename detail::EdgeLength< G >::type;

/*--------------------------------------------------------------------------*/
/*----------------------------- SHORTEST PATHS -----------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G >
std::vector< std::uint64_t > countShortestPaths( const G & g , int s );

template< Graph G >
std::pair< std::vector< int > , std::vector< int > >
multiSourceDistance( const G & g , const std::vector< int > & S );

template< Graph G >
int setDistance( const G & g , const std::vector< bool > & A ,
                 const std::vector< bool > & B );

/*--------------------------------------------------------------------------*/
/*----------------------------- LONGEST PATHS ------------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G >
std::vector< int > longestPathLayering( const G & g );

template< Graph G , class Keep >
std::vector< PathLength< G > > dagLongestPaths( const G & g , Keep && keep );

template< Graph G >
std::vector< PathLength< G > > dagLongestPaths( const G & g );

/*--------------------------------------------------------------------------*/
/*--------------------------------- CYCLES ---------------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G , class F >
void simpleCycles( const G & g , int s , F && f );

/*--------------------------------------------------------------------------*/
/*--------------------------------- A LINE ---------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
std::optional< std::vector< std::size_t > > refuelingStops(
                                      const std::vector< T > & D , T L , T R );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/graph/impl/Paths.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* Paths.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Paths.h ----------------------------*/
/*--------------------------------------------------------------------------*/