Program Listing for File ShortestPaths.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File ShortestPaths.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/graph/Graph.h"
#include "ADS/graph/Visit.h"
#include "ADS/priority/FibonacciHeapPriorityQueue.h"
#include "ADS/priority/HeapPriorityQueue.h"
#include "ADS/priority/ListPriorityQueue.h"
#include "ADS/priority/PriorityQueue.h"
#include "ADS/queue/ArrayQueue.h"
#include "ADS/queue/Dequeue.h"
#include "ADS/stack/ArrayStack.h"

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <limits>
#include <memory>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------------- TYPES -----------------------------------*/
/*--------------------------------------------------------------------------*/

enum class Frontier { LIST , HEAP , FIBONACCI , QUEUE , STACK , DEQUE };

template< class D >
constexpr D infinity( void )
{
 if constexpr( std::numeric_limits< D >::has_infinity )
  return( std::numeric_limits< D >::infinity() );
 else
  return( std::numeric_limits< D >::max() );
 }

template< class D >
struct ShortestPathTree {
 std::vector< D > d;
 std::vector< int > T;
 std::vector< int > order;
 bool negativeCycle = false;
 };

struct FrontierCounts {
 long long adds = 0 , extracts = 0 , decreases = 0 , edges = 0;
 };

template< class S , class D >
concept PrototypeFrontier = requires( S s , int v , const D & d , bool b ) {
 s.add( v , d , b );
 { s.extract() } -> std::convertible_to< int >;
 s.update( v , d );
 { s.empty() } -> std::same_as< bool >;
 };

template< PriorityQueue Q >
class PriorityFrontier {

 public:

 PriorityFrontier( Q & q , int n ) : f_q( q ) ,
                                     f_h( std::size_t( n < 0 ? 0 : n ) ) {}

 template< class D >
 void add( int v , const D & d , bool ) {
  f_h[ v ] = f_q.insert( v , key( v , d ) );
  }

 int extract( void ) { return( f_q.deleteMin() ); }

 template< class D >
 void update( int v , const D & d ) {
  f_q.decrease( f_h[ v ] , key( v , d ) );
  }

 [[nodiscard]] bool empty( void ) const { return( f_q.empty() ); }

 template< class D >
 static typename Q::Priority key( int v , const D & d ) {
  using P = typename Q::Priority;
  if constexpr( requires { typename P::first_type; } )
   return( P( d , v ) );
  else
   return( P( d ) );
  }

 private:

 Q & f_q;
 std::vector< typename Q::Handle > f_h;

 };  // end( class PriorityFrontier )

template< class Q >
class QueueFrontier {

 public:

 static constexpr bool fifo = true;

 explicit QueueFrontier( Q & q ) : f_q( q ) {}

 template< class D >
 void add( int v , const D & , bool ) { f_q.enqueue( v ); }

 int extract( void ) { return( f_q.dequeue() ); }

 template< class D >
 void update( int , const D & ) {}

 [[nodiscard]] bool empty( void ) const { return( f_q.empty() ); }

 private:

 Q & f_q;

 };  // end( class QueueFrontier )

template< class Q >
class StackFrontier {

 public:

 explicit StackFrontier( Q & q ) : f_q( q ) {}

 template< class D >
 void add( int v , const D & , bool ) { f_q.push( v ); }

 int extract( void ) { return( f_q.pop() ); }

 template< class D >
 void update( int , const D & ) {}

 [[nodiscard]] bool empty( void ) const { return( f_q.empty() ); }

 private:

 Q & f_q;

 };  // end( class StackFrontier )

template< class Q >
class DequeFrontier {

 public:

 explicit DequeFrontier( Q & q ) : f_q( q ) {}

 template< class D >
 void add( int v , const D & , bool first ) {
  if( first ) f_q.insertTail( v ); else f_q.insertHead( v );
  }

 int extract( void ) { return( f_q.removeHead() ); }

 template< class D >
 void update( int , const D & ) {}

 [[nodiscard]] bool empty( void ) const { return( f_q.empty() ); }

 private:

 Q & f_q;

 };  // end( class DequeFrontier )

/*--------------------------------------------------------------------------*/
/*------------------------------ PROTOTYPE ---------------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G >
ShortestPathTree< typename G::Weight > shortestPaths( const G & g , int r ,
                                                      Frontier how );

template< Graph G , class S >
requires PrototypeFrontier< S , typename G::Weight >
ShortestPathTree< typename G::Weight > shortestPaths( const G & g , int r ,
                                     S & frontier ,
                                     FrontierCounts * c = nullptr );

template< Graph G >
auto dijkstra( const G & g , int r );

template< Graph G >
auto johnson( const G & g , int r );

template< Graph G >
auto fredmanTarjan( const G & g , int r );

template< Graph G >
auto bellmanFordMoore( const G & g , int r );

template< Graph G >
auto papeDEsopo( const G & g , int r );

template< Graph G >
ShortestPathTree< typename G::Weight > dagShortestPaths( const G & g ,
                                                         int r );

template< Graph G >
bool isShortestPathTree( const G & g , int r ,
                         const ShortestPathTree< typename G::Weight > & R );

template< Graph G >
bool reachesNegativeCycle( const G & g , int r );

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

}  // end( namespace ADS )

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

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

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

#endif  /* ShortestPaths.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File ShortestPaths.h ------------------------*/
/*--------------------------------------------------------------------------*/