graphs.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_ADTS_GRAPHS_GRAPHS_H
#define ELEMENTA_ADTS_GRAPHS_GRAPHS_H
 
#include <cstddef>
#include <memory>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <type_traits>
#include "elementa/base/definitions.h"
#include "elementa/base/fundamentaltypes.h"
#include "elementa/base/exceptions.h"
#include "elementa/base/iterators.h"
#include "elementa/base/serial_channels/serializers.h"
#include "elementa/patterns/clonable.h"
 
#include "elementa/base/debugging.h"
 
 
namespace elementa
{
 
namespace adts
{
 
namespace graphs
{
 
/* ***************************************************************************
 
    General definitions: size_vertex, size_edge
    
*******************************************************************************/
 
using size_vertex = size_t;
 
using size_edge = size_t;
 
 
/* ***************************************************************************
 
    Base template class: Graph
    
*******************************************************************************/
 
 
template <class Vertex, class Edge>
class Graph: public elementa::patterns::Clonable
{
 public:
 
    using VertexType = Vertex;
    using EdgeType = Edge;
 
    using viterator = elementa::base::MultIterator<Vertex>;
 
    using eiterator = elementa::base::MultIterator<Edge>;
 
 
 
    class VectorOfVIts: public std::vector<viterator>
    {
     public:
 
        VectorOfVIts(void) = default;
 
 
        VectorOfVIts(const Graph & g);
    };
 
 
    class VectorOfEIts: public std::vector<eiterator>
    {
     public:
 
        VectorOfEIts(void) = default;
 
 
        VectorOfEIts(const Graph & g);
    };
 
 
    class MapOfVItPos
    {
     public:
 
 
        MapOfVItPos(const Graph & g);
 
 
        MapOfVItPos(const VectorOfVIts & m);
 
        MapOfVItPos(const MapOfVItPos & oth) { copyFrom(oth); }
        MapOfVItPos(MapOfVItPos && oth) { moveFrom(std::move(oth)); }
        MapOfVItPos & operator=(const MapOfVItPos & oth)
            { if (this != &oth) copyFrom(oth); return(*this); }
        MapOfVItPos & operator=(MapOfVItPos && oth)
            { if (this != &oth) moveFrom(std::move(oth)); return(*this); }
 
        ~MapOfVItPos(void) = default;
 
 
 
        size_t size(void) const noexcept { return(map_.size()); }
 
        bool empty(void) const noexcept { return(map_.empty()); }
 
 
        size_t at(const viterator & vit) const
            { return(map_.at(vit.implementation()->pointedData())); }
 
     private:
 
        std::unordered_map< void * , size_t > map_;
 
        void copyFrom(const MapOfVItPos & oth) { map_ = oth.map_; }
        void moveFrom(MapOfVItPos && oth) { map_ = std::move(oth.map_); }
    };
 
 
    class MapOfEItPos
    {
     public:
 
 
        MapOfEItPos(const Graph & g);
 
 
        MapOfEItPos(const VectorOfEIts & m);
 
        MapOfEItPos(const MapOfEItPos & oth) { copyFrom(oth); }
        MapOfEItPos(MapOfEItPos && oth) { moveFrom(std::move(oth)); }
        MapOfEItPos & operator=(const MapOfEItPos & oth)
            { if (this != &oth) copyFrom(oth); return(*this); }
        MapOfEItPos & operator=(MapOfEItPos && oth)
            { if (this != &oth) moveFrom(std::move(oth)); return(*this); }
 
        ~MapOfEItPos(void) = default;
 
 
 
        size_t size(void) const noexcept { return(map_.size()); }
 
        bool empty(void) const noexcept { return(map_.empty()); }
 
 
        size_t at(const eiterator & eit) const
            { return(map_.at(eit.implementation()->pointedData())); }
 
     private:
 
        std::unordered_map< void * , size_t > map_;
 
        void copyFrom(const MapOfEItPos & oth) { map_ = oth.map_; }
        void moveFrom(MapOfEItPos && oth) { map_ = std::move(oth.map_); }
    };
 
 
    using EPred = std::function< bool(const Edge &) >;
 
    static constexpr bool trivial_epred(const Edge &) noexcept { return(true); }
 
    static constexpr bool nil_epred(const Edge &) noexcept { return(false); }
 
 
    class VRange_All: public elementa::base::Range<viterator>
    {
     public:
 
 
        VRange_All(const Graph & gr):gr_{&gr} {}
 
        viterator begin(void) const { return(gr_->vallbegin()); }
        viterator end(void) const { return(gr_->vallend()); }       
 
     private:
        
        const Graph * gr_;
    };
 
 
    class VRange_Pred: public elementa::base::Range<viterator>
    {
     public:
 
 
        using Pred = std::function< bool(const Vertex &) >;
 
 
        VRange_Pred(const Graph & gr, eiterator & eit,
                    Pred & pred): gr_{&gr}, eit_{&eit}, pred_{&pred} {}
 
 
        viterator begin(void) const;
        viterator end(void) const;
 
     private:
        
        const Graph * gr_;
        eiterator * eit_;
        Pred * pred_;
    };
 
    class ERange_All: public elementa::base::Range<eiterator>
    {
     public:
 
 
        ERange_All(const Graph & gr):gr_{&gr} {}
 
        eiterator begin(void) const { return(gr_->eallbegin()); }
        eiterator end(void) const { return(gr_->eallend()); }       
 
     private:
        
        const Graph * gr_;
    };
 
 
    class ERange_Pred: public elementa::base::Range<eiterator>
    {
     public:
 
 
        ERange_Pred(const Graph & gr, eiterator & eit,
                    EPred & pred): gr_{&gr}, eit_{&eit}, pred_{&pred} {}
 
 
        eiterator begin(void) const;
        eiterator end(void) const;
 
