GraphAlgorithms.h

Go to the documentation of this file.

/*******************************************************************************
 * The software programs comprising "CGRA-ME" and the documentation provided
 * with them are copyright by its authors and the University of Toronto. Only
 * non-commercial, not-for-profit use of this software is permitted without ex-
 * plicit permission. This software is provided "as is" with no warranties or
 * guarantees of support. See the LICENCE for more details. You should have re-
 * ceived a copy of the full licence along with this software. If not, see
 * <http://cgra-me.ece.utoronto.ca/license/>.
 ******************************************************************************/
 
#ifndef __GRAPH_ALGORITHMS_H__
#define __GRAPH_ALGORITHMS_H__
 
#include <CGRA/utility/Collections.h>
#include <CGRA/impl/GraphAlgorithmHelpers.h>
 
#include <algorithm>
#include <array>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <thread>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
template<
    typename VertexID,
    typename MapGen = StandardMapMaker<std::unordered_map, VertexID>,
    typename SetGen = StandardSetMaker<std::unordered_set, VertexID>
>
class GraphAlgorithms {
private:
    int num_threads = 1; //< Max number of concurrent threads (may not be used by all algorithms)
 
    MapGen vertex_map_gen = {};
 
    SetGen vertex_set_gen = {};
 
public:
    GraphAlgorithms() { }
 
    template<typename NewMapGen, typename NewSetGen>
    GraphAlgorithms(
        int num_threads,
        NewMapGen&& vertex_map_gen,
        NewSetGen&& vertex_set_gen
    )
        : num_threads(num_threads)
        , vertex_map_gen(std::forward<NewMapGen>(vertex_map_gen))
        , vertex_set_gen(std::forward<NewSetGen>(vertex_set_gen))
    { }
 
    auto withThreads(int num_threads) const {
        return GraphAlgorithms<
            VertexID,
            MapGen
        >(
            num_threads,
            vertex_map_gen,
            vertex_set_gen
        );
    }
 
    template<typename NewMapGen>
    auto withMapGen(NewMapGen&& newVertexMapGen) const {
        return GraphAlgorithms<
            VertexID,
            std::decay_t<NewMapGen>,
            SetGen
        >(
            num_threads,
            std::forward<NewMapGen>(newVertexMapGen),
            vertex_set_gen
        );
    }
 
    template<typename NewSetGen>
    auto withSetGen(NewSetGen&& newVertexSetGen) const {
        return GraphAlgorithms<
            VertexID,
            MapGen,
            std::decay_t<NewSetGen>
        >(
            num_threads,
            vertex_map_gen,
            std::forward<NewSetGen>(newVertexSetGen)
        );
    }
 
    template<typename... Params>
    auto makeVertexMap() const {
        return this->vertex_map_gen.template operator()<Params...>();
    }
 
    template<typename... Params>
    auto makeVertexSet() const {
        return this->vertex_set_gen.template operator()<Params...>();
    }
 
    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>>;
 
    struct TracebackResult {
        VertexPath path;
        bool success;
 
        template<typename STREAM, typename GRAPH>
        void print(STREAM&& os, const GRAPH& g) const {
            os << "{success = " << success << "; ";
            print_container(os, path, [&](auto&& os, auto& v) { os << g.getNodeRef(v); });
            os << '}';
        }
 
        template<typename STREAM>
        friend STREAM& operator<<(STREAM& os, const TracebackResult& tbr) { tbr.print(os); return os; }
    };
 
    // this file has algorithms related to searching,
    // eg. depth- and breadth-first visits
    #include <CGRA/impl/GraphAlgorithms_Searching.inl>
 
    // this file has algorithms related to finding paths,
    // eg. tracing back through a search, and finding n shortest paths
    #include <CGRA/impl/GraphAlgorithms_Paths.inl>
 
}; // end class GraphAlgorithms
 
#endif // __GRAPH_ALGORITHMS_H__