ROSE 0.11.145.147
Graph.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_Graph_H
9#define Sawyer_Graph_H
10
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> // for Sawyer::Nothing
17#include <Sawyer/Sawyer.h>
18#include <boost/range/iterator_range.hpp>
19#include <boost/unordered_map.hpp>
20#include <ostream>
21#if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
22#include <iomanip>
23#endif
24
25namespace Sawyer {
26namespace Container {
27
79// Special vertex and edge key types.
81
88template<class VertexValue>
90public:
92 explicit GraphVertexNoKey(const VertexValue&) {}
93};
94
101template<class EdgeValue>
103public:
104 GraphEdgeNoKey() {}
105 explicit GraphEdgeNoKey(const EdgeValue&) {}
106};
107
109// Special vertex and edge indexing types.
111
117template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
119public:
123 void clear() {}
124
131 void insert(const VertexOrEdgeKey&, const VertexOrEdgeConstIterator&) {}
132
136 void erase(const VertexOrEdgeKey&) {}
137
142 Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey&) const {
143 return Nothing();
144 }
145};
146
152template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
155public:
159 void clear() {
160 map_.clear();
161 }
162
166 void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
167 map_.insert(key, iter); // Unlike std::map, Sawyer's "insert" always inserts
168 }
169
173 void erase(const VertexOrEdgeKey &key) {
174 map_.erase(key);
175 }
176
180 Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
181 return map_.getOptional(key);
182 }
183};
184
192template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
194 typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator> Map;
195 Map map_;
196public:
200 void clear() {
201 map_.clear();
202 }
203
207 void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
208 map_[key] = iter;
209 }
210
214 void erase(const VertexOrEdgeKey &key) {
215 map_.erase(key);
216 }
217
221 Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
222 typename Map::const_iterator found = map_.find(key);
223 if (found == map_.end())
224 return Nothing();
225 return found->second;
226 }
227};
228
237template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
242
243// Partial specialization for when there is no vertex index
244template<class VertexValue, class ConstVertexIterator>
245struct GraphIndexTraits<GraphVertexNoKey<VertexValue>, ConstVertexIterator> {
246 typedef GraphVoidIndex<GraphVertexNoKey<VertexValue>, ConstVertexIterator> Index;
247};
248
249// Partial specialization for when there is no edge index.
250template<class EdgeValue, class ConstEdgeIterator>
251struct GraphIndexTraits<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> {
252 typedef GraphVoidIndex<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> Index;
253};
254
255// A #define so users that don't understand C++ templates can still get by. See GraphIndexTraits doc for details.
256// Must be used at global scope.
257#define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE) \
258 namespace Sawyer { \
259 namespace Container { \
260 template<class VertexOrEdgeConstIterator> \
261 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
262 typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index; \
263 }; \
264 } \
265 }
266
267#define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE) \
268 namespace Sawyer { \
269 namespace Container { \
270 template<class VertexOrEdgeConstIterator> \
271 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
272 typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index; \
273 }; \
274 } \
275 }
276
277
279// Graph traits
281
283template<class G>
286 typedef typename G::EdgeIterator EdgeIterator;
287
289 typedef typename G::EdgeValueIterator EdgeValueIterator;
290
292 typedef typename G::VertexIterator VertexIterator;
293
295 typedef typename G::VertexValueIterator VertexValueIterator;
296
298 typedef typename G::Vertex Vertex;
299
301 typedef typename G::Edge Edge;
302
304 typedef typename G::VertexValue VertexValue;
305
307 typedef typename G::EdgeValue EdgeValue;
308
310 static bool allVertices(const Vertex&) {
311 return true;
312 }
313
315 static bool allEdges(const Edge&) {
316 return true;
317 }
318};
319
320// GraphTraits specialization for const graphs.
321template<class G>
322struct GraphTraits<const G> {
323 typedef typename G::ConstEdgeIterator EdgeIterator;
324 typedef typename G::ConstEdgeValueIterator EdgeValueIterator;
325 typedef typename G::ConstVertexIterator VertexIterator;
326 typedef typename G::ConstVertexValueIterator VertexValueIterator;
327 typedef const typename G::Vertex Vertex;
328 typedef const typename G::Edge Edge;
329 typedef const typename G::VertexValue VertexValue;
330 typedef const typename G::EdgeValue EdgeValue;
331 static bool allVertices(const Vertex&) { return true; }
332 static bool allEdges(const Edge&) { return true; }
333};
334
631template<class V = Nothing, class E = Nothing,
632 class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>,
633 class Alloc = DefaultAllocator>
634class Graph {
635public:
636 typedef V VertexValue;
637 typedef E EdgeValue;
638 typedef VKey VertexKey;
639 typedef EKey EdgeKey;
640 typedef Alloc Allocator;
641 class Vertex;
642 class Edge;
644private:
645 enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
646 typedef IndexedList<Edge, Allocator> EdgeList;
647 typedef IndexedList<Vertex, Allocator> VertexList;
648
649 template<class T>
650 class VirtualList {
651 VirtualList *next_[N_PHASES];
652 VirtualList *prev_[N_PHASES];
653 T *node_;
654 public:
655 VirtualList() {
656 reset(NULL);
657 }
658
659 void reset(T* node) {
660 node_ = node;
661 for (size_t i=0; i<N_PHASES; ++i)
662 next_[i] = prev_[i] = this;
663 }
664
665 bool isHead() const {
666 return node_ == NULL;
667 }
668
669 bool isSingleton(EdgePhase phase) const {
670 ASSERT_require(phase < N_PHASES);
671 ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
672 return next_[phase]==this;
673 }
674
675 bool isEmpty(EdgePhase phase) const {
676 ASSERT_require(isHead());
677 ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
678 return next_[phase]==this;
679 }
680
681 void insert(EdgePhase phase, VirtualList *newNode) { // insert newNode before this
682 ASSERT_require(phase < N_PHASES);
683 ASSERT_not_null(newNode);
684 ASSERT_forbid(newNode->isHead());
685 ASSERT_require(newNode->isSingleton(phase)); // cannot be part of another sublist already
686 prev_[phase]->next_[phase] = newNode;
687 newNode->prev_[phase] = prev_[phase];
688 prev_[phase] = newNode;
689 newNode->next_[phase] = this;
690 }
691
692 void remove(EdgePhase phase) { // Remove this node from the list
693 ASSERT_require(phase < N_PHASES);
694 ASSERT_forbid(isHead());
695 prev_[phase]->next_[phase] = next_[phase];
696 next_[phase]->prev_[phase] = prev_[phase];
697 next_[phase] = prev_[phase] = this;
698 }
699
700 VirtualList& next(EdgePhase phase) { return *next_[phase]; }
701 const VirtualList& next(EdgePhase phase) const { return *next_[phase]; }
702 VirtualList& prev(EdgePhase phase) { return *prev_[phase]; }
703 const VirtualList& prev(EdgePhase phase) const { return *prev_[phase]; }
704
705 T& dereference() { // Return the Edge to which this VirtualList node belongs
706 ASSERT_forbid(isHead()); // list head contains no user-data
707 return *(T*)this; // depends on VirtualList being at the beginning of Edge
708 }
709
710 const T& dereference() const {
711 ASSERT_forbid(isHead());
712 return *(const T*)this;
713 }
714
715#if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
716 void dump(EdgePhase phase, std::ostream &o) const {
717 const VirtualList *cur = this;
718 o <<" " <<std::setw(18) <<"Node"
719 <<"\t" <<std::setw(18) <<"This"
720 <<"\t" <<std::setw(18) <<"Next"
721 <<"\t" <<std::setw(18) <<"Prev\n";
722 do {
723 o <<" " <<std::setw(18) <<node_
724 <<"\t" <<std::setw(18) <<cur
725 <<"\t" <<std::setw(18) <<cur->next_[phase]
726 <<"\t" <<std::setw(18) <<cur->prev_[phase] <<"\n";
727 cur = cur->next_[phase];
728 } while (cur!=this && cur->next_[phase]!=cur);
729 }
730#endif
731 };
732
734 // Iterators
736public: // public only for the sake of doxygen
739 template<class Derived, class Value, class Node, class BaseIter, class VList>
741 public:
742 // Five standard iterator types
743 using iterator_category = std::bidirectional_iterator_tag;
744 using value_type = Value;
745 using difference_type = std::ptrdiff_t;
746 using pointer = Value*;
747 using reference = Value&;
748
749 private:
750 EdgePhase phase_; // IN_EDGES, OUT_EDGES or N_PHASES (graph edges)
751 BaseIter iter_; // EdgeList::NodeIterator or EdgeList::ConstNodeIterator
752 VList *vlist_; // (const) VirtualList<Edge> when phase_ is IN_EDGES or OUT_EDGES
753 protected:
754 friend class Graph;
756 EdgeBaseIterator(const EdgeBaseIterator &other): phase_(other.phase_), iter_(other.iter_), vlist_(other.vlist_) {}
757 EdgeBaseIterator(const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
758 EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
759 template<class BaseIter2> EdgeBaseIterator(EdgePhase phase, const BaseIter2 &iter, VList *vlist)
760 : phase_(phase), iter_(iter), vlist_(vlist) {}
761
762 Node& dereference() const {
763 return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
764 }
765
766 private:
767 Derived* derived() { return static_cast<Derived*>(this); }
768 const Derived* derived() const { return static_cast<const Derived*>(this); }
769
770 public:
772 Derived& operator=(const Derived &other) {
773 phase_ = other.phase_;
774 iter_ = other.iter_;
775 vlist_ = other.vlist_;
776 return *derived();
777 }
778
785 Derived& operator++() {
786 if (N_PHASES==phase_) {
787 ++iter_;
788 } else {
789 vlist_ = &vlist_->next(phase_);
790 }
791 return *derived();
792 }
793 Derived operator++(int) {
794 Derived old = *derived();
795 ++*this;
796 return old;
797 }
806 Derived& operator--() {
807 if (N_PHASES==phase_) {
808 --iter_;
809 } else {
810 vlist_ = &vlist_->prev(phase_);
811 }
812 return *derived();
813 }
814 Derived operator--(int) {
815 Derived old = *derived();
816 --*this;
817 return old;
818 }
828 template<class OtherIter>
829 bool operator==(const OtherIter &other) const {
830 Node *a = NULL;
831 if (N_PHASES==phase_) {
832 a = iter_.isAtEnd() ? NULL : &iter_->value();
833 } else {
834 a = vlist_->isHead() ? NULL : &vlist_->dereference();
835 }
836 Node *b = NULL;
837 if (N_PHASES==other.phase_) {
838 b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
839 } else {
840 b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
841 }
842 return a == b;
843 }
844 template<class OtherIter>
845 bool operator!=(const OtherIter &other) const {
846 return !(*this==other);
847 }
851 bool isEmpty() const {
852 if (N_PHASES == phase_) {
853 return iter_.isAtEnd();
854 } else {
855 return vlist_->isHead();
856 }
857 }
858 };
859
861 template<class Derived, class Value, class Node, class BaseIter>
863 public:
864 // Five standard iterator types
865 using iterator_category = std::bidirectional_iterator_tag;
866 using value_type = Value;
867 using difference_type = std::ptrdiff_t;
868 using pointer = Value*;
869 using reference = Value&;
870
871 private:
872 BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
873 protected:
874 friend class Graph;
876 VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
877 VertexBaseIterator(const BaseIter &base): base_(base) {}
878 Node& dereference() const { return base_->value(); }
879 public:
881 Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
882 VertexBaseIterator& operator=(const VertexBaseIterator &other) { base_ = other.base_; return *this; }
883
890 Derived& operator++() { ++base_; return *derived(); }
891 Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
900 Derived& operator--() { --base_; return *derived(); }
901 Derived operator--(int) { Derived old=*derived(); --*this; return old; }
909 template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
910 template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
914 bool isEmpty() const {
915 return base_.base() == NULL;
916 }
917
918 private:
919 Derived* derived() { return static_cast<Derived*>(this); }
920 const Derived* derived() const { return static_cast<const Derived*>(this); }
921 };
922
923public:
930 class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
931 VirtualList<Edge> > {
932 typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
933 VirtualList<Edge> > Super;
934 public:
935 typedef Edge& Reference;
936 typedef Edge* Pointer;
937 EdgeIterator() {}
938 EdgeIterator(const EdgeIterator &other): Super(other) {}
939 EdgeIterator& operator=(const EdgeIterator &other) { this->Super::operator=(other); return *this; }
940 Edge& operator*() const { return this->dereference(); }
941 Edge* operator->() const { return &this->dereference(); }
942 private:
943 friend class Graph;
944 EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
945 EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
946 };
947
954 class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
955 typename EdgeList::ConstNodeIterator,
956 const VirtualList<Edge> > {
957 typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
958 typename EdgeList::ConstNodeIterator,
959 const VirtualList<Edge> > Super;
960 public:
961 typedef const Edge& Reference;
962 typedef const Edge* Pointer;
964 ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
965 ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
966 ConstEdgeIterator& operator=(const ConstEdgeIterator &other) { this->Super::operator=(other); return *this; }
967 const Edge& operator*() const { return this->dereference(); }
968 const Edge* operator->() const { return &this->dereference(); }
969 private:
970 friend class Graph;
971 ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
972 ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
973 };
974
981 class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
982 VirtualList<Edge> > {
983 typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
984 VirtualList<Edge> > Super;
985 public:
986 typedef EdgeValue& Reference;
987 typedef EdgeValue* Pointer;
989 EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
990 EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
991 EdgeValueIterator& operator=(const EdgeValueIterator &other) { this->Super::operator=(other); return *this; }
992 EdgeValue& operator*() const { return this->dereference().value(); }
993 EdgeValue* operator->() const { return &this->dereference().value(); }
994 private:
995 friend class Graph;
996 EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
997 EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
998 };
999
1005 class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
1006 typename EdgeList::ConstNodeIterator,
1007 const VirtualList<Edge> > {
1009 typename EdgeList::ConstNodeIterator,
1010 const VirtualList<Edge> > Super;
1011 public:
1012 typedef const EdgeValue& Reference;
1013 typedef const EdgeValue* Pointer;
1015 ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
1016 ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1017 ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1018 ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1019 ConstEdgeValueIterator& operator=(const EdgeValueIterator &other) { this->Super::operator=(other); return *this; }
1020 const EdgeValue& operator*() const { return this->dereference().value(); }
1021 const EdgeValue* operator->() const { return &this->dereference().value(); }
1022 private:
1023 friend class Graph;
1024 ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1025 ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1026 };
1027
1034 class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1035 typename VertexList::NodeIterator> {
1037 typename VertexList::NodeIterator> Super;
1038 public:
1039 typedef Vertex& Reference;
1040 typedef Vertex* Pointer;
1041 VertexIterator() {}
1042 VertexIterator(const VertexIterator &other): Super(other) {}
1043 VertexIterator& operator=(const VertexIterator &other) { this->Super::operator=(other); return *this; }
1044 Vertex& operator*() const { return this->dereference(); }
1045 Vertex* operator->() const { return &this->dereference(); }
1046 private:
1047 friend class Graph;
1048 VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1049 };
1050
1056 class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1057 typename VertexList::ConstNodeIterator> {
1059 typename VertexList::ConstNodeIterator> Super;
1060 public:
1061 typedef const Vertex& Reference;
1062 typedef const Vertex* Pointer;
1064 ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1065 ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1066 ConstVertexIterator& operator=(const ConstVertexIterator &other) { this->Super::operator=(other); return *this; }
1067 const Vertex& operator*() const { return this->dereference(); }
1068 const Vertex* operator->() const { return &this->dereference(); }
1069 private:
1070 friend class Graph;
1071 ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1072 };
1073
1080 class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1081 typename VertexList::NodeIterator> {
1083 typename VertexList::NodeIterator> Super;
1084 public:
1085 typedef VertexValue& Reference;
1086 typedef VertexValue* Pointer;
1088 VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1089 VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1090 VertexValueIterator& operator=(const VertexValueIterator &other) { this->Super::operator=(other); return *this; }
1091 VertexValue& operator*() const { return this->dereference().value(); }
1092 VertexValue* operator->() const { return &this->dereference().value(); }
1093 private:
1094 friend class Graph;
1095 VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1096 };
1097
1103 class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1104 typename VertexList::ConstNodeIterator> {
1106 typename VertexList::ConstNodeIterator> Super;
1107 public:
1108 typedef const VertexValue& Reference;
1109 typedef const VertexValue* Pointer;
1112 ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1113 ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1114 ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1115 ConstVertexValueIterator& operator=(const ConstVertexValueIterator &other) { this->Super::operator=(other); return *this; }
1116 const VertexValue& operator*() const { return this->dereference().value(); }
1117 const VertexValue* operator->() const { return &this->dereference().value(); }
1118 private:
1119 friend class Graph;
1120 ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1121 };
1122
1123
1125 // Storage nodes
1127public:
1128
1133 class Edge {
1134 VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1135 EdgeValue value_; // user-defined data for each edge
1136 typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1137 VertexIterator source_, target_; // starting and ending points of the edge are always required
1138 private:
1139 friend class Graph;
1141 : value_(value), source_(source), target_(target) {}
1142 public:
1152 const size_t& id() const { return self_->id(); }
1153
1162 const VertexIterator& source() { return source_; }
1163 ConstVertexIterator source() const { return source_; }
1174 const VertexIterator& target() { return target_; }
1175 ConstVertexIterator target() const { return target_; }
1188 EdgeValue& value() { return value_; }
1189 const EdgeValue& value() const { return value_; }
1196 bool isSelfEdge() const {
1197 return source_ == target_;
1198 }
1199 };
1200
1205 class Vertex {
1206 VertexValue value_; // user data for this vertex
1207 typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1208 VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1209 size_t nInEdges_; // number of incoming edges
1210 size_t nOutEdges_; // number of outgoing edges
1211 private:
1212 friend class Graph;
1213 Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1214 public:
1225 const size_t& id() const { return self_->id(); }
1226
1236 boost::iterator_range<EdgeIterator> inEdges() {
1237 EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1238 EdgeIterator end(IN_EDGES, &edgeLists_);
1239 return boost::iterator_range<EdgeIterator>(begin, end);
1240 }
1241 boost::iterator_range<ConstEdgeIterator> inEdges() const {
1242 ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1243 ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1244 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1245 }
1257 boost::iterator_range<EdgeIterator> outEdges() {
1258 EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1259 EdgeIterator end(OUT_EDGES, &edgeLists_);
1260 return boost::iterator_range<EdgeIterator>(begin, end);
1261 }
1262 boost::iterator_range<ConstEdgeIterator> outEdges() const {
1263 ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1264 ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1265 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1266 }
1272 size_t nInEdges() const {
1273 return nInEdges_;
1274 }
1275
1279 size_t nOutEdges() const {
1280 return nOutEdges_;
1281 }
1282
1287 size_t degree() const {
1288 return nInEdges_ + nOutEdges_;
1289 }
1290
1301 VertexValue& value() { return value_; }
1302 const VertexValue& value() const { return value_; }
1304 };
1305
1306private:
1308 typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1309
1310 EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1311 VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1312 EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1313 VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1314
1316 // Serialization
1318#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
1319private:
1320 friend class boost::serialization::access;
1321
1322 struct BoostSerializableEdge {
1323 size_t srcId, tgtId;
1324 EdgeValue value;
1325
1326 BoostSerializableEdge()
1327 : srcId(-1), tgtId(-1) {}
1328
1329 BoostSerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1330 : srcId(srcId), tgtId(tgtId), value(value) {}
1331
1332 template<class S>
1333 void serialize(S &s, const unsigned /*version*/) {
1334 s & BOOST_SERIALIZATION_NVP(srcId);
1335 s & BOOST_SERIALIZATION_NVP(tgtId);
1336 s & BOOST_SERIALIZATION_NVP(value);
1337 }
1338 };
1339
1340 template<class S>
1341 void save(S &s, const unsigned /*version*/) const {
1342 size_t nv = nVertices();
1343 s <<BOOST_SERIALIZATION_NVP(nv);
1344 for (size_t i=0; i<nv; ++i)
1345 s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
1346
1347 size_t ne = nEdges();
1348 s <<BOOST_SERIALIZATION_NVP(ne);
1349 for (size_t i=0; i<ne; ++i) {
1350 ConstEdgeIterator edge = findEdge(i);
1351 BoostSerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1352 s <<BOOST_SERIALIZATION_NVP(se);
1353 }
1354 }
1355
1356 template<class S>
1357 void load(S &s, const unsigned /*version*/) {
1358 clear();
1359 size_t nv = 0;
1360 s >>BOOST_SERIALIZATION_NVP(nv);
1361 for (size_t i=0; i<nv; ++i) {
1362 VertexValue vv;
1363 s >>boost::serialization::make_nvp("vertex", vv);
1364 insertVertex(vv);
1365 }
1366
1367 size_t ne = 0;
1368 s >>BOOST_SERIALIZATION_NVP(ne);
1369 for (size_t i=0; i<ne; ++i) {
1370 BoostSerializableEdge se;
1371 s >>BOOST_SERIALIZATION_NVP(se);
1372 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1373 insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1374 }
1375 }
1376
1377 BOOST_SERIALIZATION_SPLIT_MEMBER();
1378#endif
1379
1380#ifdef SAWYER_HAVE_CEREAL
1381private:
1382 friend class cereal::access;
1383
1384 struct CerealSerializableEdge {
1385 size_t srcId, tgtId;
1386 EdgeValue value;
1387
1388 CerealSerializableEdge()
1389 : srcId(-1), tgtId(-1) {}
1390
1391 CerealSerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1392 : srcId(srcId), tgtId(tgtId), value(value) {}
1393
1394 template<class Archive>
1395 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive &archive) {
1396 archive(CEREAL_NVP(srcId));
1397 archive(CEREAL_NVP(tgtId));
1398 archive(CEREAL_NVP(value));
1399 }
1400 };
1401
1402 template<class Archive>
1403 void CEREAL_SAVE_FUNCTION_NAME(Archive &archive) const {
1404 size_t nv = nVertices();
1405 archive(CEREAL_NVP(nv));
1406 for (size_t i = 0; i < nv; ++i)
1407 archive(cereal::make_nvp("vertex", findVertex(i)->value()));
1408
1409 size_t ne = nEdges();
1410 archive(CEREAL_NVP(ne));
1411 for (size_t i = 0; i < ne; ++i) {
1412 ConstEdgeIterator edge = findEdge(i);
1413 CerealSerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1414 archive(CERAL_NVP(se));
1415 }
1416 }
1417
1418 template<class Archive>
1419 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
1420 clear();
1421 size_t nv = 0;
1422 archive(CEREAL_NVP(nv));
1423 for (size_t i = 0; i < nv; ++i) {
1424 VertexValue vv;
1425 archive(cereal::make_nvp("vertex", vv));
1426 insertVertex(vv);
1427 }
1428
1429 size_t ne = 0;
1430 archive(CEREAL_NVP(ne));
1431 for (size_t i = 0; i < ne; ++i) {
1432 CerealSerializableEdge se;
1433 archive(CEREAL_NVP(se));
1434 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1435 insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1436 }
1437 }
1438#endif
1439
1441 // Initialization
1443public:
1444
1450 Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1451
1462 Graph(const Graph &other)
1463 : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1464 *this = other;
1465 }
1466
1475 template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1477 : edges_(allocator), vertices_(allocator) {
1478 *this = other;
1479 }
1480
1488 Graph& operator=(const Graph &other) {
1489 return operator=<V, E>(other);
1490 }
1491
1503 template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1505 clear();
1506 for (size_t i=0; i<other.nVertices(); ++i) {
1508 VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1509 ASSERT_require(inserted->id() == i);
1510 }
1511 for (size_t i=0; i<other.nEdges(); ++i) {
1513 VertexIterator vsrc = findVertex(edge->source()->id());
1514 VertexIterator vtgt = findVertex(edge->target()->id());
1515 insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1516 }
1517 return *this;
1518 }
1519
1524 return vertices_.allocator();
1525 }
1526
1528public:
1529
1538 boost::iterator_range<VertexIterator> vertices() {
1539 return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1540 VertexIterator(vertices_.nodes().end()));
1541 }
1542 boost::iterator_range<ConstVertexIterator> vertices() const {
1543 return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1544 ConstVertexIterator(vertices_.nodes().end()));
1545 }
1565 boost::iterator_range<VertexValueIterator> vertexValues() {
1566 return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1567 VertexValueIterator(vertices_.nodes().end()));
1568 }
1569 boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1570 return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1571 ConstVertexValueIterator(vertices_.nodes().end()));
1572 }
1586 return VertexIterator(vertices_.find(id));
1587 }
1589 return ConstVertexIterator(vertices_.find(id));
1590 }
1604 if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1605 return findVertex((*ov)->id());
1606 return vertices().end();
1607 }
1609 return vertexIndex_.lookup(key).orElse(vertices().end());
1610 }
1624 return findVertexKey(VertexKey(value));
1625 }
1627 return findVertexKey(VertexKey(value));
1628 }
1635 bool isValidVertex(const ConstVertexIterator &vertex) const {
1636 return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1637 }
1638
1647 boost::iterator_range<EdgeIterator> edges() {
1648 return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1649 EdgeIterator(edges_.nodes().end()));
1650 }
1651 boost::iterator_range<ConstEdgeIterator> edges() const {
1652 return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1653 ConstEdgeIterator(edges_.nodes().end()));
1654 }
1674 boost::iterator_range<EdgeValueIterator> edgeValues() {
1675 return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1676 EdgeValueIterator(edges_.nodes().end()));
1677 }
1678 boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1679 return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1680 ConstEdgeValueIterator(edges_.nodes().end()));
1681 }
1695 return EdgeIterator(edges_.find(id));
1696 }
1697 ConstEdgeIterator findEdge(size_t id) const {
1698 return ConstEdgeIterator(edges_.find(id));
1699 }
1713 if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1714 return findEdge((*oe)->id());
1715 return edges().end();
1716 }
1718 return edgeIndex_.lookup(key).orElse(edges().end());
1719 }
1733 return findEdgeKey(EdgeKey(value));
1734 }
1736 return findEdgeValue(EdgeKey(value));
1737 }
1744 bool isValidEdge(const ConstEdgeIterator &edge) const {
1745 return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1746 }
1747
1754 size_t nVertices() const {
1755 return vertices_.size();
1756 }
1757
1764 size_t nEdges() const {
1765 return edges_.size();
1766 }
1767
1773 bool isEmpty() const {
1774 ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1775 return vertices_.isEmpty();
1776 }
1777
1791 return insertVertexImpl(value, true /*strict*/);
1792 }
1793
1803 return insertVertexImpl(value, false /*non-strict*/);
1804 }
1805
1820 EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1821 const EdgeValue &value = EdgeValue()) {
1822 return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1823 }
1824 EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1825 const EdgeValue &value = EdgeValue()) {
1826 ASSERT_require(isValidVertex(sourceVertex));
1827 ASSERT_require(isValidVertex(targetVertex));
1828 return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1829 }
1842 EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1843 const EdgeValue &value = EdgeValue()) {
1844 return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1845 }
1847 const EdgeValue &value = EdgeValue()) {
1848 ASSERT_require(isValidVertex(sourceVertex));
1849 ASSERT_require(isValidVertex(targetVertex));
1850 return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1851 }
1858 EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1859 const EdgeValue &edgeValue = EdgeValue()) {
1860 VertexIterator source = insertVertexMaybe(sourceValue);
1861 VertexIterator target = insertVertexMaybe(targetValue);
1862 return insertEdge(source, target, edgeValue);
1863 }
1864
1881 ASSERT_require(isValidEdge(edge));
1882 EdgeIterator next = edge; ++next; // advance before we delete edge
1883 edgeIndex_.erase(EdgeKey(edge->value()));
1884 --edge->source_->nOutEdges_;
1885 edge->edgeLists_.remove(OUT_EDGES);
1886 --edge->target_->nInEdges_;
1887 edge->edgeLists_.remove(IN_EDGES);
1888 edges_.eraseAt(edge->self_); // edge is now deleted
1889 return next;
1890 }
1892 ASSERT_require(isValidEdge(edge));
1893 return eraseEdge(findEdge(edge->id()));
1894 }
1907 ASSERT_require(isValidEdge(edge));
1908 VertexIterator source = edge->source();
1909 VertexIterator target = edge->target();
1910 EdgeIterator retval = eraseEdge(edge);
1911 if (source == target) {
1912 if (source->degree() == 0)
1913 eraseVertex(source);
1914 } else {
1915 if (source->degree() == 0)
1916 eraseVertex(source);
1917 if (target->degree() == 0)
1918 eraseVertex(target);
1919 }
1920 return retval;
1921 }
1922
1932 void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1933 ASSERT_require(isValidVertex(source));
1934 ASSERT_require(isValidVertex(target));
1935 if (source->nOutEdges() < target->nInEdges()) {
1936 EdgeIterator iter = source->outEdges().begin();
1937 while (iter != source->outEdges().end()) {
1938 if (iter->target() == target) {
1939 iter = eraseEdge(iter);
1940 } else {
1941 ++iter;
1942 }
1943 }
1944 } else {
1945 EdgeIterator iter = target->inEdges().begin();
1946 while (iter != target->inEdges().end()) {
1947 if (iter->source() == source) {
1948 iter = eraseEdge(iter);
1949 } else {
1950 ++iter;
1951 }
1952 }
1953 }
1954 }
1955 void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1956 ASSERT_require(isValidVertex(source));
1957 ASSERT_require(isValidVertex(target));
1958 eraseEdges(findVertex(source->id()), findVertex(target->id()));
1959 }
1979 ASSERT_require(isValidVertex(vertex));
1980 VertexIterator next = vertex; ++next; // advance before we delete vertex
1981 clearEdges(vertex);
1982 vertexIndex_.erase(VertexKey(vertex->value()));
1983 vertices_.eraseAt(vertex->self_); // vertex is now deleted
1984 return next;
1985 }
1987 ASSERT_require(isValidVertex(vertex));
1988 return eraseVertex(findVertex(vertex->id()));
1989 }
1998 void clearEdges() {
1999 for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
2000 vertex->inEdges().reset();
2001 vertex->outEdges().reset();
2002 }
2003 edges_.clear();
2004 edgeIndex_.clear();
2005 }
2006
2017 void clearEdges(const VertexIterator &vertex) {
2018 clearOutEdges(vertex);
2019 clearInEdges(vertex);
2020 }
2021 void clearEdges(const ConstVertexIterator &vertex) {
2022 clearOutEdges(vertex);
2023 clearInEdges(vertex);
2024 }
2036 void clearOutEdges(const VertexIterator &vertex) {
2037 ASSERT_forbid(vertex==vertices().end());
2038 for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
2039 edge = eraseEdge(edge);
2040 }
2042 ASSERT_forbid(vertex==vertices().end());
2043 clearOutEdges(findVertex(vertex->id()));
2044 }
2056 void clearInEdges(const VertexIterator &vertex) {
2057 ASSERT_forbid(vertex==vertices().end());
2058 for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
2059 edge = eraseEdge(edge);
2060 }
2061 void clearInEdges(const ConstVertexIterator &vertex) {
2062 ASSERT_forbid(vertex==vertices().end());
2063 clearInEdges(findVertex(vertex->id()));
2064 }
2074 void clear() {
2075 edges_.clear();
2076 vertices_.clear();
2077 edgeIndex_.clear();
2078 vertexIndex_.clear();
2079 }
2080
2082 // Internal implementation details
2084private:
2085 VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
2086 const VertexKey key(value);
2087 if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
2088 if (strict)
2089 throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
2090 return findVertex((*found)->id());
2091 }
2092 typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
2093 inserted->value().self_ = inserted;
2094 inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
2095 VertexIterator retval = VertexIterator(inserted);
2096 vertexIndex_.insert(key, retval);
2097 return retval;
2098 }
2099
2100 EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2101 const EdgeValue &value, bool strict) {
2102 const EdgeKey key(value);
2103 ASSERT_require(isValidVertex(sourceVertex));
2104 ASSERT_require(isValidVertex(targetVertex));
2105 if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2106 if (strict)
2107 throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2108 return findEdge((*found)->id());
2109 }
2110 typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
2111 inserted->value().self_ = inserted;
2112 inserted->value().edgeLists_.reset(&inserted->value());
2113 EdgeIterator newEdge(inserted);
2114 sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2115 ++sourceVertex->nOutEdges_;
2116 targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2117 ++targetVertex->nInEdges_;
2118 edgeIndex_.insert(key, newEdge);
2119 return newEdge;
2120 }
2121
2122
2124 // Deprecated stuff
2126public:
2127 // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
2128 typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
2129 typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
2130 typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
2131 typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
2132 typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
2133 typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
2134};
2135
2136} // namespace
2137} // namespace
2138
2139#endif
Map based index is the default index type when indexes are present.
Definition Graph.h:153
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
Definition Graph.h:166
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition Graph.h:180
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
Definition Graph.h:173
void clear()
Erase all data from this index.
Definition Graph.h:159
Type of edge key for graphs that do not index their edges.
Definition Graph.h:102
Hash-based indexing.
Definition Graph.h:193
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
Definition Graph.h:207
void clear()
Erase all data from this index.
Definition Graph.h:200
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
Definition Graph.h:214
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition Graph.h:221
Type of vertex key for graphs that do not index their vertices.
Definition Graph.h:89
Fake index for graphs that don't have an index.
Definition Graph.h:118
void clear()
Erase all data from this index.
Definition Graph.h:123
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition Graph.h:136
void insert(const VertexOrEdgeKey &, const VertexOrEdgeConstIterator &)
Insert a new element into the map.
Definition Graph.h:131
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &) const
Look up iterator for vertex or edge key.
Definition Graph.h:142
Bidirectional edge node iterator.
Definition Graph.h:956
Bidirectional edge value iterator.
Definition Graph.h:1007
Bidirectional vertex node iterator.
Definition Graph.h:1057
Bidirectional vertex value iterator.
Definition Graph.h:1104
Base class for edge iterators.
Definition Graph.h:740
bool operator==(const OtherIter &other) const
Equality predicate.
Definition Graph.h:829
Derived operator++(int)
Increment.
Definition Graph.h:793
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition Graph.h:845
bool isEmpty() const
True if iterator doesn't point to anything.
Definition Graph.h:851
Derived operator--(int)
Decrement.
Definition Graph.h:814
Derived & operator=(const Derived &other)
Assignment.
Definition Graph.h:772
Bidirectional edge node iterator.
Definition Graph.h:931
Bidirectional edge value iterator.
Definition Graph.h:982
EdgeValue & value()
User-defined value.
Definition Graph.h:1188
const VertexIterator & target()
Target vertex.
Definition Graph.h:1174
ConstVertexIterator source() const
Source vertex.
Definition Graph.h:1163
const VertexIterator & source()
Source vertex.
Definition Graph.h:1162
const EdgeValue & value() const
User-defined value.
Definition Graph.h:1189
ConstVertexIterator target() const
Target vertex.
Definition Graph.h:1175
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition Graph.h:1196
const size_t & id() const
Unique edge ID number.
Definition Graph.h:1152
Base class for vertex iterators.
Definition Graph.h:862
bool operator==(const OtherIter &other) const
Equality predicate.
Definition Graph.h:909
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition Graph.h:910
Derived & operator=(const Derived &other)
Assignment.
Definition Graph.h:881
bool isEmpty() const
True if iterator doesn't point to anything.
Definition Graph.h:914
Bidirectional vertex node iterator.
Definition Graph.h:1035
Bidirectional vertex value iterator.
Definition Graph.h:1081
const VertexValue & value() const
User-defined value.
Definition Graph.h:1302
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Definition Graph.h:1236
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
Definition Graph.h:1257
boost::iterator_range< ConstEdgeIterator > outEdges() const
List of outgoing edges.
Definition Graph.h:1262
size_t nInEdges() const
Number of incoming edges.
Definition Graph.h:1272
size_t nOutEdges() const
Number of outgoing edges.
Definition Graph.h:1279
size_t degree() const
Number of incident edges.
Definition Graph.h:1287
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition Graph.h:1241
const size_t & id() const
Unique vertex ID number.
Definition Graph.h:1225
VertexValue & value()
User-defined value.
Definition Graph.h:1301
Graph containing user-defined vertices and edges.
Definition Graph.h:634
E EdgeValue
User-level data associated with edges.
Definition Graph.h:637
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition Graph.h:1842
void clearEdges()
Erase all edges, but leave all vertices.
Definition Graph.h:1998
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition Graph.h:1820
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition Graph.h:1744
EKey EdgeKey
Type for looking up an edge.
Definition Graph.h:639
void clear()
Remove all vertices and edges.
Definition Graph.h:2074
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition Graph.h:1647
ConstEdgeIterator findEdgeKey(const EdgeKey &key) const
Finds an edge given its key.
Definition Graph.h:1717
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition Graph.h:2056
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
Definition Graph.h:1694
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition Graph.h:2017
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition Graph.h:2036
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition Graph.h:1585
VKey VertexKey
Type for looking up a vertex.
Definition Graph.h:638
size_t nVertices() const
Total number of vertices.
Definition Graph.h:1754
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition Graph.h:1880
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition Graph.h:2021
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition Graph.h:2061
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition Graph.h:1846
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition Graph.h:1538
ConstVertexIterator findVertex(size_t id) const
Finds the vertex with specified ID number.
Definition Graph.h:1588
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
Definition Graph.h:1790
void clearOutEdges(const ConstVertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition Graph.h:2041
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition Graph.h:1732
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition Graph.h:1697
ConstVertexIterator findVertexKey(const VertexKey &key) const
Finds a vertex given its key.
Definition Graph.h:1608
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
Definition Graph.h:1635
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition Graph.h:1735
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition Graph.h:1955
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition Graph.h:1678
bool isEmpty() const
True if graph is empty.
Definition Graph.h:1773
Alloc Allocator
Allocator for vertex and edge nodes.
Definition Graph.h:640
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition Graph.h:1986
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition Graph.h:1565
EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue, const EdgeValue &edgeValue=EdgeValue())
Insert an edge and its vertex end points.
Definition Graph.h:1858
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition Graph.h:1712
const Allocator & allocator()
Allocator.
Definition Graph.h:1523
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition Graph.h:1623
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition Graph.h:1626
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition Graph.h:1891
Graph & operator=(const Graph &other)
Assignment.
Definition Graph.h:1488
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition Graph.h:1906
V VertexValue
User-level data associated with vertices.
Definition Graph.h:636
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition Graph.h:1504
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition Graph.h:1932
VertexIterator insertVertexMaybe(const VertexValue &value)
Optionally insert a new vertex.
Definition Graph.h:1802
Graph(const Allocator &allocator=Allocator())
Default constructor.
Definition Graph.h:1450
EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition Graph.h:1824
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition Graph.h:1651
Graph(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other, const Allocator &allocator=Allocator())
Copy constructor.
Definition Graph.h:1476
VertexIterator findVertexKey(const VertexKey &key)
Finds a vertex given its key.
Definition Graph.h:1603
size_t nEdges() const
Total number of edges.
Definition Graph.h:1764
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition Graph.h:1978
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition Graph.h:1542
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition Graph.h:1674
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition Graph.h:1569
Graph(const Graph &other)
Copy constructor.
Definition Graph.h:1462
Doubly-linked list with constant-time indexing.
Definition IndexedList.h:75
Container associating values with keys.
Definition Sawyer/Map.h:72
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition Sawyer/Map.h:602
Map & erase(const Key &key)
Remove a node with specified key.
Definition Sawyer/Map.h:744
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition Sawyer/Map.h:646
Map & clear()
Remove all nodes.
Definition Sawyer/Map.h:732
Error for existing values.
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Sawyer support library.
Traits for vertex and edge indexing.
Definition Graph.h:238
GraphBimapIndex< VertexOrEdgeKey, VertexOrEdgeConstIterator > Index
Type of index to use for the specified key type.
Definition Graph.h:240
Traits for graphs.
Definition Graph.h:284
G::EdgeValueIterator EdgeValueIterator
Const or non-const edge value iterator.
Definition Graph.h:289
G::VertexValueIterator VertexValueIterator
Const or non-const vertex value iterator.
Definition Graph.h:295
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
Definition Graph.h:286
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition Graph.h:292
G::VertexValue VertexValue
User-defined vertex type without connectivity information.
Definition Graph.h:304
static bool allEdges(const Edge &)
Predicate returning true for all edges.
Definition Graph.h:315
static bool allVertices(const Vertex &)
Predicate returning true for all vertices.
Definition Graph.h:310
G::Edge Edge
Edge type including user type and connectivity.
Definition Graph.h:301
G::EdgeValue EdgeValue
User-defined edge type without connectivity information.
Definition Graph.h:307
G::Vertex Vertex
Vertex type including user type and connectivity.
Definition Graph.h:298