Graph.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_Graph_H
#define Sawyer_Graph_H

#include <Sawyer/Assert.h>
#include <Sawyer/DefaultAllocator.h>
#include <Sawyer/Exception.h>
#include <Sawyer/IndexedList.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>                            // for Sawyer::Nothing
#include <Sawyer/Sawyer.h>
#include <boost/range/iterator_range.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/unordered_map.hpp>
#include <ostream>
#if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
#include <iomanip>
#endif

namespace Sawyer {
namespace Container {

// Special vertex and edge key types.

template<class VertexValue>
class GraphVertexNoKey {
public:
    GraphVertexNoKey() {}
    explicit GraphVertexNoKey(const VertexValue&) {}
};

template<class EdgeValue>
class GraphEdgeNoKey {
public:
    GraphEdgeNoKey() {}
    explicit GraphEdgeNoKey(const EdgeValue&) {}
};

// Special vertex and edge indexing types.

template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
class GraphVoidIndex {
public:
    void clear() {}

    void insert(const VertexOrEdgeKey&, const VertexOrEdgeConstIterator&) {}

    void erase(const VertexOrEdgeKey&) {}

    Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey&) const {
        return Nothing();
    }
};

template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
class GraphBimapIndex {
    Map<VertexOrEdgeKey, VertexOrEdgeConstIterator> map_;
public:
    void clear() {
        map_.clear();
    }

    void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
        map_.insert(key, iter);                         // Unlike std::map, Sawyer's "insert" always inserts
    }

    void erase(const VertexOrEdgeKey &key) {
        map_.erase(key);
    }

    Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
        return map_.getOptional(key);
    }
};

template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
class GraphHashIndex {
    typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator> Map;
    Map map_;
public:
    void clear() {
        map_.clear();
    }

    void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
        map_[key] = iter;
    }

    void erase(const VertexOrEdgeKey &key) {
        map_.erase(key);
    }

    Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
        typename Map::const_iterator found = map_.find(key);
        if (found == map_.end())
            return Nothing();
        return found->second;
    }
};

template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
struct GraphIndexTraits {
    typedef GraphBimapIndex<VertexOrEdgeKey, VertexOrEdgeConstIterator> Index;
};

// Partial specialization for when there is no vertex index
template<class VertexValue, class ConstVertexIterator>
struct GraphIndexTraits<GraphVertexNoKey<VertexValue>, ConstVertexIterator> {
    typedef GraphVoidIndex<GraphVertexNoKey<VertexValue>, ConstVertexIterator> Index;
};

// Partial specialization for when there is no edge index.
template<class EdgeValue, class ConstEdgeIterator>
struct GraphIndexTraits<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> {
    typedef GraphVoidIndex<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> Index;
};

// A #define so users that don't understand C++ templates can still get by. See GraphIndexTraits doc for details.
// Must be used at global scope.
#define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE)                                                                   \
    namespace Sawyer {                                                                                                         \
        namespace Container {                                                                                                  \
            template<class VertexOrEdgeConstIterator>                                                                          \
            struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> {                                                     \
                typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index;                                                           \
            };                                                                                                                 \
        }                                                                                                                      \
    }

#define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE)                                                                   \
    namespace Sawyer {                                                                                                         \
        namespace Container {                                                                                                  \
            template<class VertexOrEdgeConstIterator>                                                                          \
            struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> {                                                     \
                typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index;                                                 \
            };                                                                                                                 \
        }                                                                                                                      \
    }

    
// Graph traits

template<class G>
struct GraphTraits {
    typedef typename G::EdgeIterator EdgeIterator;

    typedef typename G::EdgeValueIterator EdgeValueIterator;

    typedef typename G::VertexIterator VertexIterator;

    typedef typename G::VertexValueIterator VertexValueIterator;

    typedef typename G::Vertex Vertex;

    typedef typename G::Edge Edge;

    typedef typename G::VertexValue VertexValue;

    typedef typename G::EdgeValue EdgeValue;
};

// GraphTraits specialization for const graphs.
template<class G>
struct GraphTraits<const G> {
    typedef typename G::ConstEdgeIterator EdgeIterator;
    typedef typename G::ConstEdgeValueIterator EdgeValueIterator;
    typedef typename G::ConstVertexIterator VertexIterator;
    typedef typename G::ConstVertexValueIterator VertexValueIterator;
    typedef const typename G::Vertex Vertex;
    typedef const typename G::Edge Edge;
    typedef const typename G::VertexValue VertexValue;
    typedef const typename G::EdgeValue EdgeValue;
};