     private:
        
        const Graph * gr_;
        eiterator * eit_;
        EPred * pred_;
    };
 
    class ERange_Leaving: public elementa::base::Range<eiterator>
    {
     public:
 
 
        ERange_Leaving(const Graph & gr, const viterator & v):gr_{&gr},
                                                                     v_{v} {}
 
        eiterator begin(void) const { return(gr_->eleavingbegin(v_));}
        eiterator end(void) const { return(gr_->eleavingend(v_)); }     
 
     private:
        
        const Graph * gr_;
        viterator v_;
    };
 
    class ERange_Entering: public elementa::base::Range<eiterator>
    {
     public:
 
 
        ERange_Entering(const Graph & gr, const viterator & v):
                                                                    gr_{&gr},
                                                                    v_{v} {}
 
        eiterator begin(void) const { return(gr_->eenteringbegin(v_));}
        eiterator end(void) const { return(gr_->eenteringend(v_)); }        
 
     private:
        
        const Graph * gr_;
        viterator v_;
    };
 
 
    class ERange_DepthFirst: public elementa::base::Range<eiterator>
    {
     public:
 
 
        static size_edge forceBacktrack(eiterator & eit);
 
 
        ERange_DepthFirst(const Graph & gr, const viterator & v):
                                                                    gr_{&gr},
                                                                    v_{v}
            {ELE_CODE_TRACE_OFF; 
                ELE_CODE_TRACE({}, "created erangedepthfirst.");
                ELE_CODE_TRACE({}, "\t(for node " << v.to_string() << ")");
                ELE_CODE_TRACE({}, "\t(keeping copy " << v_.to_string() << ")"); 
            }
 
        eiterator begin(void) const { return(gr_->edepthfirstbegin(v_));}
        eiterator end(void) const { return(gr_->edepthfirstend(v_)); }
 
     private:
 
        const Graph * gr_;
        viterator v_;       
    };
 
 
    class ERange_BreadthFirst: public elementa::base::Range<eiterator>
    {
     public:
 
 
        ERange_BreadthFirst(const Graph & gr, const viterator & v):
                                                                    gr_{&gr},
                                                                    v_{v}
            {}
 
        eiterator begin(void) const 
            { return(gr_->ebreadthfirstbegin(v_)); }
        eiterator end(void) const 
            { return(gr_->ebreadthfirstend(v_)); }
 
     private:
 
        const Graph * gr_;
        viterator v_;       
    };
 
    Graph(void) = default;
 
    Graph(const Graph & oth) = default;
 
    Graph & operator=(const Graph & oth) = default;
 
    Graph(Graph && oth) = default;
 
    Graph & operator=(Graph && oth) = default;
 
    virtual ~Graph(void) = default;
 
    virtual bool empty(void) const = 0;
    
    virtual size_vertex size_vertices(void) const = 0;
    
    virtual size_edge size_edges(void) const = 0;
 
    bool isLeaf(const viterator & it) const noexcept
        { return((it.valid()) && (erangeLeaving(it).begin().isEnd())); }
 
    bool toLeaf(const eiterator & it) const noexcept
        { return((it.valid()) && (isLeaf(destination(it)))); }
 
 
    bool toLastChild(const eiterator & it, const viterator & vit)const noexcept;
 
 
    virtual viterator origin(const eiterator & it) const = 0;
 
 
    virtual viterator destination(const eiterator & it) const = 0;
 
 
    virtual void connection(const eiterator & it, 
                            viterator & vorg, viterator & vdest) const
        { vorg = origin(it); vdest = destination(it); }
 
 
    virtual eiterator connected(const viterator & v0, 
                                const viterator & v1,
                                const EPred & epred = trivial_epred) const;
 
 
    virtual viterator find_vertex(const Vertex & v) const;
 
 
    virtual eiterator find_edge(const Edge & e) const;
 
 
    virtual size_t vertexToPos(const viterator & vit) const;
 
 
    virtual viterator posToVertex(size_t vpos) const;
 
 
    virtual size_t edgeToPos(const eiterator & eit) const;
 
 
    virtual eiterator posToEdge(size_t epos) const;
 
    virtual void clear(void) = 0;
 
 
    virtual viterator insert(const Vertex & v) = 0;
 
 
    virtual eiterator connect(const viterator & itv0, const viterator & itv1, 
                              const Edge & e) = 0;
 
 
    virtual void unconnect(const eiterator & ite) = 0;
 
 
    virtual void unconnect(const VectorOfEIts & sinds) = 0;
 
 
    virtual void erase(const viterator & itv) = 0;
 
 
    virtual void erase(const VectorOfVIts & sinds) = 0;
 
 
    virtual void splice(Graph & oth, 
                        VectorOfVIts * svothits = nullptr, 
                        VectorOfEIts * seothits = nullptr,
                        VectorOfVIts * svits = nullptr, 
                        VectorOfEIts * seits = nullptr) = 0;
 
    VRange_All vrangeAll(void) const 
        { return(VRange_All{*this}); }
 
    VRange_Pred vrangePred(eiterator & eit, 
                           typename VRange_Pred::Pred & pred) const
        { return(VRange_Pred{*this,eit,pred}); }
 
    ERange_All erangeAll(void) const 
        { return(ERange_All{*this}); }
 
    ERange_Pred erangePred(eiterator & eit, const EPred & pred) const
        { return(ERange_Pred{*this,eit,pred}); }
 
