graph_paths.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_ADTS_GRAPH_PATHS_H
#define ELEMENTA_ADTS_GRAPH_PATHS_H
 
#include <type_traits>
#include <vector>
#include <functional>
#include "elementa/adts/graphs/graphs.h"
 
 
namespace elementa
{
 
namespace adts
{
 
namespace graphs
{
 
/* ***************************************************************************
 
    Enum type: GPathKind
    Template type: GPathKindType
    Constepxr: kOtherGPathKind
    Template type: GPathElement
    Template class: GPath
    
*******************************************************************************/
 
ELE_CLASS_ENUM(GPathKind,
                kVertexPath,    
                kEdgePath       
                );
 
template <GPathKind KIND>
struct GPathKindType {};
 
constexpr GPathKind kOtherGPathKind(GPathKind kid)
{ return(kid == GPathKind::kVertexPath ?  GPathKind::kEdgePath :
                                            GPathKind::kVertexPath); }
 
template <class Vertex, class Edge, GPathKind KIND>
using GPathElement = typename std::conditional<
                            KIND == GPathKind::kVertexPath,
                            typename Graph<Vertex,Edge>::viterator,
                            typename Graph<Vertex,Edge>::eiterator >::type;
 
template <class Vertex, class Edge, GPathKind KIND>
class GPath: public std::vector< GPathElement<Vertex,Edge,KIND> >
{
 public:
 
    static const GPathKind kKind = KIND;
 
    using VectorElem = GPathElement<Vertex,Edge,KIND>;
 
    using BasePath = std::vector<VectorElem>;
 
    using BaseGraph = Graph<Vertex,Edge>;
 
    using Collection = std::vector<GPath>;
 
    using BasePath::BasePath;
 
 
    GPath< Vertex,Edge,kOtherGPathKind(KIND) > other(
        const BaseGraph & g,
        const typename BaseGraph::EPred & epred = BaseGraph::trivial_epred)const
        { return(other_hidden(g,epred,GPathKindType<KIND>{})); }
 
 
    std::string to_string(const BaseGraph & g,
                          const std::function<std::string(const Vertex & vd)> & 
                            vtostr = [](const Vertex & vd)->std::string 
                                     { return(std::to_string(vd)); },
                          const std::function<std::string(const Edge & ed)> & 
                            etostr = [](const Edge & ed)->std::string 
                                     { return(std::to_string(ed)); }) const
        { return(to_string_hidden(g,vtostr,etostr,GPathKindType<KIND>{})); }
 
 private:
 
 
    GPath<Vertex,Edge,kOtherGPathKind(KIND)> other_hidden(
                                const BaseGraph & g,
                                const typename BaseGraph::EPred & p,
                                GPathKindType<GPathKind::kVertexPath>) const;
 
 
    GPath<Vertex,Edge,kOtherGPathKind(KIND)> other_hidden(
                                const BaseGraph & g,
                                const typename BaseGraph::EPred & p,
                                GPathKindType<GPathKind::kEdgePath>) const;
 
    std::string to_string_hidden(const BaseGraph & g,
                          const std::function<std::string(const Vertex & vd)> & 
                            vtostr, 
                          const std::function<std::string(const Edge & ed)> & 
                            etostr, 
                          GPathKindType<GPathKind::kVertexPath>) const;
 
    std::string to_string_hidden(const BaseGraph & g,
                          const std::function<std::string(const Vertex & vd)> & 
                            vtostr, 
                          const std::function<std::string(const Edge & ed)> & 
                            etostr, 
                          GPathKindType<GPathKind::kEdgePath>) const;
};
 
 
/* ***************************************************************************
 
    Template type: EdgeWeightFunction
    Template constexpr: trivial_edge_weight, value_edge_weight
    
*******************************************************************************/
 
template <class Vertex, class Edge, class Weight = double>
using EdgeWeightFunction = 
    std::function< Weight(const typename Graph<Vertex,Edge>::eiterator &) >;
 
template <class Vertex, class Edge>
constexpr double trivial_edge_weight(
    const typename Graph<Vertex,Edge>::eiterator &) noexcept
        { return(1.0); }
 
 
template <class Vertex, class Edge>
constexpr double value_edge_weight(
    const typename Graph<Vertex,Edge>::eiterator & eit) noexcept
        { return(*eit); }
 
 
 
/* ===========================================================================
 
        ========== IMPLEMENTATION OF TEMPLATES ===========
 
============================================================================= */
 
/* ***************************************************************************
 
    Template class: GPath
    
*******************************************************************************/
 
template <class Vertex, class Edge, GPathKind KIND>
GPath<Vertex,Edge,kOtherGPathKind(KIND)> 
    GPath<Vertex,Edge,KIND>::other_hidden(
                                const BaseGraph & g,
                                const typename BaseGraph::EPred & p,
                                GPathKindType<GPathKind::kVertexPath>) const
{
    // from vertex to edge path
    GPath<Vertex,Edge,GPathKind::kEdgePath> np;
 
    bool first{true};
    typename BaseGraph::viterator prevvit;
    for (const auto & vit : *this)
    {
        if (first) first = false;
        else np.push_back(g.connected(prevvit,vit,p));
        prevvit = vit;
    }
    return(np);
}
 
template <class Vertex, class Edge, GPathKind KIND>
GPath<Vertex,Edge,kOtherGPathKind(KIND)>
    GPath<Vertex,Edge,KIND>::other_hidden(
                                const BaseGraph & g,
                                const typename BaseGraph::EPred & p,
                                GPathKindType<GPathKind::kEdgePath>) const
{
    // from edge to vertex path
    GPath<Vertex,Edge,GPathKind::kVertexPath> np;
 
    auto eit = this->begin();
    typename BaseGraph::viterator vit0,vit1;
    bool first{true};
    while (eit != this->end())
    {
        g.connection(eit,vit0,vit1);
        if (first) 
        {
            np.push_back(vit0);
            first = false;
        }
        np.push_back(vit1);
        ++eit;
    }
 
    return(np);
}
 
template <class Vertex, class Edge, GPathKind KIND>
std::string GPath<Vertex,Edge,KIND>::to_string_hidden(
                const BaseGraph & g,
                const std::function<std::string(const Vertex & vd)> & vtostr, 
                const std::function<std::string(const Edge & ed)> & etostr, 
                GPathKindType<GPathKind::kVertexPath>) const
{
    std::string res{"VPATH with "};
    res += std::to_string(this->size()) + " vertices: < ";
    for (const auto & vit: *this) res += vtostr(*vit) + " ";
    return(res + ">");
}
 
template <class Vertex, class Edge, GPathKind KIND>
std::string GPath<Vertex,Edge,KIND>::to_string_hidden(
                const BaseGraph & g,
                const std::function<std::string(const Vertex & vd)> & vtostr, 
                const std::function<std::string(const Edge & ed)> & etostr, 
                GPathKindType<GPathKind::kEdgePath>) const
{
    std::string res{"EPATH with "};
    res += std::to_string(this->size()) + " edges: < ";
    typename BaseGraph::viterator vit0,vit1;
    for (const auto & eit: *this) 
    {
        g.connection(eit,vit0,vit1);
        res += etostr(*eit) + ":(" + vtostr(*vit0) + " -> " + 
               vtostr(*vit1) + ") ";
    }
    return(res + ">");
}
 
 
} // end graphs namespace
 
} // end adts namespace
 
} // end elementa namespace
 
 
#endif