template<class V = Nothing, class E = Nothing,
         class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>,
         class Alloc = DefaultAllocator>
class Graph {
public:
    typedef V VertexValue;                              
    typedef E EdgeValue;                                
    typedef VKey VertexKey;                             
    typedef EKey EdgeKey;                               
    typedef Alloc Allocator;                            
    class Vertex;                                       
    class Edge;                                         
private:
    enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
    typedef IndexedList<Edge, Allocator> EdgeList;
    typedef IndexedList<Vertex, Allocator> VertexList;

    template<class T>
    class VirtualList {
        VirtualList *next_[N_PHASES];
        VirtualList *prev_[N_PHASES];
        T *node_;
    public:
        VirtualList() {
            reset(NULL);
        }

        void reset(T* node) {
            node_ = node;
            for (size_t i=0; i<N_PHASES; ++i)
                next_[i] = prev_[i] = this;
        }

        bool isHead() const {
            return node_ == NULL;
        }

        bool isSingleton(EdgePhase phase) const {
            ASSERT_this();
            ASSERT_require(phase < N_PHASES);
            ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
            return next_[phase]==this;
        }

        bool isEmpty(EdgePhase phase) const {
            ASSERT_this();
            ASSERT_require(isHead());
            ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
            return next_[phase]==this;
        }

        void insert(EdgePhase phase, VirtualList *newNode) { // insert newNode before this
            ASSERT_this();
            ASSERT_require(phase < N_PHASES);
            ASSERT_not_null(newNode);
            ASSERT_forbid(newNode->isHead());
            ASSERT_require(newNode->isSingleton(phase)); // cannot be part of another sublist already
            prev_[phase]->next_[phase] = newNode;
            newNode->prev_[phase] = prev_[phase];
            prev_[phase] = newNode;
            newNode->next_[phase] = this;
        }

        void remove(EdgePhase phase) {                  // Remove this node from the list
            ASSERT_this();
            ASSERT_require(phase < N_PHASES);
            ASSERT_forbid(isHead());
            prev_[phase]->next_[phase] = next_[phase];
            next_[phase]->prev_[phase] = prev_[phase];
            next_[phase] = prev_[phase] = this;
        }

        VirtualList& next(EdgePhase phase) { return *next_[phase]; }
        const VirtualList& next(EdgePhase phase) const { return *next_[phase]; }
        VirtualList& prev(EdgePhase phase) { return *prev_[phase]; }
        const VirtualList& prev(EdgePhase phase) const { return *prev_[phase]; }

        T& dereference() {                              // Return the Edge to which this VirtualList node belongs
            ASSERT_this();
            ASSERT_forbid(isHead());                    // list head contains no user-data
            return *(T*)this;                           // depends on VirtualList being at the beginning of Edge
        }

        const T& dereference() const {
            ASSERT_this();
            ASSERT_forbid(isHead());
            return *(const T*)this;
        }

#if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
        void dump(EdgePhase phase, std::ostream &o) const {
            const VirtualList *cur = this;
            o <<"  " <<std::setw(18) <<"Node"
              <<"\t" <<std::setw(18) <<"This"
              <<"\t" <<std::setw(18) <<"Next"
              <<"\t" <<std::setw(18) <<"Prev\n";
            do {
                o <<"  " <<std::setw(18) <<node_
                  <<"\t" <<std::setw(18) <<cur
                  <<"\t" <<std::setw(18) <<cur->next_[phase]
                  <<"\t" <<std::setw(18) <<cur->prev_[phase] <<"\n";
                cur = cur->next_[phase];
            } while (cur!=this && cur->next_[phase]!=cur);
        }
#endif
    };