    ERange_Leaving erangeLeaving(const viterator & v) const
        { return(ERange_Leaving{*this,v}); }
 
    ERange_Entering erangeEntering(const viterator & v) const
        { return(ERange_Entering{*this,v}); }
 
    ERange_DepthFirst erangeDepthFirst(const viterator & v) const
        { return(ERange_DepthFirst{*this,v}); }
 
    ERange_BreadthFirst erangeBreadthFirst(const viterator & v) const
        { return(ERange_BreadthFirst{*this,v}); }
 
 protected:
 
    virtual viterator vallbegin(void) const = 0;
 
    virtual viterator vallend(void) const = 0;
 
    virtual eiterator eallbegin(void) const = 0;
 
    virtual eiterator eallend(void) const = 0;
 
    virtual eiterator eleavingbegin(const viterator &v) const = 0;
 
    virtual eiterator eleavingend(const viterator &v) const = 0;
 
    virtual eiterator eenteringbegin(const viterator &v) const = 0;
 
    virtual eiterator eenteringend(const viterator &v) const = 0;
 
 
 private:
 
    // Depth-first, bread-first and Pred iterator behaviours provided entirely.
 
    class VItImpl_Pred final: public elementa::base::MultItImpl<Vertex>
                                    // indirectly derives from Validatable
    {
     public:
 
        VItImpl_Pred(const Graph & gr, 
                     typename VRange_Pred::Pred & itpred,
                     eiterator & eit, 
                     bool beginorend = true): 
                                        elementa::patterns::Validatable{true},
                                        gr_{&gr},
                                        itpred_{&itpred},
                                        eit_{&eit}
            { if (beginorend) { isend_ = false; iterateToNext(); }
              else isend_ = true; }
            
        VItImpl_Pred(const VItImpl_Pred & oth):
                                    elementa::patterns::Validatable{oth},
                                    elementa::base::MultItImpl<Vertex>{oth}
            { copyFrom(oth); }
 
        VItImpl_Pred & operator=(const VItImpl_Pred & oth) 
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Vertex>::operator=(oth);
                copyFrom(oth); 
              } 
              return(*this); }
 
        VItImpl_Pred(VItImpl_Pred && oth):
                            elementa::patterns::Validatable{std::move(oth)},
                            elementa::base::MultItImpl<Vertex>{std::move(oth)}
            { moveFrom(std::move(oth)); }
 
        VItImpl_Pred & operator=(VItImpl_Pred && oth)
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Vertex>::operator=(std::move(oth));
                moveFrom(std::move(oth)); 
              }
              return(*this); }
 
        typename elementa::base::MultItImpl<Vertex>::Ptr clone(void) const
            { return(typename elementa::base::MultItImpl<Vertex>::Ptr{
                        new VItImpl_Pred{*this}}); }
 
        Vertex & operator*(void)
            { checkDeref(); auto vit = gr_->destination(*eit_);
              return(*vit); }
              
        Vertex * pointedData(void) const
            { if ((isend_)||(eit_->isEnd())) return(nullptr); 
              return(&(const_cast<VItImpl_Pred *>(this)->operator*())); }
 
        VItImpl_Pred & operator++(void)
            { if ((!isend_)&&(!eit_->isEnd())) { ++(*eit_); iterateToNext(); } 
              return(*this); }
 
        std::string to_string(void) const override;
 
     private:
 
        bool isend_;
        const Graph * gr_;
        typename VRange_Pred::Pred * itpred_;
        eiterator * eit_;
 
        void checkDeref(void) const;
        void iterateToNext(void);
        
        void copyFrom(const VItImpl_Pred & oth)
            { isend_ = oth.isend_; gr_ = oth.gr_; itpred_ = oth.itpred_; 
              eit_ = oth.eit_; }
 
