Program Listing for File StaticGraph.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File StaticGraph.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <cstddef>
#include <ranges>
#include <span>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

#if defined( __GNUC__ ) || defined( __clang__ )
 #define ADS_GRAPH_PREFETCH( p ) __builtin_prefetch( ( const void * )( p ) )
#else
 #define ADS_GRAPH_PREFETCH( p ) ( ( void ) 0 )
#endif

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS StaticGraph ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class W >
struct WeightedArc {
 int to;
 W w;
 };

template< class W = std::monostate >
class StaticGraph {

/*--------------------------------------------------------------------------*/
 public:

 using Weight = W;

 static constexpr bool weighted = ! std::is_same_v< W , std::monostate >;

 using Arc = std::conditional_t< weighted , WeightedArc< W > , int >;

 StaticGraph( void ) : f_off( 1 , 0 ) {}

 StaticGraph( int n , const std::vector< std::tuple< int , int , W > > & E ,
              bool directed = true );

 StaticGraph( int n , const std::vector< std::pair< int , int > > & E ,
              bool directed = true ) requires( ! weighted );

 template< Graph G >
 explicit StaticGraph( const G & g );

 [[nodiscard]] bool directed( void ) const { return( f_directed ); }

 [[nodiscard]] int n( void ) const { return( int( f_off.size() ) - 1 ); }

 [[nodiscard]] int m( void ) const { return( f_m ); }

 [[nodiscard]] int arcs( void ) const { return( int( f_arc.size() ) ); }

 [[nodiscard]] int bound( void ) const { return( n() ); }

 [[nodiscard]] bool hasNode( int u ) const {
  return( ( u >= 0 ) && ( u < n() ) );
  }

 [[nodiscard]] int degree( int u ) const;

 [[nodiscard]] std::vector< int > V( void ) const;

 [[nodiscard]] std::vector< int > adj( int u ) const;

 template< class F >
 void forEachAdj( int u , F && f ) const;

 template< class F >
 void forEachEdge( int u , F && f ) const requires( weighted );

 [[nodiscard]] std::span< const Arc > out( int u ) const;

 [[nodiscard]] const int * offsets( void ) const { return( f_off.data() ); }

 [[nodiscard]] const Arc * arcData( void ) const { return( f_arc.data() ); }

 static int head( const Arc & a ) {
  if constexpr( weighted ) return( a.to ); else return( a );
  }

 [[nodiscard]] StaticGraph transpose( void ) const;

 [[nodiscard]] StaticGraph relabel( const std::vector< int > & p ) const;

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 [[nodiscard]] auto nodes( void ) const {
  return( std::views::iota( 0 , n() ) );
  }

/*--------------------------------------------------------------------------*/
 private:

 template< class Edges , class Get >
 void build( int n , const Edges & E , Get && get );

 [[nodiscard]] bool consistent( void ) const;

 bool f_directed = true;
 std::vector< int > f_off;
 std::vector< Arc > f_arc;
 int f_m = 0;

 };  // end( class StaticGraph )

/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

template< class W >
std::vector< int > bfsOrder( const StaticGraph< W > & g , int r = 0 );

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

}  // end( namespace ADS )

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

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

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

#endif  /* StaticGraph.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File StaticGraph.h -------------------------*/
/*--------------------------------------------------------------------------*/