graph.h

/********************************************************************
 * Copyright (C) 2015 Liangliang Nan <liangliang.nan@gmail.com>
 * https://3d.bk.tudelft.nl/liangliang/
 *
 * This file is part of Easy3D. If it is useful in your research/work,
 * I would be grateful if you show your appreciation by citing it:
 * ------------------------------------------------------------------
 *      Liangliang Nan.
 *      Easy3D: a lightweight, easy-to-use, and efficient C++ library
 *      for processing and rendering 3D data.
 *      Journal of Open Source Software, 6(64), 3255, 2021.
 * ------------------------------------------------------------------
 *
 * Easy3D is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License Version 3
 * as published by the Free Software Foundation.
 *
 * Easy3D is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 ********************************************************************/
 
#ifndef EASY3D_CORE_GRAPH_H
#define EASY3D_CORE_GRAPH_H
 
 
#include <easy3d/core/model.h>
 
#include <vector>
 
#include <easy3d/core/types.h>
#include <easy3d/core/property.h>
 
 
namespace easy3d {
 
 
    class Graph : public virtual Model
    {
 
    public: //------------------------------------------------------ topology types
 
 
        class BaseHandle
        {
        public:
 
            explicit BaseHandle(int _idx = -1) : idx_(_idx) {}
 
            int idx() const { return idx_; }
 
            void reset() { idx_ = -1; }
 
            bool is_valid() const { return idx_ != -1; }
 
            bool operator==(const BaseHandle& _rhs) const {
                return idx_ == _rhs.idx_;
            }
 
            bool operator!=(const BaseHandle& _rhs) const {
                return idx_ != _rhs.idx_;
            }
 
            bool operator<(const BaseHandle& _rhs) const {
                return idx_ < _rhs.idx_;
            }
 
            struct Hash {
                std::size_t operator()(const BaseHandle& h) const { return h.idx(); }
            };
 
        private:
            friend class Graph;
            int idx_;
        };
 
 
        struct Vertex : public BaseHandle
        {
            explicit Vertex(int _idx = -1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'v' << idx(); }
        };
 
        struct Edge : public BaseHandle
        {
            explicit Edge(int _idx = -1) : BaseHandle(_idx) {}
        };
 
 
    public: //-------------------------------------------------- connectivity types
 
        struct VertexConnectivity
        {
            std::vector<Edge>  edges_;
        };
 
 
        struct EdgeConnectivity
        {
            Vertex source_;
            Vertex target_;
        };
 
 
    public: //------------------------------------------------------ property types
 
        template <class T> class VertexProperty : public Property<T>
        {
        public:
 
            explicit VertexProperty() = default;
            explicit VertexProperty(Property<T> p) : Property<T>(p) {}
 
            typename Property<T>::reference operator[](Vertex v)
            {
                return Property<T>::operator[](v.idx());
            }
 
            typename Property<T>::const_reference operator[](Vertex v) const
            {
                return Property<T>::operator[](v.idx());
            }
        };
 
 
        template <class T> class EdgeProperty : public Property<T>
        {
        public:
 
            explicit EdgeProperty() = default;
            explicit EdgeProperty(Property<T> p) : Property<T>(p) {}
 
            typename Property<T>::reference operator[](Edge e)
            {
                return Property<T>::operator[](e.idx());
            }
 
            typename Property<T>::const_reference operator[](Edge e) const
            {
                return Property<T>::operator[](e.idx());
            }
        };
 
        template <class T> class ModelProperty : public Property<T>
        {
        public:
 
            explicit ModelProperty() = default;
            explicit ModelProperty(Property<T> p) : Property<T>(p) {}
 
            typename Property<T>::reference operator[](size_t idx)
            {
                return Property<T>::operator[](idx);
            }
 
            typename Property<T>::const_reference operator[](size_t idx) const
            {
                return Property<T>::operator[](idx);
            }
        };
 
 
 