        void moveFrom(VItImpl_Pred && oth)
            { copyFrom(oth); oth.isend_ = true; }
 
    };
 
    class EItImpl_Pred final: public elementa::base::MultItImpl<Edge>
                                    // indirectly derives from Validatable
    {
     public:
 
        EItImpl_Pred(const Graph & gr, 
                     typename ERange_Pred::Pred & itpred,
                     eiterator & eit, 
                     bool beginorend = true): 
                                        elementa::patterns::Validatable{true},
                                        gr_{&gr},
                                        itpred_{&itpred},
                                        eit_{&eit}
            { if (beginorend) { isend_ = false; iterateToNext(); }
              else isend_ = true; }
            
        EItImpl_Pred(const EItImpl_Pred & oth):
                                    elementa::patterns::Validatable{oth},
                                    elementa::base::MultItImpl<Edge>{oth}
            { copyFrom(oth); }
 
        EItImpl_Pred & operator=(const EItImpl_Pred & oth) 
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(oth);
                copyFrom(oth); 
              } 
              return(*this); }
 
        EItImpl_Pred(EItImpl_Pred && oth):
                            elementa::patterns::Validatable{std::move(oth)},
                            elementa::base::MultItImpl<Edge>{std::move(oth)}
            { moveFrom(std::move(oth)); }
 
        EItImpl_Pred & operator=(EItImpl_Pred && oth)
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(std::move(oth));
                moveFrom(std::move(oth)); 
              }
              return(*this); }
 
        typename elementa::base::MultItImpl<Edge>::Ptr clone(void) const
            { return(typename elementa::base::MultItImpl<Edge>::Ptr{
                        new EItImpl_Pred{*this}}); }
 
        Edge & operator*(void)
            { checkDeref(); return(*(*eit_)); }
              
        Edge * pointedData(void) const
            { if ((isend_)||(eit_->isEnd())) return(nullptr); 
              return(&(const_cast<EItImpl_Pred *>(this)->operator*())); }
 
        EItImpl_Pred & operator++(void)
            { if ((!isend_)&&(!eit_->isEnd())) { ++(*eit_); iterateToNext(); }
              return(*this); }
 
        std::string to_string(void) const override;
 
     private:
 
        bool isend_;
        const Graph * gr_;
        typename ERange_Pred::Pred * itpred_;
        eiterator * eit_;
 
        void checkDeref(void) const;
        void iterateToNext(void);
        
        void copyFrom(const EItImpl_Pred & oth)
            { isend_ = oth.isend_; gr_ = oth.gr_; itpred_ = oth.itpred_; 
              eit_ = oth.eit_; }
 
        void moveFrom(EItImpl_Pred && oth)
            { copyFrom(oth); oth.isend_ = true; }
 
    };
 
    // Edge iteration for depth-first search from a vertex.
    class EItImpl_DepthFirst final: public elementa::base::MultItImpl<Edge>
                                    // indirectly derives from Validatable
    {
     public:
 
        EItImpl_DepthFirst(Graph & gr, const viterator & vi, 
                           bool beginorend = true);
            
        EItImpl_DepthFirst(const EItImpl_DepthFirst & oth):
                                        elementa::patterns::Validatable{oth},
                                        elementa::base::MultItImpl<Edge>{oth}
            { copyFrom(oth); }
 
        EItImpl_DepthFirst & operator=(const EItImpl_DepthFirst & oth) 
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(oth);
                copyFrom(oth); 
              } 
              return(*this); }
 
        EItImpl_DepthFirst(EItImpl_DepthFirst && oth):
                                elementa::patterns::Validatable{std::move(oth)},
                                elementa::base::MultItImpl<Edge>{std::move(oth)}
            { copyFrom(oth); }
 
        EItImpl_DepthFirst & operator=(EItImpl_DepthFirst && oth)
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(std::move(oth));
                copyFrom(oth); 
              }
              return(*this); }
 
        typename elementa::base::MultItImpl<Edge>::Ptr clone(void) const
            {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"");
                return(typename elementa::base::MultItImpl<Edge>::Ptr{
                        new EItImpl_DepthFirst{*this}}); }
 
        Edge & operator*(void);
        Edge * pointedData(void) const;
        EItImpl_DepthFirst & operator++(void); 
        std::string to_string(void) const override;
 
        size_edge forceBacktrack(void)
            { return(backtrack()); }
 
     private:
 
        using EStack = std::stack<eiterator>;
 
        Graph * gr_;
        viterator vparent_;
        eiterator ecurr_;
        EStack stack_;
 
        void checkDeref(void) const;
        void copyFrom(const EItImpl_DepthFirst & oth)
            { gr_ = oth.gr_; vparent_ = oth.vparent_; ecurr_ = oth.ecurr_; 
              stack_ = oth.stack_; }
        size_edge backtrack(void);
    };
 
 
    // Edge iteration for breadth-first search from a vertex.
    class EItImpl_BreadthFirst final: public elementa::base::MultItImpl<Edge>
                                      // indirectly derives from Validatable
    {
     public:
 
        EItImpl_BreadthFirst(Graph & gr, const viterator & vi, 
                             bool beginorend = true);
 
        EItImpl_BreadthFirst(const EItImpl_BreadthFirst & oth):
                                        elementa::patterns::Validatable{oth},
                                        elementa::base::MultItImpl<Edge>{oth}
            { copyFrom(oth); }
 
        EItImpl_BreadthFirst & operator=(const EItImpl_BreadthFirst &oth)
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(oth);
                copyFrom(oth); 
              }
              return(*this); }
 
        EItImpl_BreadthFirst(EItImpl_BreadthFirst && oth):
                                elementa::patterns::Validatable{std::move(oth)},
                                elementa::base::MultItImpl<Edge>{std::move(oth)}
            { copyFrom(oth); }
 
        EItImpl_BreadthFirst & operator=(EItImpl_BreadthFirst && oth)
            { if (this != &oth)
              {
                elementa::patterns::Validatable::operator=(oth);
                elementa::base::MultItImpl<Edge>::operator=(std::move(oth));
                copyFrom(oth); 
              }
              return(*this); }
 
        typename elementa::base::MultItImpl<Edge>::Ptr clone(void) const
            { return(typename elementa::base::MultItImpl<Edge>::Ptr{
                        new EItImpl_BreadthFirst{*this}}); }
 
        Edge & operator*(void);
        Edge * pointedData(void) const;
        EItImpl_BreadthFirst & operator++(void); 
        std::string to_string(void) const override;
 
     private:
 
        using EQueue = std::queue<eiterator>;
 
        Graph * gr_;
        viterator vparent_;
        eiterator ecurr_;
        EQueue queue_;
 
        void checkDeref(void) const;
        void copyFrom(const EItImpl_BreadthFirst & oth)
            { gr_ = oth.gr_; vparent_ = oth.vparent_; ecurr_ = oth.ecurr_; 
              queue_ = oth.queue_; }
    };
 
    eiterator edepthfirstbegin(const viterator &v) const;
    eiterator edepthfirstend(const viterator &v) const;
    eiterator ebreadthfirstbegin(const viterator &v) const;
    eiterator ebreadthfirstend(const viterator &v) const;
 
 
 static_assert( (!std::is_void<Vertex>::value) && (!std::is_void<Edge>::value),
                "Graph cannot work with void Vertex/Edge data" );
};
 
 
/* ***************************************************************************
 
    Template class: Szer_GraphCompactText
    
*******************************************************************************/
 
 
template <class Vertex, class Edge>
class Szer_GraphCompactText: 
                        public elementa::base::Serializer<Graph<Vertex,Edge>>
{
 public:
 
    using GraphType = Graph<Vertex,Edge>;
 
 
    Szer_GraphCompactText(elementa::base::Serializer<Vertex> & szerv,
                          elementa::base::Serializer<Edge> & szere):    
                                                            szerv_{&szerv},
                                                            szere_{&szere}
        {}
 
    void ser(elementa::base::OutSerCh & chout, const GraphType & graph);
 
    // No deserialization implemented.
 
 private:
 
    elementa::base::Serializer<Vertex> * szerv_{nullptr};
    elementa::base::Serializer<Edge> * szere_{nullptr}; 
 
static_assert((sizeof(size_vertex)<=8) && 
              (sizeof(size_edge)<=8),
              "Serialization requires 64 bits or less for size_vertex and "
              "size_edge");
};
 
 
 