    //                                  Iterators
public:                                                 // public only for the sake of doxygen
    template<class Derived, class Value, class Node, class BaseIter, class VList>
    class EdgeBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
        EdgePhase phase_;                               // IN_EDGES, OUT_EDGES or N_PHASES (graph edges)
        BaseIter iter_;                                 // EdgeList::NodeIterator or EdgeList::ConstNodeIterator
        VList *vlist_;                                  // (const) VirtualList<Edge> when phase_ is IN_EDGES or OUT_EDGES
    protected:
        friend class Graph;
        EdgeBaseIterator() {}
        EdgeBaseIterator(const EdgeBaseIterator &other): phase_(other.phase_), iter_(other.iter_), vlist_(other.vlist_) {}
        EdgeBaseIterator(const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
        EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
        template<class BaseIter2> EdgeBaseIterator(EdgePhase phase, const BaseIter2 &iter, VList *vlist)
            : phase_(phase), iter_(iter), vlist_(vlist) {}

        Node& dereference() const {
            return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
        }

    private:
        Derived* derived() { return static_cast<Derived*>(this); }
        const Derived* derived() const { return static_cast<const Derived*>(this); }

    public:
        Derived& operator=(const Derived &other) {
            phase_ = other.phase_;
            iter_ = other.iter_;
            vlist_ = other.vlist_;
            return *derived();
        }

        Derived& operator++() {
            if (N_PHASES==phase_) {
                ++iter_;
            } else {
                vlist_ = &vlist_->next(phase_);
            }
            return *derived();
        }
        Derived operator++(int) {
            Derived old = *derived();
            ++*this;
            return old;
        }
        Derived& operator--() {
            if (N_PHASES==phase_) {
                --iter_;
            } else {
                vlist_ = &vlist_->prev(phase_);
            }
            return *derived();
        }
        Derived operator--(int) {
            Derived old = *derived();
            --*this;
            return old;
        }
        template<class OtherIter>
        bool operator==(const OtherIter &other) const {
            Node *a = NULL;
            if (N_PHASES==phase_) {
                a = iter_.isAtEnd() ? NULL : &iter_->value();
            } else {
                a = vlist_->isHead() ? NULL : &vlist_->dereference();
            }
            Node *b = NULL;
            if (N_PHASES==other.phase_) {
                b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
            } else {
                b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
            }
            return a == b;
        }
        template<class OtherIter>
        bool operator!=(const OtherIter &other) const {
            return !(*this==other);
        }
        bool operator<(const EdgeBaseIterator &other) const {
            Node *a = NULL;
            if (N_PHASES==phase_) {
                a = iter_.isAtEnd() ? NULL : &iter_->value();
            } else {
                a = vlist_->isHead() ? NULL : &vlist_->dereference();
            }
            Node *b = NULL;
            if (N_PHASES==other.phase_) {
                b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
            } else {
                b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
            }
            return a < b;
        }
    };

    template<class Derived, class Value, class Node, class BaseIter>
    class VertexBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
        BaseIter base_;                                 // VertexList::NodeIterator or VertexList::ConstNodeIterator
    protected:
        friend class Graph;
        VertexBaseIterator() {}
        VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
        VertexBaseIterator(const BaseIter &base): base_(base) {}
        Node& dereference() const { return base_->value(); }
    public:
        Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }

        Derived& operator++() { ++base_; return *derived(); }
        Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
        Derived& operator--() { --base_; return *derived(); }
        Derived operator--(int) { Derived old=*derived(); --*this; return old; }
        template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
        template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
        bool operator<(const VertexBaseIterator &other) const { return base_ < other.base_; }

    private:
        Derived* derived() { return static_cast<Derived*>(this); }
        const Derived* derived() const { return static_cast<const Derived*>(this); }
    };

