CGRA-ME
Classes | Public Types | Public Member Functions | Private Attributes | List of all members
GraphAlgorithms< VertexID, MapGen, SetGen > Class Template Reference

#include <GraphAlgorithms.h>

Classes

struct  TracebackResult
 

Public Types

template<typename... Params>
using VertexMap = std::decay_t< decltype(std::declval< MapGen >().template operator()<Params... >())>
 
using VertexList = std::vector< VertexID >
 
using VertexPath = VertexList
 
template<typename... Params>
using VertexSet = std::decay_t< decltype(std::declval< SetGen >().template operator()<Params... >())>
 
using PathList = std::vector< VertexPath >
 
using EdgeSet = std::set< std::pair< VertexID, VertexID > >
 

Public Member Functions

 GraphAlgorithms ()
 
template<typename NewMapGen , typename NewSetGen >
 GraphAlgorithms (int num_threads, NewMapGen &&vertex_map_gen, NewSetGen &&vertex_set_gen)
 
auto withThreads (int num_threads) const
 
template<typename NewMapGen >
auto withMapGen (NewMapGen &&newVertexMapGen) const
 
template<typename NewSetGen >
auto withSetGen (NewSetGen &&newVertexSetGen) const
 
template<typename... Params>
auto makeVertexMap () const
 
template<typename... Params>
auto makeVertexSet () const
 

Private Attributes

int num_threads = 1
 
MapGen vertex_map_gen = {}
 
SetGen vertex_set_gen = {}
 

Detailed Description

template<typename VertexID, typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
class GraphAlgorithms< VertexID, MapGen, SetGen >

A generic graph algorithms library. Works with any object - the only required interface is a unary function called fanout that takes a vertex id, and returns a range-like object (ie. has .begin() and .end()) of objects that can be converted to vertex ids.

First, a small example using a depth first visit:

struct Graph { std::vector<std::vector<int>> fanout_lists; const std::vector<int>& fanout(int ndesc) const { return fanout_lists.at(ndesc); } } g { {{1}, {2,0}, {3,0}, {1,0}} };

struct Visitor : DoNothingGraphVisitor<int> { void onExplore(int ndesc) { std::cout << ndesc << ' '; } } v;

GraphAlgorithms<int> g_algos;

// this should print: 1 2 3 0 g_algos.depthFirstVisit(g, 1, [](auto&&) { return false; }, v);

// (end example)

The GraphAlgorithms class itself store no information about any graphs or algorithms that are called. It only serves as a common configuration object for meta-parameters, such as the number of threads used, and what sort of map is used to store data indexed by vertices when running algorithms.

The default constructor is sufficient for most purposes. If configuration of the meta-parameters is desired, then other constructors can be used, or the builder-style member functions can be called.

Definition at line 72 of file GraphAlgorithms.h.

Member Typedef Documentation

◆ EdgeSet

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
using GraphAlgorithms< VertexID, MapGen, SetGen >::EdgeSet = std::set<std::pair<VertexID, VertexID> >

Definition at line 184 of file GraphAlgorithms.h.

◆ PathList

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
using GraphAlgorithms< VertexID, MapGen, SetGen >::PathList = std::vector<VertexPath>

Definition at line 183 of file GraphAlgorithms.h.

◆ VertexList

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
using GraphAlgorithms< VertexID, MapGen, SetGen >::VertexList = std::vector<VertexID>

Definition at line 179 of file GraphAlgorithms.h.

◆ VertexMap

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename... Params>
using GraphAlgorithms< VertexID, MapGen, SetGen >::VertexMap = std::decay_t<decltype(std::declval<MapGen>().template operator()<Params...>())>

Definition at line 178 of file GraphAlgorithms.h.

◆ VertexPath

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
using GraphAlgorithms< VertexID, MapGen, SetGen >::VertexPath = VertexList

Definition at line 180 of file GraphAlgorithms.h.

◆ VertexSet

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename... Params>
using GraphAlgorithms< VertexID, MapGen, SetGen >::VertexSet = std::decay_t<decltype(std::declval<SetGen>().template operator()<Params...>())>

Definition at line 182 of file GraphAlgorithms.h.

Constructor & Destructor Documentation

◆ GraphAlgorithms() [1/2]

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
GraphAlgorithms< VertexID, MapGen, SetGen >::GraphAlgorithms ( )
inline

Definition at line 102 of file GraphAlgorithms.h.

◆ GraphAlgorithms() [2/2]

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename NewMapGen , typename NewSetGen >
GraphAlgorithms< VertexID, MapGen, SetGen >::GraphAlgorithms ( int  num_threads,
NewMapGen &&  vertex_map_gen,
NewSetGen &&  vertex_set_gen 
)
inline

Definition at line 105 of file GraphAlgorithms.h.

Member Function Documentation

◆ makeVertexMap()

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename... Params>
auto GraphAlgorithms< VertexID, MapGen, SetGen >::makeVertexMap ( ) const
inline

Definition at line 168 of file GraphAlgorithms.h.

◆ makeVertexSet()

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename... Params>
auto GraphAlgorithms< VertexID, MapGen, SetGen >::makeVertexSet ( ) const
inline

Definition at line 173 of file GraphAlgorithms.h.

◆ withMapGen()

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename NewMapGen >
auto GraphAlgorithms< VertexID, MapGen, SetGen >::withMapGen ( NewMapGen &&  newVertexMapGen) const
inline

A builder-style function for specifying the vertex map maker This function returns (by value) a GraphAlgorithms object that only differs in what object is used to make a vertex map.

Definition at line 137 of file GraphAlgorithms.h.

◆ withSetGen()

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
template<typename NewSetGen >
auto GraphAlgorithms< VertexID, MapGen, SetGen >::withSetGen ( NewSetGen &&  newVertexSetGen) const
inline

A builder-style function for specifying the vertex set maker This function returns (by value) a GraphAlgorithms object that only differs in what object is used to make a vertex set.

Definition at line 155 of file GraphAlgorithms.h.

◆ withThreads()

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
auto GraphAlgorithms< VertexID, MapGen, SetGen >::withThreads ( int  num_threads) const
inline

A builder-style function for specifying the number of threads. This function returns (by value) a GraphAlgorithms object that only differs in the maximum number of threads.

Definition at line 120 of file GraphAlgorithms.h.

Member Data Documentation

◆ num_threads

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
int GraphAlgorithms< VertexID, MapGen, SetGen >::num_threads = 1
private

Definition at line 82 of file GraphAlgorithms.h.

◆ vertex_map_gen

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
MapGen GraphAlgorithms< VertexID, MapGen, SetGen >::vertex_map_gen = {}
private

The map generator object used. This object may be called in a concurrent manner, and therefore must be thread-safe. A nullary template operator() must be supplied, which will be passed template parameters corresponding to the mapped type. See makeVertexMap for exact details.

Definition at line 91 of file GraphAlgorithms.h.

◆ vertex_set_gen

template<typename VertexID , typename MapGen = StandardMapMaker<std::unordered_map, VertexID>, typename SetGen = StandardSetMaker<std::unordered_set, VertexID>>
SetGen GraphAlgorithms< VertexID, MapGen, SetGen >::vertex_set_gen = {}
private

The set generator object used. This object may be called in a concurrent manner, and therefore must be thread-safe. A nullary template operator() must be supplied, See makeVertexSet for exact details.

Definition at line 99 of file GraphAlgorithms.h.

The documentation for this class was generated from the following file:
Generated on Fri Nov 17 2023 12:26:53 for CGRA-ME by   doxygen 1.8.17