Program Listing for File PointerGraph.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File PointerGraph.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <algorithm>
#include <list>
#include <queue>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS PointerGraph ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class W = int >
class PointerGraph {

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

 struct Node;

 struct Edge {
  Node * to;
  W weight;
  };

 struct Node {
  T label;
  int degree = 0;
  bool seen = false;
  std::list< Edge > out;
  };

 PointerGraph( void ) = default;
 PointerGraph( const PointerGraph & ) = delete;
 PointerGraph & operator=( const PointerGraph & ) = delete;

 [[nodiscard]] int n( void ) const { return( int( f_V.size() ) ); }

 Node * insertNode( const T & t );

 [[nodiscard]] Node * find( const T & t );

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

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

 void deleteEdge( Node * u , Node * v );

 bool deleteNode( Node * u );

 void forceDeleteNode( Node * u );

 [[nodiscard]] std::vector< Node * > adjacent( const Node * u ) const;

 template< class F >
 void dfs( Node * r , F && f );

 template< class F >
 void bfs( Node * r , F && f );

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

 void clear( void );

 [[nodiscard]] bool owns( const Node * u ) const;

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

 std::list< Node > f_V;

 };  // end( class PointerGraph )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PointerGraph.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File PointerGraph.h -------------------------*/
/*--------------------------------------------------------------------------*/