public:
    class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
                                                VirtualList<Edge> > {
        typedef                EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
                                                VirtualList<Edge> > Super;
    public:
        typedef Edge& Reference;
        typedef Edge* Pointer;
        EdgeIterator() {}
        EdgeIterator(const EdgeIterator &other): Super(other) {}
        Edge& operator*() const { return this->dereference(); }
        Edge* operator->() const { return &this->dereference(); }
    private:
        friend class Graph;
        EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
        EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
    };

    class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
                                                     typename EdgeList::ConstNodeIterator,
                                                     const VirtualList<Edge> > {
        typedef                     EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
                                                     typename EdgeList::ConstNodeIterator,
                                                     const VirtualList<Edge> > Super;
    public:
        typedef const Edge& Reference;
        typedef const Edge* Pointer;
        ConstEdgeIterator() {}
        ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
        ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
        const Edge& operator*() const { return this->dereference(); }
        const Edge* operator->() const { return &this->dereference(); }
    private:
        friend class Graph;
        ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
        ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
    };
    class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
                                                     VirtualList<Edge> > {
        typedef                     EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
                                                     VirtualList<Edge> > Super;
    public:
        typedef EdgeValue& Reference;
        typedef EdgeValue* Pointer;
        EdgeValueIterator() {}
        EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
        EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
        EdgeValue& operator*() const { return this->dereference().value(); }
        EdgeValue* operator->() const { return &this->dereference().value(); }
    private:
        friend class Graph;
        EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
        EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
    };

    class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
                                                          typename EdgeList::ConstNodeIterator,
                                                          const VirtualList<Edge> > {
        typedef                          EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
                                                          typename EdgeList::ConstNodeIterator,
                                                          const VirtualList<Edge> > Super;
    public:
        typedef const EdgeValue& Reference;
        typedef const EdgeValue* Pointer;
        ConstEdgeValueIterator() {}
        ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
        ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
        ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
        ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
        const EdgeValue& operator*() const { return this->dereference().value(); }
        const EdgeValue* operator->() const { return &this->dereference().value(); }
    private:
        friend class Graph;
        ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
        ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
    };

    class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
                                                    typename VertexList::NodeIterator> {
        typedef                  VertexBaseIterator<VertexIterator, Vertex, Vertex,
                                                    typename VertexList::NodeIterator> Super;
    public:
        typedef Vertex& Reference;
        typedef Vertex* Pointer;
        VertexIterator() {}
        VertexIterator(const VertexIterator &other): Super(other) {}
        Vertex& operator*() const { return this->dereference(); }
        Vertex* operator->() const { return &this->dereference(); }
    private:
        friend class Graph;
        VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
    };

    class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
                                                         typename VertexList::ConstNodeIterator> {
        typedef                       VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
                                                         typename VertexList::ConstNodeIterator> Super;
    public:
        typedef const Vertex& Reference;
        typedef const Vertex* Pointer;
        ConstVertexIterator() {}
        ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
        ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
        const Vertex& operator*() const { return this->dereference(); }
        const Vertex* operator->() const { return &this->dereference(); }
    private:
        friend class Graph;
        ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
    };
        
    class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
                                                         typename VertexList::NodeIterator> {
        typedef                       VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
                                                         typename VertexList::NodeIterator> Super;
    public:
        typedef VertexValue& Reference;
        typedef VertexValue* Pointer;
        VertexValueIterator() {}
        VertexValueIterator(const VertexValueIterator &other): Super(other) {}
        VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
        VertexValue& operator*() const { return this->dereference().value(); }
        VertexValue* operator->() const { return &this->dereference().value(); }
    private:
        friend class Graph;
        VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
    };

    class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
                                                              typename VertexList::ConstNodeIterator> {
        typedef                            VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
                                                              typename VertexList::ConstNodeIterator> Super;
    public:
        typedef const VertexValue& Reference;
        typedef const VertexValue* Pointer;
        ConstVertexValueIterator() {}
        ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
        ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
        ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
        ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
        const VertexValue& operator*() const { return this->dereference().value(); }
        const VertexValue* operator->() const { return &this->dereference().value(); }
    private:
        friend class Graph;
        ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
    };


    //                                  Storage nodes
public:

    class Edge {
        VirtualList<Edge> edgeLists_;                   // links for in- and out-edge sublists; MUST BE FIRST
        EdgeValue value_;                               // user-defined data for each edge
        typename EdgeList::NodeIterator self_;          // always points to itself so we can get to IndexedList::Node
        VertexIterator source_, target_;                // starting and ending points of the edge are always required
    private:
        friend class Graph;
        Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
            : value_(value), source_(source), target_(target) {}
    public:
        const size_t& id() const { return self_->id(); }

        const VertexIterator& source() { return source_; }
        ConstVertexIterator source() const { return source_; }
        const VertexIterator& target() { return target_; }
        ConstVertexIterator target() const { return target_; }
        EdgeValue& value() { return value_; }
        const EdgeValue& value() const { return value_; }
        bool isSelfEdge() const {
            return source_ == target_;
        }
    };

    class Vertex {
        VertexValue value_;                             // user data for this vertex
        typename VertexList::NodeIterator self_;        // always points to itself so we can get to IndexedList::Node
        VirtualList<Edge> edgeLists_;                   // this is the head node; points to the real edges
        size_t nInEdges_;                               // number of incoming edges
        size_t nOutEdges_;                              // number of outgoing edges
    private:
        friend class Graph;
        Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
    public:
        const size_t& id() const { return self_->id(); }

        boost::iterator_range<EdgeIterator> inEdges() {
            EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
            EdgeIterator end(IN_EDGES, &edgeLists_);
            return boost::iterator_range<EdgeIterator>(begin, end);
        }
        boost::iterator_range<ConstEdgeIterator> inEdges() const {
            ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
            ConstEdgeIterator end(IN_EDGES, &edgeLists_);
            return boost::iterator_range<ConstEdgeIterator>(begin, end);
        }
        boost::iterator_range<EdgeIterator> outEdges() {
            EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
            EdgeIterator end(OUT_EDGES, &edgeLists_);
            return boost::iterator_range<EdgeIterator>(begin, end);
        }
        boost::iterator_range<ConstEdgeIterator> outEdges() const {
            ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
            ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
            return boost::iterator_range<ConstEdgeIterator>(begin, end);
        }
        size_t nInEdges() const {
            return nInEdges_;
        }

        size_t nOutEdges() const {
            return nOutEdges_;
        }

        size_t degree() const {
            return nInEdges_ + nOutEdges_;
        }

        VertexValue& value() { return value_; }
        const VertexValue& value() const { return value_; }
    };

