Program Listing for File Graph.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File Graph.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"
#include "ADS/sequence/List.h"

#include <concepts>
#include <cstddef>
#include <optional>
#include <ranges>
#include <string>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------------- CONCEPTS --------------------------------*/
/*--------------------------------------------------------------------------*/

template< class G >
concept Graph = requires( const G g , int u ) {
 { g.n() } -> std::convertible_to< int >;
 { g.bound() } -> std::convertible_to< int >;
 { g.directed() } -> std::same_as< bool >;
 { g.hasNode( u ) } -> std::same_as< bool >;
 { g.V() } -> std::same_as< std::vector< int > >;
 { g.adj( u ) } -> std::same_as< std::vector< int > >;
 g.forEachAdj( u , []( int ) {} );
 };

template< class G >
concept DynamicGraph = Graph< G > && requires( G g , int u , int v ) {
 { g.insertNode() } -> std::same_as< int >;
 g.insertEdge( u , v );
 g.deleteNode( u );
 g.deleteEdge( u , v );
 };

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS GraphNodes ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class GraphNodes {

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

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

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

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

 [[nodiscard]] int bound( void ) const { return( int( f_alive.size() ) ); }

 [[nodiscard]] bool hasNode( int u ) const;

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

 [[nodiscard]] const T & label( int u ) const;

 void setLabel( int u , const T & t );

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

 // the nodes and (in the derived graphs) the adjacent nodes as ranges,
 // which visit them where they are, instead of the vectors that V() and
 // adj() build

 struct Alive {
  static std::size_t size( const auto & o ) { return( o.f_alive.size() ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( o.f_alive[ i ] );
   }
  static int read( const auto & , std::size_t i ) { return( int( i ) ); }
  };

 [[nodiscard]] auto nodes( void ) const {
  using It = SlotIterator< GraphNodes , Alive >;
  return( std::ranges::subrange( It( this , 0 ) ,
                                 It( this , f_alive.size() ) ) );
  }

/*--------------------------------------------------------------------------*/
 protected:

 GraphNodes( int n , bool directed );

 int addNode( const T & t );

 int check( int u ) const;

 void edge( int u , int v ) const;

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

 bool f_directed;
 std::vector< bool > f_alive;
 std::vector< T > f_label;
 int f_n = 0;
 int f_m = 0;

 };  // end( class GraphNodes )

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

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

inline std::vector< int > adjFromIncidence(
                          const std::vector< std::vector< int > > & B ,
                          int u , bool directed );

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

}  // end( namespace ADS )

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

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

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

#endif  /* Graph.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Graph.h ----------------------------*/
/*--------------------------------------------------------------------------*/