    public: //------------------------------------------------------ iterator types
 
        class VertexIterator
        {
        public:
 
            explicit VertexIterator(Vertex v = Vertex(), const Graph* g = nullptr) : hnd_(v), graph_(g)
            {
                if (graph_ && graph_->has_garbage()) while (graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) ++hnd_.idx_;
            }
 
            Vertex operator*()  const { return  hnd_; }
 
            bool operator==(const VertexIterator& rhs) const
            {
                return (hnd_ == rhs.hnd_);
            }
 
            bool operator!=(const VertexIterator& rhs) const
            {
                return !operator==(rhs);
            }
 
            VertexIterator& operator++()
            {
                ++hnd_.idx_;
                assert(graph_);
                while (graph_->has_garbage() && graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }
 
            VertexIterator& operator--()
            {
                --hnd_.idx_;
                assert(graph_);
                while (graph_->has_garbage() && graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Vertex  hnd_;
            const Graph* graph_;
        };
 
 
        class EdgeIterator
        {
        public:
 
            explicit EdgeIterator(Edge e = Edge(), const Graph* g = nullptr) : hnd_(e), graph_(g)
            {
                if (graph_ && graph_->has_garbage()) while (graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) ++hnd_.idx_;
            }
 
            Edge operator*()  const { return  hnd_; }
 
            bool operator==(const EdgeIterator& rhs) const
            {
                return (hnd_ == rhs.hnd_);
            }
 
            bool operator!=(const EdgeIterator& rhs) const
            {
                return !operator==(rhs);
            }
 
            EdgeIterator& operator++()
            {
                ++hnd_.idx_;
                assert(graph_);
                while (graph_->has_garbage() && graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }
 
            EdgeIterator& operator--()
            {
                --hnd_.idx_;
                assert(graph_);
                while (graph_->has_garbage() && graph_->is_valid(hnd_) && graph_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Edge  hnd_;
            const Graph* graph_;
        };
 
 
    public: //-------------------------- containers for C++11 range-based for loops
 
        class VertexContainer
        {
        public:
            VertexContainer(VertexIterator _begin, VertexIterator _end) : begin_(_begin), end_(_end) {}
            VertexIterator begin() const { return begin_; }
            VertexIterator end()   const { return end_; }
        private:
            VertexIterator begin_, end_;
        };
 
        class EdgeContainer
        {
        public:
            EdgeContainer(EdgeIterator _begin, EdgeIterator _end) : begin_(_begin), end_(_end) {}
            EdgeIterator begin() const { return begin_; }
            EdgeIterator end()   const { return end_; }
        private:
            EdgeIterator begin_, end_;
        };
 
 
    public: //---------------------------------------------------- circulator types
 
 
        class EdgeAroundVertexCirculator
        {
        public:
 
            explicit EdgeAroundVertexCirculator(const Graph* g, Vertex v=Vertex())
                : graph_(g), vertex_(v), finished_(false)
            {
                iterator_ = graph_->vconn_[vertex_].edges_.begin();
                end_ = graph_->vconn_[vertex_].edges_.end();
            }
 
            bool operator==(const EdgeAroundVertexCirculator& rhs) const {
                assert(graph_);
                return ((graph_ == rhs.graph_) && (vertex_ == rhs.vertex_) && (iterator_ == rhs.iterator_))
                    || (finished_); // to behave like a circulator
            }
 
            bool operator!=(const EdgeAroundVertexCirculator& rhs) const {
                return !operator==(rhs);
            }
 
            EdgeAroundVertexCirculator& operator++() {
                assert(graph_);
                ++iterator_;
                if (iterator_ == end_) {    // to behave like a circulator
                    iterator_ = graph_->vconn_[vertex_].edges_.begin();
                    finished_ = true;
                }
                return *this;
            }
 
            EdgeAroundVertexCirculator& operator--()
            {
                assert(graph_);
                --iterator_;
                return *this;
            }
 
            Edge operator*() const { 
                assert(graph_);
                if (iterator_ != end_)  return *iterator_;
                else                    return Edge();
            }
 
            operator bool() const { return !graph_->vconn_[vertex_].edges_.empty(); }
 
            Vertex vertex() const { return vertex_; }
 
            // helper for C++11 range-based for-loops
            EdgeAroundVertexCirculator& begin() { iterator_ = graph_->vconn_[vertex_].edges_.begin(); return *this; }
            // helper for C++11 range-based for-loops
            EdgeAroundVertexCirculator& end() { iterator_ = end_; return *this; }
 
        private:
            const Graph*  graph_;
            const Vertex  vertex_;
            std::vector<Edge>::const_iterator iterator_;
            // helper for C++11 range-based for-loops
            std::vector<Edge>::const_iterator end_;
            bool finished_; // for the circulator behavior
        };
 
 
 
        class VertexAroundVertexCirculator
        {
        public:
 
            explicit VertexAroundVertexCirculator(const Graph* g, Vertex v = Vertex())
                : graph_(g), vertex_(v), finished_(false)
            {
                iterator_ = graph_->vconn_[vertex_].edges_.begin();
                end_ = graph_->vconn_[vertex_].edges_.end();
            }
 
            bool operator==(const VertexAroundVertexCirculator& rhs) const {
                assert(graph_);
                return ((graph_ == rhs.graph_) && (vertex_ == rhs.vertex_) && (iterator_ == rhs.iterator_))
                    || (finished_); // to behave like a circulator
            }
 
            bool operator!=(const VertexAroundVertexCirculator& rhs) const {
                return !operator==(rhs);
            }
 
            VertexAroundVertexCirculator& operator++() {
                assert(graph_);
                ++iterator_;
                if (iterator_ == end_) {    // to behave like a circulator
                    iterator_ = graph_->vconn_[vertex_].edges_.begin();
                    finished_ = true;
                }
                return *this;
            }
 
            VertexAroundVertexCirculator& operator--()
            {
                assert(graph_);
                --iterator_;
                return *this;
            }
 
            Vertex operator*() const {
                assert(graph_);
                if (iterator_ != end_) {
                    Vertex v = graph_->vertex(*iterator_, 1);
                    if (v != vertex_)   return v;
                    else                return graph_->vertex(*iterator_, 0);
                }
                return Vertex();
            }
 
            operator bool() const { return !graph_->vconn_[vertex_].edges_.empty(); }
 
            Vertex vertex() const { return vertex_; }
 
            // helper for C++11 range-based for-loops
            VertexAroundVertexCirculator& begin() {
                iterator_ = graph_->vconn_[vertex_].edges_.begin();
                return *this;
            }
            // helper for C++11 range-based for-loops
            VertexAroundVertexCirculator& end() {
                iterator_ = end_;
                return *this;
            }
 
        private:
            const Graph*  graph_;
            const Vertex  vertex_;
            std::vector<Edge>::const_iterator iterator_;
            // helper for C++11 range-based for-loops
            std::vector<Edge>::const_iterator end_;
            bool finished_; // for the circulator behavior
        };
 
 
 
    public: //-------------------------------------------- constructor / destructor
 
 
 
        Graph();
 
        ~Graph() override = default;
 
        Graph(const Graph& rhs) { operator=(rhs); }
 
        Graph& operator=(const Graph& rhs);
 
        Graph& assign(const Graph& rhs);
 
 
    public: //----------------------------------------------- add new vertex / face
 
 
 
        Vertex add_vertex(const vec3& p);
 
        Edge add_edge(const Vertex& v1, const Vertex& v2);
 
    public: //--------------------------------------------------- memory management
 
 
 
        unsigned int vertices_size() const { return (unsigned int)vprops_.size(); }
        unsigned int edges_size() const { return (unsigned int)eprops_.size(); }
 
        unsigned int n_vertices() const { return vertices_size() - deleted_vertices_; }
        unsigned int n_edges() const { return edges_size() - deleted_edges_; }
 
        void clear();
 
        void reserve(unsigned int nvertices, unsigned int nedges);
 
        void resize(unsigned int nv, unsigned int ne) {
            vprops_.resize(nv);
            eprops_.resize(ne);
        }
 
        bool has_garbage() const { return garbage_; }
 
        void collect_garbage();
 
 
        bool is_deleted(Vertex v) const
        {
            return vdeleted_[v];
        }
        bool is_deleted(Edge e) const
        {
            return edeleted_[e];
        }
 
        bool is_valid(Vertex v) const
        {
            return (0 <= v.idx()) && (v.idx() < (int)vertices_size());
        }
        bool is_valid(Edge e) const
        {
            return (0 <= e.idx()) && (e.idx() < (int)edges_size());
        }
 
 
    public: //---------------------------------------------- low-level connectivity
 
 
 
        bool is_isolated(Vertex v) const
        {
            return vconn_[v].edges_.empty();
        }
 
        Vertex vertex(Edge e, unsigned int i) const
        {
            assert(i<=1);
            if (i == 0)
                return econn_[e].source_;
            else
                return econn_[e].target_;
        }
 
        Vertex source(Edge e) const { return econn_[e].source_; }
 
        Vertex target(Edge e) const { return econn_[e].target_; }
 
    public: //--------------------------------------------------- property handling
 
 
 
        template <class T> VertexProperty<T> add_vertex_property(const std::string& name, const T t = T())
        {
            return VertexProperty<T>(vprops_.add<T>(name, t));
        }
        template <class T> EdgeProperty<T> add_edge_property(const std::string& name, const T t = T())
        {
            return EdgeProperty<T>(eprops_.add<T>(name, t));
        }
        template <class T> ModelProperty<T> add_model_property(const std::string& name, const T t = T())
        {
            return ModelProperty<T>(mprops_.add<T>(name, t));
        }
 
 
        template <class T> VertexProperty<T> get_vertex_property(const std::string& name) const
        {
            return VertexProperty<T>(vprops_.get<T>(name));
        }
        template <class T> EdgeProperty<T> get_edge_property(const std::string& name) const
        {
            return EdgeProperty<T>(eprops_.get<T>(name));
        }
        template <class T> ModelProperty<T> get_model_property(const std::string& name) const
        {
            return ModelProperty<T>(mprops_.get<T>(name));
        }
 
 
        template <class T> VertexProperty<T> vertex_property(const std::string& name, const T t = T())
        {
            return VertexProperty<T>(vprops_.get_or_add<T>(name, t));
        }
        template <class T> EdgeProperty<T> edge_property(const std::string& name, const T t = T())
        {
            return EdgeProperty<T>(eprops_.get_or_add<T>(name, t));
        }
 
        template <class T> ModelProperty<T> model_property(const std::string& name, const T t = T())
        {
            return ModelProperty<T>(mprops_.get_or_add<T>(name, t));
        }
 
        template<class T>
        bool remove_vertex_property(VertexProperty<T> &p) { return vprops_.remove(p); }
 
        bool remove_vertex_property(const std::string &n) { return vprops_.remove(n); }
 
        template<class T>
        bool remove_edge_property(EdgeProperty<T> &p) { return eprops_.remove(p); }
 
        bool remove_edge_property(const std::string &n) { return eprops_.remove(n); }
 
        template<class T>
        bool remove_model_property(ModelProperty<T> &p) { return mprops_.remove(p); }
 
        bool remove_model_property(const std::string &n) { return mprops_.remove(n); }
 
        bool rename_vertex_property(const std::string &old_name, const std::string &new_name) {
            return vprops_.rename(old_name, new_name);
        }
 
        bool rename_edge_property(const std::string &old_name, const std::string &new_name) {
            return eprops_.rename(old_name, new_name);
        }
 
        bool rename_model_property(const std::string &old_name, const std::string &new_name) {
            return mprops_.rename(old_name, new_name);
        }
 
        const std::type_info& get_vertex_property_type(const std::string& name) const
        {
            return vprops_.get_type(name);
        }
        const std::type_info& get_edge_property_type(const std::string& name) const
        {
            return eprops_.get_type(name);
        }
        const std::type_info& get_model_property_type(const std::string& name) const
        {
            return mprops_.get_type(name);
        }
 
 
        std::vector<std::string> vertex_properties() const
        {
            return vprops_.properties();
        }
        std::vector<std::string> edge_properties() const
        {
            return eprops_.properties();
        }
        std::vector<std::string> model_properties() const
        {
            return mprops_.properties();
        }
 
        void property_stats(std::ostream& output) const override;
 
 
 
    public: //--------------------------------------------- iterators & circulators
 
 
 
        VertexIterator vertices_begin() const
        {
            return VertexIterator(Vertex(0), this);
        }
 
        VertexIterator vertices_end() const
        {
            return VertexIterator(Vertex(static_cast<int>(vertices_size())), this);
        }
 
        VertexContainer vertices() const
        {
            return VertexContainer(vertices_begin(), vertices_end());
        }
 
        EdgeIterator edges_begin() const
        {
            return EdgeIterator(Edge(0), this);
        }
 
        EdgeIterator edges_end() const
        {
            return EdgeIterator(Edge(static_cast<int>(edges_size())), this);
        }
 
        EdgeContainer edges() const
        {
            return EdgeContainer(edges_begin(), edges_end());
        }
 
        VertexAroundVertexCirculator vertices(Vertex v) const
        {
            return VertexAroundVertexCirculator(this, v);
        }
 
        EdgeAroundVertexCirculator edges(Vertex v) const
        {
            return EdgeAroundVertexCirculator(this, v);
        }
 
 
    public: //--------------------------------------------- higher-level operations
 
 
 
 
        unsigned int valence(Vertex v) const;
 
        Edge find_edge(Vertex a, Vertex b) const;
 
        void delete_vertex(Vertex v);
 
        void delete_edge(Edge e);
 
 
    public: //------------------------------------------ geometry-related functions
 
 
 
        const vec3& position(Vertex v) const { return vpoint_[v]; }
 
        vec3& position(Vertex v) { return vpoint_[v]; }
 
        const std::vector<vec3>& points() const override { return vpoint_.vector(); }
 
        std::vector<vec3>& points() override { return vpoint_.vector(); }
 
        float edge_length(Edge e) const;
 
 
 
    private: //---------------------------------------------- allocate new elements
 
        Vertex new_vertex()
        {
            vprops_.push_back();
            return Vertex(static_cast<int>(vertices_size() - 1));
        }
 
        Edge new_edge()
        {
            eprops_.push_back();
            return Edge(static_cast<int>(edges_size() - 1));
        }
 
 
    private: //------------------------------------------------------- private data
 
        PropertyContainer vprops_;
        PropertyContainer eprops_;
        PropertyContainer mprops_;
 
        VertexProperty<VertexConnectivity>      vconn_;
        EdgeProperty<EdgeConnectivity>          econn_;
 
        VertexProperty<bool>  vdeleted_;
        EdgeProperty<bool>    edeleted_;
 
        VertexProperty<vec3>  vpoint_;
 
        unsigned int deleted_vertices_;
        unsigned int deleted_edges_;
        bool garbage_;
    };
 
 
    //------------------------------------------------------------ output operators
 
 
    inline std::ostream& operator<<(std::ostream& os, Graph::Vertex v)
    {
        return (os << 'v' << v.idx());
    }
 
    inline std::ostream& operator<<(std::ostream& os, Graph::Edge e)
    {
        return (os << 'e' << e.idx());
    }
 
} // namespace easy3d
 
#endif // EASY3D_CORE_GRAPH_H