/* ===========================================================================
 
        ========== IMPLEMENTATION OF TEMPLATES ==========
 
============================================================================= */
 
 
/* **********************************************************************
 
    Template subclass: Graph::VectorOfVIts
 
*************************************************************************/
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::VectorOfVIts::VectorOfVIts(const Graph & g)
{
    viterator v = g.vrangeAll().begin();
    while (v != g.vrangeAll().end()) 
    {
        this->push_back(v);
        ++v;
    }
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::VectorOfEIts
 
*************************************************************************/
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::VectorOfEIts::VectorOfEIts(const Graph & g)
{
    eiterator e = g.erangeAll().begin();
    while (e != g.erangeAll().end()) 
    {
        this->push_back(e);
        ++e;
    }
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::MapOfVItPos
 
*************************************************************************/
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::MapOfVItPos::MapOfVItPos(const Graph & g)
{
    size_t pos{0};
    viterator v = g.vrangeAll().begin();
    while (v != g.vrangeAll().end()) 
    {
        map_[v.implementation()->pointedData()] = pos;
        ++pos;
        ++v;
    }
}
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::MapOfVItPos::MapOfVItPos(const Graph::VectorOfVIts & m)
{
    for (size_t f = 0; f < m.size(); ++f)
        map_[m[f].implementation()->pointedData()] = f;
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::MapOfEItPos
 
*************************************************************************/
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::MapOfEItPos::MapOfEItPos(const Graph & g)
{
    size_t pos{0};
    eiterator e = g.erangeAll().begin();
    while (e != g.erangeAll().end()) 
    {
        map_[e.implementation()->pointedData()] = pos;
        ++pos;
        ++e;
    }
}
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::MapOfEItPos::MapOfEItPos(const Graph::VectorOfEIts & m)
{
    for (size_t f = 0; f < m.size(); ++f)
        map_[m[f].implementation()->pointedData()] = f;
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::VRange_Pred
 
*************************************************************************/
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::viterator 
Graph<Vertex,Edge>::VRange_Pred::begin(void) const
{
    return(viterator{
        typename viterator::ImplementationPtr{
            new VItImpl_Pred{*gr_,*(const_cast<VRange_Pred *>(this)->pred_),
                             *eit_}}});
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::viterator 
Graph<Vertex,Edge>::VRange_Pred::end(void) const
{static Pred nilpred = [](const Vertex & si)->bool {return(false);};
 
    eiterator nileit{gr_->erangeAll().end()};
    return(viterator{
        typename viterator::ImplementationPtr{
            new VItImpl_Pred{*gr_,nilpred,nileit,false}}}); 
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::ERange_Pred
 
*************************************************************************/
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::eiterator 
Graph<Vertex,Edge>::ERange_Pred::begin(void) const
{
    return(eiterator{
        typename eiterator::ImplementationPtr{
            new EItImpl_Pred{*gr_,*(const_cast<ERange_Pred *>(this)->pred_),
                             *eit_}}});
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::eiterator 
Graph<Vertex,Edge>::ERange_Pred::end(void) const
{
    eiterator nileit{gr_->erangeAll().end()};
    return(eiterator{
        typename eiterator::ImplementationPtr{
            new EItImpl_Pred{*gr_,nil_epred,nileit,false}}}); 
}
 
 
/* ***************************************************************************
 
    Template subclass: Graph::ERange_DepthFirst
    
*******************************************************************************/
 
template <class Vertex, class Edge>
size_edge Graph<Vertex,Edge>::ERange_DepthFirst::forceBacktrack(eiterator & eit)
{
    if (!eit.valid()) ELE_CODE_INVSTATE("Invalid edge iterator");
    if (eit.implementation() == nullptr)
        ELE_CODE_INVSTATE("Null edge iterator");
    return( dynamic_cast<EItImpl_DepthFirst &>(
                *(eit.implementation())).forceBacktrack() );
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::VItImpl_Pred
 
*************************************************************************/
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::VItImpl_Pred::checkDeref(void) const
{
    if ((isend_)||(eit_->isEnd()))
        ELE_CODE_INVSTATE("End iterator cannot be dereferenced");
}
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::VItImpl_Pred::iterateToNext(void)
{
    if ((!isend_)&&(!eit_->isEnd()))
    {
        bool finish{false};
        while (!finish)
        {
            Vertex & si = operator*();
            if (itpred_->operator()(si)) finish = true;
            else
            {
                ++(*eit_);
                if (eit_->isEnd()) finish = true;
            }
        }   
    }
}
 
template <class Vertex, class Edge>
std::string Graph<Vertex,Edge>::VItImpl_Pred::to_string(void) const 
{
    return(std::string{"vit_pred(gr:"} + 
           std::to_string(elementa::base::to_number(gr_)) + " " +
           elementa::base::MultItImpl<Vertex>::to_string() + 
           ", isend_ = " + elementa::base::kYesNoCString(isend_) + 
           ", with eit: " + eit_->to_string() + ")");
}
 
 
/* **********************************************************************
 
    Template subclass: Graph::EItImpl_Pred
 
*************************************************************************/
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::EItImpl_Pred::checkDeref(void) const
{
    if ((isend_)||(eit_->isEnd()))
        ELE_CODE_INVSTATE("End iterator cannot be dereferenced");
}
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::EItImpl_Pred::iterateToNext(void)
{
    if ((!isend_)&&(!eit_->isEnd()))
    {
        bool finish{false};
        while (!finish)
        {
            if (itpred_->operator()(*(*eit_))) finish = true;
            else
            {
                ++(*eit_);
                if (eit_->isEnd()) finish = true;
            }
        }   
    }
}
 
template <class Vertex, class Edge>
std::string Graph<Vertex,Edge>::EItImpl_Pred::to_string(void) const 
{
    return(std::string{"eit_pred(gr:"} + 
           std::to_string(elementa::base::to_number(gr_)) + " " +
           elementa::base::MultItImpl<Edge>::to_string() + 
           ", isend_ = " + elementa::base::kYesNoCString(isend_) + 
           ", with eit: " + eit_->to_string() + ")");
}
 
 
/* ***************************************************************************
 
    Template subclass: Graph::EItImpl_DepthFirst
    
*******************************************************************************/
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::EItImpl_DepthFirst::checkDeref(void) const
{
    if ((!elementa::patterns::Validatable::valid()) || (!ecurr_.valid()))
        ELE_CODE_INVSTATE("De-referencing invalid iterator");
    if (ecurr_.isEnd()) 
        ELE_CODE_INVSTATE("De-referencing end iterator");
}
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::EItImpl_DepthFirst::EItImpl_DepthFirst(
                            Graph & gr, 
                            const viterator & vi, 
                            bool beginorend):gr_{&gr},vparent_{vi},
                                             ecurr_{gr_->erangeAll().end()}
{
    if ((vparent_.valid()) && (!vparent_.isEnd()))
    {
        if (beginorend) ecurr_ = gr_->erangeLeaving(vparent_).begin();
        elementa::patterns::Validatable::setValid(); 
    }
    // else, it remains invalid
}
 
template <class Vertex, class Edge>
Edge & Graph<Vertex,Edge>::EItImpl_DepthFirst::operator*(void)
{
    checkDeref();
    return(*ecurr_);
}
 
template <class Vertex, class Edge>
Edge * Graph<Vertex,Edge>::EItImpl_DepthFirst::pointedData(void) const
{
    if (!elementa::patterns::Validatable::valid()) 
        ELE_CODE_INVSTATE("Invalid iterator does not point anywhere");
    if (ecurr_.isEnd()) return(nullptr);
    return(ecurr_.implementation()->pointedData());
}
 
template <class Vertex, class Edge>
size_edge Graph<Vertex,Edge>::EItImpl_DepthFirst::backtrack(void)
{
    size_edge bes{0};
    if ((elementa::patterns::Validatable::valid()) && (!ecurr_.isEnd()))
        while (1)
        {
            ++ecurr_; // next sibling of current edge, skipping current's depths
            ++bes;
            if (ecurr_.isEnd()) // no more siblings
            {
                if (stack_.empty()) // nothing to backtrack to
                {
                    ecurr_ = gr_->erangeAll().end();
                    break;
                }
                else // something to backtrack to
                {
                    auto & prevei = stack_.top(); // not invalid or end()
                    vparent_ = gr_->origin(prevei);
                    ecurr_ = prevei; 
                    stack_.pop();
                    // increment ecurr_ in the next iteration of this loop
                }
            }
            else break; // go on with the sibling in next step
        }
    return(bes);
}
 
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::EItImpl_DepthFirst & 
    Graph<Vertex,Edge>::EItImpl_DepthFirst::operator++(void)
{
    if ((elementa::patterns::Validatable::valid()) && (!ecurr_.isEnd()))
    {
        // look for depth first child of ecurr_
        auto vi = gr_->destination(ecurr_); // vi cannot be end() or invalid
        auto ei = gr_->erangeLeaving(vi).begin();
        if (ei.isEnd()) // no more depth
            backtrack();
        else
        {
            stack_.push(ecurr_);
            vparent_ = vi;
            ecurr_ = ei; // next child
        }
    } 
    return(*this);
}
 
template <class Vertex, class Edge>
std::string Graph<Vertex,Edge>::EItImpl_DepthFirst::to_string(void) const 
{
    return(std::string{"eit_depthfirst(gr:"} + 
           std::to_string(elementa::base::to_number(gr_)) + " " +
           elementa::base::MultItImpl<Edge>::to_string() + ")");
}
 
 
/* ***************************************************************************
 
    Template subclass: Graph::EItImpl_BreadthFirst
    
*******************************************************************************/
 
template <class Vertex, class Edge>
void Graph<Vertex,Edge>::EItImpl_BreadthFirst::checkDeref(void) const
{
    if ((!elementa::patterns::Validatable::valid()) || (!ecurr_.valid()))
        ELE_CODE_INVSTATE("De-referencing invalid iterator");
    if (ecurr_.isEnd()) 
        ELE_CODE_INVSTATE("De-referencing end iterator");
}
 
template <class Vertex, class Edge>
Graph<Vertex,Edge>::EItImpl_BreadthFirst::EItImpl_BreadthFirst(
                            Graph & gr, 
                            const viterator & vi, 
                            bool beginorend):gr_{&gr},vparent_{vi},
                                             ecurr_{gr_->erangeAll().end()}
{
    if ((vparent_.valid()) && (!vparent_.isEnd()))
    {
        if (beginorend) ecurr_ = gr_->erangeLeaving(vparent_).begin();
        elementa::patterns::Validatable::setValid(); 
    }
    // else, it remains invalid
}
 
template <class Vertex, class Edge>
Edge & Graph<Vertex,Edge>::EItImpl_BreadthFirst::operator*(void)
{
    checkDeref();
    return(*ecurr_);
}
 
template <class Vertex, class Edge>
Edge * Graph<Vertex,Edge>::EItImpl_BreadthFirst::pointedData(void) const
{
    if (!elementa::patterns::Validatable::valid()) 
        ELE_CODE_INVSTATE("Invalid iterator does not point anywhere");
    if (ecurr_.isEnd()) return(nullptr);
    return(ecurr_.implementation()->pointedData());
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::EItImpl_BreadthFirst & 
    Graph<Vertex,Edge>::EItImpl_BreadthFirst::operator++(void)
{
    if ((elementa::patterns::Validatable::valid()) && (!ecurr_.isEnd()))
    {
        // add first child of current edge to the queue, if any
        auto vi = gr_->destination(ecurr_);
        auto efirst = gr_->erangeLeaving(vi).begin();
        if (!efirst.isEnd()) queue_.push(efirst);
 
        // update current edge
        ++ecurr_;
        if (ecurr_.isEnd())
        {
            if (queue_.empty()) ecurr_ = gr_->erangeAll().end(); // finished
            else    
            {
                ecurr_ = queue_.front(); // cannot be end() or invalid
                queue_.pop();
            }
        }
    } 
    return(*this);
}
 
template <class Vertex, class Edge>
std::string Graph<Vertex,Edge>::EItImpl_BreadthFirst::to_string(void) const 
{
    return(std::string{"eit_breadthfirst(gr:"} + 
           std::to_string(elementa::base::to_number(gr_)) + " " +
           elementa::base::MultItImpl<Edge>::to_string() + ")");
}
 
 
/* ***************************************************************************
 
    Template class: Graph
    
*******************************************************************************/
 
// --------------- Private methods
 
template <class Vertex, class Edge>
typename Graph<Vertex, Edge>::eiterator
    Graph<Vertex,Edge>::edepthfirstbegin(const viterator &v) const
{ELE_CODE_TRACE_OFF;
 
    ELE_CODE_TRACE({},"v is " << v.to_string());
    if ((!v.valid()) || (v.isEnd()))
        ELE_CODE_INVARG("There is no begin depth-first edge of an invalid "
                        "vertex iterator");
    typename elementa::base::MultItImpl<Edge>::Ptr 
        impl{new EItImpl_DepthFirst{const_cast<Graph<Vertex,Edge> &>(*this),
                                    v,true}};
    eiterator res{impl};
    return(res);    
}
 
template <class Vertex, class Edge>
typename Graph<Vertex, Edge>::eiterator
    Graph<Vertex,Edge>::edepthfirstend(const viterator &v) const
{
    if ((!v.valid()) || (v.isEnd()))
        ELE_CODE_INVARG("There is no begin leaving edge of an invalid "
                        "vertex iterator");
    typename elementa::base::MultItImpl<Edge>::Ptr 
        impl{new EItImpl_DepthFirst{const_cast<Graph<Vertex,Edge> &>(*this),
                                    v,false}};
    eiterator res{impl};
    return(res);    
}
 
template <class Vertex, class Edge>
typename Graph<Vertex, Edge>::eiterator
    Graph<Vertex,Edge>::ebreadthfirstbegin(const viterator &v) const
{
    if ((!v.valid()) || (v.isEnd()))
        ELE_CODE_INVARG("There is no begin depth-first edge of an invalid "
                        "vertex iterator");
    typename elementa::base::MultItImpl<Edge>::Ptr 
        impl{new EItImpl_BreadthFirst{const_cast<Graph<Vertex,Edge> &>(*this),
                                      v,true}};
    eiterator res{impl};
    return(res);    
}
 
template <class Vertex, class Edge>
typename Graph<Vertex, Edge>::eiterator
    Graph<Vertex,Edge>::ebreadthfirstend(const viterator &v) const
{
    if ((!v.valid()) || (v.isEnd()))
        ELE_CODE_INVARG("There is no begin leaving edge of an invalid "
                        "vertex iterator");
    typename elementa::base::MultItImpl<Edge>::Ptr 
        impl{new EItImpl_BreadthFirst{const_cast<Graph<Vertex,Edge> &>(*this),
                                      v,false}};
    eiterator res{impl};
    return(res);    
}
 
 
// ------------- Public methods
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::eiterator 
    Graph<Vertex,Edge>::connected(const viterator & v0, 
                                  const viterator & v1,
                                  const EPred & epred) const
{
    auto eit = erangeLeaving(v0).begin();
    while (eit != erangeLeaving(v0).end())
    {
        if ((epred(*eit))&&(destination(eit) == v1)) break;
        ++eit;
    }
    return(eit);
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::viterator 
    Graph<Vertex,Edge>::find_vertex(const Vertex & v) const
{
    auto vit = vrangeAll().begin();
    while (vit != vrangeAll().end()) { if (*vit == v) break; ++vit; }
    return(vit);
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::eiterator 
    Graph<Vertex,Edge>::find_edge(const Edge & e) const
{
    auto eit = erangeAll().begin();
    while (eit != erangeAll().end()) { if (*eit == e) break; ++eit; }
    return(eit);
}
 
template <class Vertex, class Edge>
bool Graph<Vertex,Edge>::toLastChild(const eiterator & it, 
                                     const viterator & vit) const noexcept
{
    if ((!it.valid())||(!vit.valid())||(it.isEnd())||(vit.isEnd()))
        return(false);
    auto eit = erangeLeaving(vit).begin();
    if (eit.isEnd()) return(false);
    auto eit2 = eit;
    do
    {
        ++eit2;
        if (!eit2.isEnd()) eit = eit2;
    } while (!eit2.isEnd()); 
    // here, eit points to the last (not end) leaving edge iterator from vit
    bool res = (it == eit);
    return(res);
}
 
template <class Vertex, class Edge>
size_t Graph<Vertex,Edge>::vertexToPos(const viterator & vi) const
{
    size_t pos{0};
    viterator v = VRange_All{*this}.begin();
    while (v != VRange_All{*this}.end()) 
        if (v == vi) break;
        else 
        { 
            ++pos; 
            ++v; 
        }
    if (v != vi)
        ELE_CODE_INTERNALERR(           
            std::string{"Could not find index for iterator "} + vi.to_string());
    return(pos);
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::viterator 
    Graph<Vertex,Edge>::posToVertex(size_t pos) const
{
    if (pos >= size_vertices()) ELE_CODE_INVARG("Position out of range");
    viterator v = VRange_All{*this}.begin();
    while ((pos > 0) && (v != VRange_All{*this}.end()))
    {
        --pos;
        ++v;
    }
    return(v);
}
 
template <class Vertex, class Edge>
size_t Graph<Vertex,Edge>::edgeToPos(const eiterator & ei) const
{
    size_t pos{0};
    eiterator e = ERange_All{*this}.begin();
    while (e != ERange_All{*this}.end()) 
        if (e == ei) break;
        else 
        { 
            ++pos; 
            ++e; 
        }
    if (e != ei) ELE_CODE_INTERNALERR(
                    std::string{"Could not find index for iterator "} + 
                    ei.to_string());
    return(pos);
}
 
template <class Vertex, class Edge>
typename Graph<Vertex,Edge>::eiterator 
    Graph<Vertex,Edge>::posToEdge(size_t pos) const
{
    if (pos >= size_edges()) ELE_CODE_INVARG("Position out of range");
    eiterator e = ERange_All{*this}.begin();
    while ((pos > 0) && (e != ERange_All{*this}.end()))
    {
        --pos;
        ++e;
    }
    return(e);
}
 
 
/* ***************************************************************************
 
    Template class: Szer_GraphCompactText
    
*******************************************************************************/
 
template <class Vertex, class Edge>
void Szer_GraphCompactText<Vertex,Edge>::ser(
    elementa::base::OutSerCh & chout, const GraphType & graph) 
{ELE_CODE_TRACE_OFF;
 
    auto writenewline = [](elementa::base::OutSerCh & chout)
    {
        chout.put('\n');
        elementa::base::serch_isgood(chout,ELE_CODE_PLACE);
    };
 
    ELE_CODE_TRACE({},"Serializing number of vertices (" << 
                      graph.size_vertices() 
                      << ")");
    elementa::base::Szer_IntText szern{20};
    szern.ser(chout,graph.size_vertices());
    writenewline(chout);
 
    ELE_CODE_TRACE({},"Serializing number of edges (" << 
                      graph.size_edges() << ")");
    szern.ser(chout,graph.size_edges());
    writenewline(chout);
 
    ELE_CODE_TRACE({},"Serializing connections from edges (ebegin() == eend(): "
                      << (typename GraphType::ERange_All{graph}.begin() == 
                          typename GraphType::ERange_All{graph}.end()) 
                      << "; ebegin().valid: " <<
                      typename GraphType::ERange_All{graph}.begin().valid() << 
                      ", eend().valid: " 
                      << typename GraphType::ERange_All{graph}.end().valid()
                      << ")");
    auto eit = typename GraphType::ERange_All{graph}.begin();
    while (eit != typename GraphType::ERange_All{graph}.end())
    {
        ELE_CODE_TRACE({},"\tserializing eit: " << eit.to_string());
        typename GraphType::viterator v0,v1; 
        graph.connection(eit,v0,v1);
        ELE_CODE_TRACE({},"\t\tedge from " << v0.to_string() << " to " <<
                          v1.to_string());
 
        szern.ser(chout,graph.vertexToPos(v0));
        writenewline(chout);
 
        szern.ser(chout,graph.vertexToPos(v1));
        writenewline(chout);
 
        ++eit;
    }
 
    if (szerv_ != nullptr)
    {
        ELE_CODE_TRACE({},"Serializing vertex data...");
        for (auto vertex : graph.vrangeAll())
        {
            szerv_->ser(chout,vertex);
            writenewline(chout);
        }
    }
    
    if (szere_ != nullptr)
    {
        ELE_CODE_TRACE({},"Serializing edge data...");
        for (auto edge : graph.erangeAll())
        {
            szere_->ser(chout,edge);
            writenewline(chout);
        }
    }
 
/*
    First 20+1 chars: the number of vertices + '\n'
    Next 20+1 chars: the number of edges + '\n'
    For each edge:
        First 20+1 chars: index of origin vertex + '\n'
        Next 20+1 chars: index of destination vertex + '\n'
    For each vertex:
        Serialization of the vertex object + '\n'
    For each edge:
        Serialization of the edge object + '\n'
*/
}
 
 
 
 
} // end graphs namespace
 
} // end adts namespace
 
} // end elementa namespace
 
 
#endif