private:
    typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
    typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;

    EdgeList edges_;                                    // all edges with integer ID numbers and O(1) insert/erase
    VertexList vertices_;                               // all vertices with integer ID numbers and O(1) insert/erase
    EdgeIndex edgeIndex_;                               // optional mapping between EdgeValue and ConstEdgeIterator
    VertexIndex vertexIndex_;                           // optional mapping between VertexValue and ConstVertexIterator

    //                                  Serialization
private:
    friend class boost::serialization::access;

    struct SerializableEdge {
        size_t srcId, tgtId;
        EdgeValue value;

        SerializableEdge()
            : srcId(-1), tgtId(-1) {}

        SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
            : srcId(srcId), tgtId(tgtId), value(value) {}

        template<class S>
        void serialize(S &s, const unsigned /*version*/) {
            s & BOOST_SERIALIZATION_NVP(srcId);
            s & BOOST_SERIALIZATION_NVP(tgtId);
            s & BOOST_SERIALIZATION_NVP(value);
        }
    };

    template<class S>
    void save(S &s, const unsigned /*version*/) const {
        size_t nv = nVertices();
        s <<BOOST_SERIALIZATION_NVP(nv);
        for (size_t i=0; i<nv; ++i)
            s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
                                               
        size_t ne = nEdges();
        s <<BOOST_SERIALIZATION_NVP(ne);
        for (size_t i=0; i<ne; ++i) {
            ConstEdgeIterator edge = findEdge(i);
            SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
            s <<BOOST_SERIALIZATION_NVP(se);
        }
    }

    template<class S>
    void load(S &s, const unsigned /*version*/) {
        clear();
        size_t nv = 0;
        s >>BOOST_SERIALIZATION_NVP(nv);
        for (size_t i=0; i<nv; ++i) {
            VertexValue vv;
            s >>boost::serialization::make_nvp("vertex", vv);
            insertVertex(vv);
        }

        size_t ne = 0;
        s >>BOOST_SERIALIZATION_NVP(ne);
        for (size_t i=0; i<ne; ++i) {
            SerializableEdge se;
            s >>BOOST_SERIALIZATION_NVP(se);
            ASSERT_require(se.srcId < nv && se.tgtId < nv);
            insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
        }
    }

    BOOST_SERIALIZATION_SPLIT_MEMBER();


    //                                  Initialization
public:

    Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};

    Graph(const Graph &other)
        : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
        *this = other;
    }

    template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
    Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
        : edges_(allocator), vertices_(allocator) {
        *this = other;
    }

    Graph& operator=(const Graph &other) {
        return operator=<V, E>(other);
    }
    
    template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
    Graph& operator=(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other) {
        clear();
        for (size_t i=0; i<other.nVertices(); ++i) {
            typename Graph<V2, E2, VKey2, EKey2, Alloc2>::ConstVertexIterator vertex = other.findVertex(i);
            VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
            ASSERT_require(inserted->id() == i);
        }
        for (size_t i=0; i<other.nEdges(); ++i) {
            typename Graph<V2, E2, VKey2, EKey2, Alloc2>::ConstEdgeIterator edge = other.findEdge(i);
            VertexIterator vsrc = findVertex(edge->source()->id());
            VertexIterator vtgt = findVertex(edge->target()->id());
            insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
        }
        return *this;
    }

    const Allocator& allocator() {
        return vertices_.allocator();
    }

