Program Listing for File ArrayGraph.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File ArrayGraph.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <ranges>
#include <span>
#include <tuple>
#include <variant>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS ArrayGraph ----------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Weight = W;

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

 template< Graph G >
 explicit ArrayGraph( 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 bound( void ) const { return( n() ); }

 [[nodiscard]] bool hasNode( 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;

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

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

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

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

 template< class G >
 static std::vector< std::tuple< int , int , W > > edges( const G & g );

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

 bool f_directed;
 std::vector< int > f_off;
 std::vector< int > f_to;
 std::vector< W > f_w;
 int f_m = 0;

 };  // end( class ArrayGraph )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ArrayGraph.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File ArrayGraph.h --------------------------*/
/*--------------------------------------------------------------------------*/