Program Listing for File ListGraph.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File ListGraph.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <concepts>
#include <optional>
#include <ranges>
#include <utility>
#include <variant>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS ListGraph -----------------------------*/
/*--------------------------------------------------------------------------*/

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

 using B = GraphNodes< T >;

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

 using Weight = W;
 using Label = T;

 explicit ListGraph( 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 -------------------------*/

 [[nodiscard]] auto neighbors( int u ) const {
  using It = KeyIterator< typename List< std::pair< int , W > >::
                          const_iterator >;
  const auto & L = f_adj[ this->check( u ) ];
  return( std::ranges::subrange( It( L.begin() ) , It( L.end() ) ) );
  }

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

 bool find( int u , int v ) const;

 bool set( int u , int v , const W & w );

 bool erase( int u , int v );

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

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

 std::vector< List< std::pair< int , W > > > f_adj;

 };  // end( class ListGraph )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ListGraph.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File ListGraph.h --------------------------*/
/*--------------------------------------------------------------------------*/