11 #include <Sawyer/Assert.h>
12 #include <Sawyer/DefaultAllocator.h>
13 #include <Sawyer/Exception.h>
14 #include <Sawyer/IndexedList.h>
15 #include <Sawyer/Map.h>
16 #include <Sawyer/Optional.h>
17 #include <Sawyer/Sawyer.h>
18 #include <boost/range/iterator_range.hpp>
19 #include <boost/serialization/access.hpp>
20 #include <boost/serialization/nvp.hpp>
21 #include <boost/serialization/split_member.hpp>
22 #include <boost/unordered_map.hpp>
91 template<
class VertexValue>
104 template<
class EdgeValue>
120 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
134 void insert(
const VertexOrEdgeKey&,
const VertexOrEdgeConstIterator&) {}
139 void erase(
const VertexOrEdgeKey&) {}
155 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
169 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
176 void erase(
const VertexOrEdgeKey &key) {
195 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
197 typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator>
Map;
210 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
217 void erase(
const VertexOrEdgeKey &key) {
225 typename Map::const_iterator found = map_.find(key);
226 if (found == map_.end())
228 return found->second;
240 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
247 template<
class VertexValue,
class ConstVertexIterator>
253 template<
class EdgeValue,
class ConstEdgeIterator>
260 #define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE) \
262 namespace Container { \
263 template<class VertexOrEdgeConstIterator> \
264 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
265 typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index; \
270 #define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE) \
272 namespace Container { \
273 template<class VertexOrEdgeConstIterator> \
274 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
275 typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index; \
320 typedef const typename G::Vertex
Vertex;
321 typedef const typename G::Edge
Edge;
323 typedef const typename G::EdgeValue
EdgeValue;
636 enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
642 VirtualList *next_[N_PHASES];
643 VirtualList *prev_[N_PHASES];
650 void reset(T* node) {
652 for (
size_t i=0; i<N_PHASES; ++i)
653 next_[i] = prev_[i] =
this;
656 bool isHead()
const {
657 return node_ == NULL;
660 bool isSingleton(EdgePhase phase)
const {
661 ASSERT_require(phase < N_PHASES);
662 ASSERT_require((next_[phase]==
this && prev_[phase]==
this) || (next_[phase]!=
this && prev_[phase]!=
this));
663 return next_[phase]==
this;
666 bool isEmpty(EdgePhase phase)
const {
667 ASSERT_require(isHead());
668 ASSERT_require((next_[phase]==
this && prev_[phase]==
this) || (next_[phase]!=
this && prev_[phase]!=
this));
669 return next_[phase]==
this;
672 void insert(EdgePhase phase, VirtualList *newNode) {
673 ASSERT_require(phase < N_PHASES);
674 ASSERT_not_null(newNode);
675 ASSERT_forbid(newNode->isHead());
676 ASSERT_require(newNode->isSingleton(phase));
677 prev_[phase]->next_[phase] = newNode;
678 newNode->prev_[phase] = prev_[phase];
679 prev_[phase] = newNode;
680 newNode->next_[phase] =
this;
683 void remove(EdgePhase phase) {
684 ASSERT_require(phase < N_PHASES);
685 ASSERT_forbid(isHead());
686 prev_[phase]->next_[phase] = next_[phase];
687 next_[phase]->prev_[phase] = prev_[phase];
688 next_[phase] = prev_[phase] =
this;
691 VirtualList& next(EdgePhase phase) {
return *next_[phase]; }
692 const VirtualList& next(EdgePhase phase)
const {
return *next_[phase]; }
693 VirtualList& prev(EdgePhase phase) {
return *prev_[phase]; }
694 const VirtualList& prev(EdgePhase phase)
const {
return *prev_[phase]; }
697 ASSERT_forbid(isHead());
701 const T& dereference()
const {
702 ASSERT_forbid(isHead());
703 return *(
const T*)
this;
707 void dump(EdgePhase phase, std::ostream &o)
const {
708 const VirtualList *cur =
this;
709 o <<
" " <<std::setw(18) <<
"Node"
710 <<
"\t" <<std::setw(18) <<
"This"
711 <<
"\t" <<std::setw(18) <<
"Next"
712 <<
"\t" <<std::setw(18) <<
"Prev\n";
714 o <<
" " <<std::setw(18) <<node_
715 <<
"\t" <<std::setw(18) <<cur
716 <<
"\t" <<std::setw(18) <<cur->next_[phase]
717 <<
"\t" <<std::setw(18) <<cur->prev_[phase] <<
"\n";
718 cur = cur->next_[phase];
719 }
while (cur!=
this && cur->next_[phase]!=cur);
730 template<
class Derived,
class Value,
class Node,
class BaseIter,
class VList>
734 using iterator_category = std::bidirectional_iterator_tag;
735 using value_type = Value;
736 using difference_type = std::ptrdiff_t;
737 using pointer = Value*;
738 using reference = Value&;
748 EdgeBaseIterator(
const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
749 EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
750 template<
class BaseIter2>
EdgeBaseIterator(EdgePhase phase,
const BaseIter2 &iter, VList *vlist)
751 : phase_(phase), iter_(iter), vlist_(vlist) {}
753 Node& dereference()
const {
754 return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
758 Derived* derived() {
return static_cast<Derived*
>(
this); }
759 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
764 phase_ = other.phase_;
766 vlist_ = other.vlist_;
777 if (N_PHASES==phase_) {
780 vlist_ = &vlist_->next(phase_);
785 Derived old = *derived();
798 if (N_PHASES==phase_) {
801 vlist_ = &vlist_->prev(phase_);
806 Derived old = *derived();
819 template<
class OtherIter>
822 if (N_PHASES==phase_) {
823 a = iter_.isAtEnd() ? NULL : &iter_->value();
825 a = vlist_->isHead() ? NULL : &vlist_->dereference();
828 if (N_PHASES==other.phase_) {
829 b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
831 b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
835 template<
class OtherIter>
837 return !(*
this==other);
843 if (N_PHASES == phase_) {
844 return iter_.isAtEnd();
846 return vlist_->isHead();
852 template<
class Derived,
class Value,
class Node,
class BaseIter>
856 using iterator_category = std::bidirectional_iterator_tag;
857 using value_type = Value;
858 using difference_type = std::ptrdiff_t;
859 using pointer = Value*;
860 using reference = Value&;
869 Node& dereference()
const {
return base_->value(); }
872 Derived&
operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
881 Derived
operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
891 Derived
operator--(
int) { Derived old=*derived(); --*
this;
return old; }
899 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base_; }
900 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base_; }
905 return base_.base() == NULL;
909 Derived* derived() {
return static_cast<Derived*
>(
this); }
910 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
921 VirtualList<Edge> > {
923 VirtualList<Edge> >
Super;
929 Edge& operator*()
const {
return this->dereference(); }
930 Edge* operator->()
const {
return &this->dereference(); }
944 typename EdgeList::ConstNodeIterator,
945 const VirtualList<Edge> > {
947 typename EdgeList::ConstNodeIterator,
948 const VirtualList<Edge> >
Super;
950 typedef const Edge& Reference;
951 typedef const Edge* Pointer;
955 const Edge& operator*()
const {
return this->dereference(); }
956 const Edge* operator->()
const {
return &this->dereference(); }
971 VirtualList<Edge> > {
973 VirtualList<Edge> >
Super;
980 EdgeValue& operator*()
const {
return this->dereference().
value(); }
981 EdgeValue* operator->()
const {
return &this->dereference().
value(); }
994 typename EdgeList::ConstNodeIterator,
995 const VirtualList<Edge> > {
997 typename EdgeList::ConstNodeIterator,
998 const VirtualList<Edge> >
Super;
1007 const EdgeValue& operator*()
const {
return this->dereference().
value(); }
1008 const EdgeValue* operator->()
const {
return &this->dereference().
value(); }
1022 typename VertexList::NodeIterator> {
1024 typename VertexList::NodeIterator>
Super;
1030 Vertex& operator*()
const {
return this->dereference(); }
1031 Vertex* operator->()
const {
return &this->dereference(); }
1043 typename VertexList::ConstNodeIterator> {
1045 typename VertexList::ConstNodeIterator>
Super;
1047 typedef const Vertex& Reference;
1048 typedef const Vertex* Pointer;
1052 const Vertex& operator*()
const {
return this->dereference(); }
1053 const Vertex* operator->()
const {
return &this->dereference(); }
1066 typename VertexList::NodeIterator> {
1068 typename VertexList::NodeIterator>
Super;
1088 typename VertexList::ConstNodeIterator> {
1090 typename VertexList::ConstNodeIterator>
Super;
1099 const VertexValue& operator*()
const {
return this->dereference().
value(); }
1100 const VertexValue* operator->()
const {
return &this->dereference().
value(); }
1117 VirtualList<Edge> edgeLists_;
1119 typename EdgeList::NodeIterator self_;
1135 const size_t&
id()
const {
return self_->id(); }
1180 return source_ == target_;
1190 typename VertexList::NodeIterator self_;
1191 VirtualList<Edge> edgeLists_;
1208 const size_t&
id()
const {
return self_->id(); }
1220 EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1222 return boost::iterator_range<EdgeIterator>(begin, end);
1224 boost::iterator_range<ConstEdgeIterator>
inEdges()
const {
1227 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1241 EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1243 return boost::iterator_range<EdgeIterator>(begin, end);
1245 boost::iterator_range<ConstEdgeIterator>
outEdges()
const {
1248 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1271 return nInEdges_ + nOutEdges_;
1294 VertexList vertices_;
1295 EdgeIndex edgeIndex_;
1296 VertexIndex vertexIndex_;
1302 friend class boost::serialization::access;
1304 struct SerializableEdge {
1305 size_t srcId, tgtId;
1309 : srcId(-1), tgtId(-1) {}
1311 SerializableEdge(
size_t srcId,
size_t tgtId,
const EdgeValue &value)
1312 : srcId(srcId), tgtId(tgtId), value(value) {}
1315 void serialize(S &s,
const unsigned ) {
1316 s & BOOST_SERIALIZATION_NVP(srcId);
1317 s & BOOST_SERIALIZATION_NVP(tgtId);
1318 s & BOOST_SERIALIZATION_NVP(value);
1323 void save(S &s,
const unsigned )
const {
1325 s <<BOOST_SERIALIZATION_NVP(nv);
1326 for (
size_t i=0; i<nv; ++i)
1327 s <<boost::serialization::make_nvp(
"vertex",
findVertex(i)->value());
1330 s <<BOOST_SERIALIZATION_NVP(ne);
1331 for (
size_t i=0; i<ne; ++i) {
1332 ConstEdgeIterator edge =
findEdge(i);
1333 SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1334 s <<BOOST_SERIALIZATION_NVP(se);
1339 void load(S &s,
const unsigned ) {
1342 s >>BOOST_SERIALIZATION_NVP(nv);
1343 for (
size_t i=0; i<nv; ++i) {
1345 s >>boost::serialization::make_nvp(
"vertex", vv);
1350 s >>BOOST_SERIALIZATION_NVP(ne);
1351 for (
size_t i=0; i<ne; ++i) {
1352 SerializableEdge se;
1353 s >>BOOST_SERIALIZATION_NVP(se);
1354 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1359 BOOST_SERIALIZATION_SPLIT_MEMBER();
1397 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1411 return operator=<V, E>(other);
1425 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1428 for (
size_t i=0; i<other.
nVertices(); ++i) {
1431 ASSERT_require(inserted->id() == i);
1433 for (
size_t i=0; i<other.
nEdges(); ++i) {
1446 return vertices_.allocator();
1461 return boost::iterator_range<VertexIterator>(
VertexIterator(vertices_.nodes().begin()),
1464 boost::iterator_range<ConstVertexIterator>
vertices()
const {
1465 return boost::iterator_range<ConstVertexIterator>(
ConstVertexIterator(vertices_.nodes().begin()),
1488 return boost::iterator_range<VertexValueIterator>(
VertexValueIterator(vertices_.nodes().begin()),
1531 return vertexIndex_.lookup(key).orElse(
vertices().end());
1569 boost::iterator_range<EdgeIterator>
edges() {
1570 return boost::iterator_range<EdgeIterator>(
EdgeIterator(edges_.nodes().begin()),
1573 boost::iterator_range<ConstEdgeIterator>
edges()
const {
1574 return boost::iterator_range<ConstEdgeIterator>(
ConstEdgeIterator(edges_.nodes().begin()),
1597 return boost::iterator_range<EdgeValueIterator>(
EdgeValueIterator(edges_.nodes().begin()),
1600 boost::iterator_range<ConstEdgeValueIterator>
edgeValues()
const {
1637 return edges().end();
1640 return edgeIndex_.lookup(key).orElse(
edges().end());
1677 return vertices_.size();
1687 return edges_.size();
1696 ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty());
1697 return vertices_.isEmpty();
1713 return insertVertexImpl(value,
true );
1725 return insertVertexImpl(value,
false );
1744 return insertEdgeImpl(sourceVertex, targetVertex, value,
true );
1766 return insertEdgeImpl(sourceVertex, targetVertex, value,
false );
1784 return insertEdge(source, target, edgeValue);
1806 --edge->source_->nOutEdges_;
1807 edge->edgeLists_.remove(OUT_EDGES);
1808 --edge->target_->nInEdges_;
1809 edge->edgeLists_.remove(IN_EDGES);
1810 edges_.eraseAt(edge->self_);
1833 if (source == target) {
1834 if (source->degree() == 0)
1837 if (source->degree() == 0)
1839 if (target->degree() == 0)
1857 if (source->nOutEdges() < target->nInEdges()) {
1859 while (iter != source->outEdges().end()) {
1860 if (iter->
target() == target) {
1868 while (iter != target->inEdges().end()) {
1869 if (iter->
source() == source) {
1905 vertices_.eraseAt(vertex->self_);
1922 vertex->inEdges().reset();
1923 vertex->outEdges().reset();
1959 ASSERT_forbid(vertex==
vertices().end());
1964 ASSERT_forbid(vertex==
vertices().end());
1979 ASSERT_forbid(vertex==
vertices().end());
1984 ASSERT_forbid(vertex==
vertices().end());
2000 vertexIndex_.clear();
2007 VertexIterator insertVertexImpl(
const VertexValue &value,
bool strict) {
2014 typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(),
Vertex(value));
2015 inserted->value().self_ = inserted;
2016 inserted->value().edgeLists_.reset(NULL);
2017 VertexIterator retval = VertexIterator(inserted);
2018 vertexIndex_.insert(key, retval);
2022 EdgeIterator insertEdgeImpl(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
2027 if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2029 throw Exception::AlreadyExists(
"cannot insert duplicate edge when graph edges are indexed");
2032 typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(),
Edge(value, sourceVertex, targetVertex));
2033 inserted->value().self_ = inserted;
2034 inserted->value().edgeLists_.reset(&inserted->value());
2035 EdgeIterator newEdge(inserted);
2036 sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2037 ++sourceVertex->nOutEdges_;
2038 targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2039 ++targetVertex->nInEdges_;
2040 edgeIndex_.insert(key, newEdge);
2050 typedef Edge EdgeNode SAWYER_DEPRECATED(
"use Edge instead");
2051 typedef Vertex VertexNode SAWYER_DEPRECATED(
"use Vertex instead");
2052 typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED(
"use EdgeIterator instead");
2053 typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED(
"use ConstEdgeIterator instead");
2054 typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED(
"use VertexIterator instead");
2055 typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED(
"use ConstVertexIterator instead");