public:

    boost::iterator_range<VertexIterator> vertices() {
        return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
                                                     VertexIterator(vertices_.nodes().end()));
    }
    boost::iterator_range<ConstVertexIterator> vertices() const {
        return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
                                                          ConstVertexIterator(vertices_.nodes().end()));
    }
    boost::iterator_range<VertexValueIterator> vertexValues() {
        return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
                                                          VertexValueIterator(vertices_.nodes().end()));
    }
    boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
        return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
                                                               ConstVertexValueIterator(vertices_.nodes().end()));
    }
    VertexIterator findVertex(size_t id) {
        return VertexIterator(vertices_.find(id));
    }
    ConstVertexIterator findVertex(size_t id) const {
        return ConstVertexIterator(vertices_.find(id));
    }
    VertexIterator findVertexKey(const VertexKey &key) {
        if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
            return findVertex((*ov)->id());
        return vertices().end();
    }
    ConstVertexIterator findVertexKey(const VertexKey &key) const {
        return vertexIndex_.lookup(key).orElse(vertices().end());
    }
    VertexIterator findVertexValue(const VertexValue &value) {
        return findVertexKey(VertexKey(value));
    }
    ConstVertexIterator findVertexValue(const VertexValue &value) const {
        return findVertexKey(VertexKey(value));
    }
    bool isValidVertex(const ConstVertexIterator &vertex) const {
        return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
    }

    boost::iterator_range<EdgeIterator> edges() {
        return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
                                                   EdgeIterator(edges_.nodes().end()));
    }
    boost::iterator_range<ConstEdgeIterator> edges() const {
        return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
                                                        ConstEdgeIterator(edges_.nodes().end()));
    }
    boost::iterator_range<EdgeValueIterator> edgeValues() {
        return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
                                                        EdgeValueIterator(edges_.nodes().end()));
    }
    boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
        return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
                                                             ConstEdgeValueIterator(edges_.nodes().end()));
    }
    EdgeIterator findEdge(size_t id) {
        return EdgeIterator(edges_.find(id));
    }
    ConstEdgeIterator findEdge(size_t id) const {
        return ConstEdgeIterator(edges_.find(id));
    }
    EdgeIterator findEdgeKey(const EdgeKey &key) {
        if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
            return findEdge((*oe)->id());
        return edges().end();
    }
    ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
        return edgeIndex_.lookup(key).orElse(edges().end());
    }
    EdgeIterator findEdgeValue(const EdgeValue &value) {
        return findEdgeKey(EdgeKey(value));
    }
    ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
        return findEdgeValue(EdgeKey(value));
    }
    bool isValidEdge(const ConstEdgeIterator &edge) const {
        return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
    }

    size_t nVertices() const {
        return vertices_.size();
    }

    size_t nEdges() const {
        return edges_.size();
    }

    bool isEmpty() const {
        ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
        return vertices_.isEmpty();
    }

    VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
        return insertVertexImpl(value, true /*strict*/);
    }

    VertexIterator insertVertexMaybe(const VertexValue &value) {
        return insertVertexImpl(value, false /*non-strict*/);
    }
    
    EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
                            const EdgeValue &value = EdgeValue()) {
        return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
    }
    EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
                            const EdgeValue &value = EdgeValue()) {
        ASSERT_require(isValidVertex(sourceVertex));
        ASSERT_require(isValidVertex(targetVertex));
        return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
    }
    EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
                                 const EdgeValue &value = EdgeValue()) {
        return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
    }
    EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
                                 const EdgeValue &value = EdgeValue()) {
        ASSERT_require(isValidVertex(sourceVertex));
        ASSERT_require(isValidVertex(targetVertex));
        return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
    }
    EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
                                        const EdgeValue &edgeValue = EdgeValue()) {
        VertexIterator source = insertVertexMaybe(sourceValue);
        VertexIterator target = insertVertexMaybe(targetValue);
        return insertEdge(source, target, edgeValue);
    }

    EdgeIterator eraseEdge(const EdgeIterator &edge) {
        ASSERT_require(isValidEdge(edge));
        EdgeIterator next = edge; ++next;               // advance before we delete edge
        edgeIndex_.erase(EdgeKey(edge->value()));
        --edge->source_->nOutEdges_;
        edge->edgeLists_.remove(OUT_EDGES);
        --edge->target_->nInEdges_;
        edge->edgeLists_.remove(IN_EDGES);
        edges_.eraseAt(edge->self_);                    // edge is now deleted
        return next;
    }
    EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
        ASSERT_require(isValidEdge(edge));
        return eraseEdge(findEdge(edge->id()));
    }
    EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
        ASSERT_require(isValidEdge(edge));
        VertexIterator source = edge->source();
        VertexIterator target = edge->target();
        EdgeIterator retval = eraseEdge(edge);
        if (source == target) {
            if (source->degree() == 0)
                eraseVertex(source);
        } else {
            if (source->degree() == 0)
                eraseVertex(source);
            if (target->degree() == 0)
                eraseVertex(target);
        }
        return retval;
    }

    void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
        ASSERT_require(isValidVertex(source));
        ASSERT_require(isValidVertex(target));
        if (source->nOutEdges() < target->nInEdges()) {
            EdgeIterator iter = source->outEdges().begin();
            while (iter != source->outEdges().end()) {
                if (iter->target() == target) {
                    iter = eraseEdge(iter);
                } else {
                    ++iter;
                }
            }
        } else {
            EdgeIterator iter = target->inEdges().begin();
            while (iter != target->inEdges().end()) {
                if (iter->source() == source) {
                    iter = eraseEdge(iter);
                } else {
                    ++iter;
                }
            }
        }
    }
    void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
        ASSERT_require(isValidVertex(source));
        ASSERT_require(isValidVertex(target));
        eraseEdges(findVertex(source->id()), findVertex(target->id()));
    }
    VertexIterator eraseVertex(const VertexIterator &vertex) {
        ASSERT_require(isValidVertex(vertex));
        VertexIterator next = vertex; ++next;       // advance before we delete vertex
        clearEdges(vertex);
        vertexIndex_.erase(VertexKey(vertex->value()));
        vertices_.eraseAt(vertex->self_);               // vertex is now deleted
        return next;
    }
    VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
        ASSERT_require(isValidVertex(vertex));
        return eraseVertex(findVertex(vertex->id()));
    }
    void clearEdges() {
        for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
            vertex->inEdges().reset();
            vertex->outEdges().reset();
        }
        edges_.clear();
        edgeIndex_.clear();
    }

    void clearEdges(const VertexIterator &vertex) {
        clearOutEdges(vertex);
        clearInEdges(vertex);
    }
    void clearEdges(const ConstVertexIterator &vertex) {
        clearOutEdges(vertex);
        clearInEdges(vertex);
    }
    void clearOutEdges(const VertexIterator &vertex) {
        ASSERT_forbid(vertex==vertices().end());
        for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
            edge = eraseEdge(edge);
    }
    void clearOutEdges(const ConstVertexIterator &vertex) {
        ASSERT_forbid(vertex==vertices().end());
        clearOutEdges(findVertex(vertex->id()));
    }
    void clearInEdges(const VertexIterator &vertex) {
        ASSERT_forbid(vertex==vertices().end());
        for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
            edge = eraseEdge(edge);
    }
    void clearInEdges(const ConstVertexIterator &vertex) {
        ASSERT_forbid(vertex==vertices().end());
        clearInEdges(findVertex(vertex->id()));
    }
    void clear() {
        edges_.clear();
        vertices_.clear();
        edgeIndex_.clear();
        vertexIndex_.clear();
    }

    // Internal implementation details
private:
    VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
        const VertexKey key(value);
        if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
            if (strict)
                throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
            return findVertex((*found)->id());
        }
        typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
        inserted->value().self_ = inserted;
        inserted->value().edgeLists_.reset(NULL);       // this is a sublist head, no edge node
        VertexIterator retval = VertexIterator(inserted);
        vertexIndex_.insert(key, retval);
        return retval;
    }

    EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
                                const EdgeValue &value, bool strict) {
        const EdgeKey key(value);
        ASSERT_require(isValidVertex(sourceVertex));
        ASSERT_require(isValidVertex(targetVertex));
        if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
            if (strict)
                throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
            return findEdge((*found)->id());
        }
        typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
        inserted->value().self_ = inserted;
        inserted->value().edgeLists_.reset(&inserted->value());
        EdgeIterator newEdge(inserted);
        sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
        ++sourceVertex->nOutEdges_;
        targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
        ++targetVertex->nInEdges_;
        edgeIndex_.insert(key, newEdge);
        return newEdge;
    }


    // Deprecated stuff
public:
    // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
    typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
    typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
    typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
    typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
    typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
    typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
};

} // namespace
} // namespace

#endif