Program Listing for File Visit.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File Visit.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/graph/Graph.h"
#include "ADS/graph/ListGraph.h"
#include "ADS/queue/ArrayQueue.h"

#include <algorithm>
#include <concepts>
#include <deque>
#include <limits>
#include <set>
#include <utility>
#include <vector>

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

namespace ADS {

inline constexpr int INF = std::numeric_limits< int >::max();

enum class Choice {
 NEWEST ,
 OLDEST
 };

inline constexpr int NIL = -1;

/*--------------------------------------------------------------------------*/
/*--------------------------------- BFS ------------------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G >
std::pair< std::vector< int > , std::vector< std::pair< int , int > > >
genericVisit( const G & g , int r , Choice c );

template< Graph G , class FN , class FE >
void bfs( const G & g , int r , FN && node , FE && edge );

template< Graph G >
std::pair< std::vector< int > , std::vector< int > > distance( const G & g ,
                                                                int r );

struct VisitCounts {
 long long nodes = 0 , edges = 0;
 };

template< Graph G , class Q >
requires requires( Q q , int v ) { q.enqueue( v ); { q.dequeue() } ->
                                   std::convertible_to< int >; }
std::pair< std::vector< int > , std::vector< int > > distance( const G & g ,
                                 int r , Q & S , VisitCounts * c = nullptr );

inline std::vector< int > path( int r , int s , const std::vector< int > & p );

/*--------------------------------------------------------------------------*/
/*--------------------------------- DFS ------------------------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G , class Pre , class Edge , class Post >
void dfs( const G & g , int u , std::vector< bool > & visited , Pre && pre ,
          Edge && edge , Post && post );

template< Graph G >
std::vector< int > cc( const G & g , std::vector< int > S );

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

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS DfsSchema ------------------------------*/
/*--------------------------------------------------------------------------*/

enum class EdgeKind { TREE , BACK , FORWARD , CROSS };

template< Graph G >
class DfsSchema {

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

 explicit DfsSchema( const G & g );

 template< class Edge >
 void visit( int u , Edge && edge );

 template< class Edge >
 void visitAll( Edge && edge );

 [[nodiscard]] int dt( int u ) const;

 [[nodiscard]] int ft( int u ) const;

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

 const G & f_g;
 std::vector< int > f_dt;
 std::vector< int > f_ft;
 int f_time = 0;

 };  // end( class DfsSchema )

/*--------------------------------------------------------------------------*/
/*--------------------- CYCLES, ORDERS AND COMPONENTS ----------------------*/
/*--------------------------------------------------------------------------*/

template< Graph G >
bool hasCycle( const G & g );

template< Graph G >
bool isTopologicalOrder( const G & g , const std::vector< int > & S );

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

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

template< Graph G >
ListGraph<> transpose( const G & g );

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

template< Graph G >
bool unilaterallyConnected( const G & g );

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

}  // end( namespace ADS )

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

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

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

#endif  /* Visit.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Visit.h ----------------------------*/
/*--------------------------------------------------------------------------*/