Program Listing for File MatrixGraph.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File MatrixGraph.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <cstddef>
#include <optional>
#include <ranges>
#include <variant>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS MatrixGraph ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class W = std::monostate , class T = std::monostate >
class MatrixGraph : public GraphNodes< T > {

 using B = GraphNodes< T >;

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

 using Weight = W;
 using Label = T;

 explicit MatrixGraph( int n = 0 , bool directed = true );

 int insertNode( const T & t = T() );

 void insertEdge( int u , int v , const W & w = W() );

 void deleteEdge( int u , int v );

 void deleteNode( int u );

 [[nodiscard]] bool hasEdge( int u , int v ) const;

 [[nodiscard]] std::optional< W > weight( int u , int v ) 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 -------------------------*/

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

 [[nodiscard]] auto neighbors( int u ) const {
  using It = SlotIterator< std::vector< std::optional< W > > , Present >;
  const auto & r = f_M[ this->check( u ) ];
  return( std::ranges::subrange( It( &r , 0 ) , It( &r , r.size() ) ) );
  }

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

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

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

 std::vector< std::vector< std::optional< W > > > f_M;

 };  // end( class MatrixGraph )

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

}  // end( namespace ADS )

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

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

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

#endif  /* MatrixGraph.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File MatrixGraph.h -------------------------*/
/*--------------------------------------------------------------------------*/