ROSE  0.11.101.0
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://github.com/matzke1/sawyer.
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/serialization/access.hpp>
20 #include <boost/serialization/nvp.hpp>
21 #include <boost/serialization/split_member.hpp>
22 #include <boost/unordered_map.hpp>
23 #include <ostream>
24 #if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
25 #include <iomanip>
26 #endif
27 
28 namespace Sawyer {
29 namespace Container {
30 
81 // Special vertex and edge key types.
84 
91 template<class VertexValue>
93 public:
94  GraphVertexNoKey() {}
95  explicit GraphVertexNoKey(const VertexValue&) {}
96 };
97 
104 template<class EdgeValue>
106 public:
107  GraphEdgeNoKey() {}
108  explicit GraphEdgeNoKey(const EdgeValue&) {}
109 };
110 
112 // Special vertex and edge indexing types.
114 
120 template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
122 public:
126  void clear() {}
127 
134  void insert(const VertexOrEdgeKey&, const VertexOrEdgeConstIterator&) {}
135 
139  void erase(const VertexOrEdgeKey&) {}
140 
145  Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey&) const {
146  return Nothing();
147  }
148 };
149 
155 template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
158 public:
162  void clear() {
163  map_.clear();
164  }
165 
169  void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
170  map_.insert(key, iter); // Unlike std::map, Sawyer's "insert" always inserts
171  }
172 
176  void erase(const VertexOrEdgeKey &key) {
177  map_.erase(key);
178  }
179 
183  Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
184  return map_.getOptional(key);
185  }
186 };
187 
195 template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
197  typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator> Map;
198  Map map_;
199 public:
203  void clear() {
204  map_.clear();
205  }
206 
210  void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter) {
211  map_[key] = iter;
212  }
213 
217  void erase(const VertexOrEdgeKey &key) {
218  map_.erase(key);
219  }
220 
224  Optional<VertexOrEdgeConstIterator> lookup(const VertexOrEdgeKey &key) const {
225  typename Map::const_iterator found = map_.find(key);
226  if (found == map_.end())
227  return Nothing();
228  return found->second;
229  }
230 };
231 
240 template<class VertexOrEdgeKey, class VertexOrEdgeConstIterator>
244 };
245 
246 // Partial specialization for when there is no vertex index
247 template<class VertexValue, class ConstVertexIterator>
248 struct GraphIndexTraits<GraphVertexNoKey<VertexValue>, ConstVertexIterator> {
249  typedef GraphVoidIndex<GraphVertexNoKey<VertexValue>, ConstVertexIterator> Index;
250 };
251 
252 // Partial specialization for when there is no edge index.
253 template<class EdgeValue, class ConstEdgeIterator>
254 struct GraphIndexTraits<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> {
255  typedef GraphVoidIndex<GraphEdgeNoKey<EdgeValue>, ConstEdgeIterator> Index;
256 };
257 
258 // A #define so users that don't understand C++ templates can still get by. See GraphIndexTraits doc for details.
259 // Must be used at global scope.
260 #define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE) \
261  namespace Sawyer { \
262  namespace Container { \
263  template<class VertexOrEdgeConstIterator> \
264  struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
265  typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index; \
266  }; \
267  } \
268  }
269 
270 #define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE) \
271  namespace Sawyer { \
272  namespace Container { \
273  template<class VertexOrEdgeConstIterator> \
274  struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
275  typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index; \
276  }; \
277  } \
278  }
279 
280 
282 // Graph traits
284 
286 template<class G>
287 struct GraphTraits {
289  typedef typename G::EdgeIterator EdgeIterator;
290 
292  typedef typename G::EdgeValueIterator EdgeValueIterator;
293 
295  typedef typename G::VertexIterator VertexIterator;
296 
298  typedef typename G::VertexValueIterator VertexValueIterator;
299 
301  typedef typename G::Vertex Vertex;
302 
304  typedef typename G::Edge Edge;
305 
307  typedef typename G::VertexValue VertexValue;
308 
310  typedef typename G::EdgeValue EdgeValue;
311 };
312 
313 // GraphTraits specialization for const graphs.
314 template<class G>
315 struct GraphTraits<const G> {
316  typedef typename G::ConstEdgeIterator EdgeIterator;
317  typedef typename G::ConstEdgeValueIterator EdgeValueIterator;
318  typedef typename G::ConstVertexIterator VertexIterator;
319  typedef typename G::ConstVertexValueIterator VertexValueIterator;
320  typedef const typename G::Vertex Vertex;
321  typedef const typename G::Edge Edge;
322  typedef const typename G::VertexValue VertexValue;
323  typedef const typename G::EdgeValue EdgeValue;
324 };
325 
622 template<class V = Nothing, class E = Nothing,
623  class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>,
624  class Alloc = DefaultAllocator>
625 class Graph {
626 public:
627  typedef V VertexValue;
628  typedef E EdgeValue;
629  typedef VKey VertexKey;
630  typedef EKey EdgeKey;
631  typedef Alloc Allocator;
632  class Vertex;
633  class Edge;
635 private:
636  enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
637  typedef IndexedList<Edge, Allocator> EdgeList;
638  typedef IndexedList<Vertex, Allocator> VertexList;
639 
640  template<class T>
641  class VirtualList {
642  VirtualList *next_[N_PHASES];
643  VirtualList *prev_[N_PHASES];
644  T *node_;
645  public:
646  VirtualList() {
647  reset(NULL);
648  }
649 
650  void reset(T* node) {
651  node_ = node;
652  for (size_t i=0; i<N_PHASES; ++i)
653  next_[i] = prev_[i] = this;
654  }
655 
656  bool isHead() const {
657  return node_ == NULL;
658  }
659 
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;
664  }
665 
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;
670  }
671 
672  void insert(EdgePhase phase, VirtualList *newNode) { // insert newNode before this
673  ASSERT_require(phase < N_PHASES);
674  ASSERT_not_null(newNode);
675  ASSERT_forbid(newNode->isHead());
676  ASSERT_require(newNode->isSingleton(phase)); // cannot be part of another sublist already
677  prev_[phase]->next_[phase] = newNode;
678  newNode->prev_[phase] = prev_[phase];
679  prev_[phase] = newNode;
680  newNode->next_[phase] = this;
681  }
682 
683  void remove(EdgePhase phase) { // Remove this node from the list
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;
689  }
690 
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]; }
695 
696  T& dereference() { // Return the Edge to which this VirtualList node belongs
697  ASSERT_forbid(isHead()); // list head contains no user-data
698  return *(T*)this; // depends on VirtualList being at the beginning of Edge
699  }
700 
701  const T& dereference() const {
702  ASSERT_forbid(isHead());
703  return *(const T*)this;
704  }
705 
706 #if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
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";
713  do {
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);
720  }
721 #endif
722  };
723 
725  // Iterators
727 public: // public only for the sake of doxygen
730  template<class Derived, class Value, class Node, class BaseIter, class VList>
732  public:
733  // Five standard iterator types
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&;
739 
740  private:
741  EdgePhase phase_; // IN_EDGES, OUT_EDGES or N_PHASES (graph edges)
742  BaseIter iter_; // EdgeList::NodeIterator or EdgeList::ConstNodeIterator
743  VList *vlist_; // (const) VirtualList<Edge> when phase_ is IN_EDGES or OUT_EDGES
744  protected:
745  friend class Graph;
746  EdgeBaseIterator() {}
747  EdgeBaseIterator(const EdgeBaseIterator &other): phase_(other.phase_), iter_(other.iter_), vlist_(other.vlist_) {}
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) {}
752 
753  Node& dereference() const {
754  return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
755  }
756 
757  private:
758  Derived* derived() { return static_cast<Derived*>(this); }
759  const Derived* derived() const { return static_cast<const Derived*>(this); }
760 
761  public:
763  Derived& operator=(const Derived &other) {
764  phase_ = other.phase_;
765  iter_ = other.iter_;
766  vlist_ = other.vlist_;
767  return *derived();
768  }
769 
776  Derived& operator++() {
777  if (N_PHASES==phase_) {
778  ++iter_;
779  } else {
780  vlist_ = &vlist_->next(phase_);
781  }
782  return *derived();
783  }
784  Derived operator++(int) {
785  Derived old = *derived();
786  ++*this;
787  return old;
788  }
797  Derived& operator--() {
798  if (N_PHASES==phase_) {
799  --iter_;
800  } else {
801  vlist_ = &vlist_->prev(phase_);
802  }
803  return *derived();
804  }
805  Derived operator--(int) {
806  Derived old = *derived();
807  --*this;
808  return old;
809  }
819  template<class OtherIter>
820  bool operator==(const OtherIter &other) const {
821  Node *a = NULL;
822  if (N_PHASES==phase_) {
823  a = iter_.isAtEnd() ? NULL : &iter_->value();
824  } else {
825  a = vlist_->isHead() ? NULL : &vlist_->dereference();
826  }
827  Node *b = NULL;
828  if (N_PHASES==other.phase_) {
829  b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
830  } else {
831  b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
832  }
833  return a == b;
834  }
835  template<class OtherIter>
836  bool operator!=(const OtherIter &other) const {
837  return !(*this==other);
838  }
842  bool isEmpty() const {
843  if (N_PHASES == phase_) {
844  return iter_.isAtEnd();
845  } else {
846  return vlist_->isHead();
847  }
848  }
849  };
850 
852  template<class Derived, class Value, class Node, class BaseIter>
854  public:
855  // Five standard iterator types
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&;
861 
862  private:
863  BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
864  protected:
865  friend class Graph;
866  VertexBaseIterator() {}
867  VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
868  VertexBaseIterator(const BaseIter &base): base_(base) {}
869  Node& dereference() const { return base_->value(); }
870  public:
872  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
873 
880  Derived& operator++() { ++base_; return *derived(); }
881  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
890  Derived& operator--() { --base_; return *derived(); }
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_; }
904  bool isEmpty() const {
905  return base_.base() == NULL;
906  }
907 
908  private:
909  Derived* derived() { return static_cast<Derived*>(this); }
910  const Derived* derived() const { return static_cast<const Derived*>(this); }
911  };
912 
913 public:
920  class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
921  VirtualList<Edge> > {
922  typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
923  VirtualList<Edge> > Super;
924  public:
925  typedef Edge& Reference;
926  typedef Edge* Pointer;
927  EdgeIterator() {}
928  EdgeIterator(const EdgeIterator &other): Super(other) {}
929  Edge& operator*() const { return this->dereference(); }
930  Edge* operator->() const { return &this->dereference(); }
931  private:
932  friend class Graph;
933  EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
934  EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
935  };
936 
943  class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
944  typename EdgeList::ConstNodeIterator,
945  const VirtualList<Edge> > {
946  typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
947  typename EdgeList::ConstNodeIterator,
948  const VirtualList<Edge> > Super;
949  public:
950  typedef const Edge& Reference;
951  typedef const Edge* Pointer;
952  ConstEdgeIterator() {}
953  ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
954  ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
955  const Edge& operator*() const { return this->dereference(); }
956  const Edge* operator->() const { return &this->dereference(); }
957  private:
958  friend class Graph;
959  ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
960  ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
961  };
970  class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
971  VirtualList<Edge> > {
972  typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
973  VirtualList<Edge> > Super;
974  public:
975  typedef EdgeValue& Reference;
976  typedef EdgeValue* Pointer;
977  EdgeValueIterator() {}
978  EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
979  EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
980  EdgeValue& operator*() const { return this->dereference().value(); }
981  EdgeValue* operator->() const { return &this->dereference().value(); }
982  private:
983  friend class Graph;
984  EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
985  EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
986  };
987 
993  class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
994  typename EdgeList::ConstNodeIterator,
995  const VirtualList<Edge> > {
997  typename EdgeList::ConstNodeIterator,
998  const VirtualList<Edge> > Super;
999  public:
1000  typedef const EdgeValue& Reference;
1001  typedef const EdgeValue* Pointer;
1002  ConstEdgeValueIterator() {}
1003  ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
1004  ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1005  ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1006  ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1007  const EdgeValue& operator*() const { return this->dereference().value(); }
1008  const EdgeValue* operator->() const { return &this->dereference().value(); }
1009  private:
1010  friend class Graph;
1011  ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1012  ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1013  };
1014 
1021  class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1022  typename VertexList::NodeIterator> {
1023  typedef VertexBaseIterator<VertexIterator, Vertex, Vertex,
1024  typename VertexList::NodeIterator> Super;
1025  public:
1026  typedef Vertex& Reference;
1027  typedef Vertex* Pointer;
1028  VertexIterator() {}
1029  VertexIterator(const VertexIterator &other): Super(other) {}
1030  Vertex& operator*() const { return this->dereference(); }
1031  Vertex* operator->() const { return &this->dereference(); }
1032  private:
1033  friend class Graph;
1034  VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1035  };
1036 
1042  class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1043  typename VertexList::ConstNodeIterator> {
1044  typedef VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1045  typename VertexList::ConstNodeIterator> Super;
1046  public:
1047  typedef const Vertex& Reference;
1048  typedef const Vertex* Pointer;
1049  ConstVertexIterator() {}
1050  ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1051  ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1052  const Vertex& operator*() const { return this->dereference(); }
1053  const Vertex* operator->() const { return &this->dereference(); }
1054  private:
1055  friend class Graph;
1056  ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1057  };
1058 
1065  class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1066  typename VertexList::NodeIterator> {
1068  typename VertexList::NodeIterator> Super;
1069  public:
1070  typedef VertexValue& Reference;
1071  typedef VertexValue* Pointer;
1072  VertexValueIterator() {}
1073  VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1074  VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1075  VertexValue& operator*() const { return this->dereference().value(); }
1076  VertexValue* operator->() const { return &this->dereference().value(); }
1077  private:
1078  friend class Graph;
1079  VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1080  };
1081 
1087  class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1088  typename VertexList::ConstNodeIterator> {
1090  typename VertexList::ConstNodeIterator> Super;
1091  public:
1092  typedef const VertexValue& Reference;
1093  typedef const VertexValue* Pointer;
1094  ConstVertexValueIterator() {}
1095  ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
1096  ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1097  ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1098  ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1099  const VertexValue& operator*() const { return this->dereference().value(); }
1100  const VertexValue* operator->() const { return &this->dereference().value(); }
1101  private:
1102  friend class Graph;
1103  ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1104  };
1105 
1106 
1108  // Storage nodes
1110 public:
1111 
1116  class Edge {
1117  VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1118  EdgeValue value_; // user-defined data for each edge
1119  typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1120  VertexIterator source_, target_; // starting and ending points of the edge are always required
1121  private:
1122  friend class Graph;
1123  Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
1124  : value_(value), source_(source), target_(target) {}
1125  public:
1135  const size_t& id() const { return self_->id(); }
1136 
1145  const VertexIterator& source() { return source_; }
1146  ConstVertexIterator source() const { return source_; }
1157  const VertexIterator& target() { return target_; }
1158  ConstVertexIterator target() const { return target_; }
1171  EdgeValue& value() { return value_; }
1172  const EdgeValue& value() const { return value_; }
1179  bool isSelfEdge() const {
1180  return source_ == target_;
1181  }
1182  };
1183 
1188  class Vertex {
1189  VertexValue value_; // user data for this vertex
1190  typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1191  VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1192  size_t nInEdges_; // number of incoming edges
1193  size_t nOutEdges_; // number of outgoing edges
1194  private:
1195  friend class Graph;
1196  Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1197  public:
1208  const size_t& id() const { return self_->id(); }
1209 
1219  boost::iterator_range<EdgeIterator> inEdges() {
1220  EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1221  EdgeIterator end(IN_EDGES, &edgeLists_);
1222  return boost::iterator_range<EdgeIterator>(begin, end);
1223  }
1224  boost::iterator_range<ConstEdgeIterator> inEdges() const {
1225  ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1226  ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1227  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1228  }
1240  boost::iterator_range<EdgeIterator> outEdges() {
1241  EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1242  EdgeIterator end(OUT_EDGES, &edgeLists_);
1243  return boost::iterator_range<EdgeIterator>(begin, end);
1244  }
1245  boost::iterator_range<ConstEdgeIterator> outEdges() const {
1246  ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1247  ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1248  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1249  }
1255  size_t nInEdges() const {
1256  return nInEdges_;
1257  }
1258 
1262  size_t nOutEdges() const {
1263  return nOutEdges_;
1264  }
1265 
1270  size_t degree() const {
1271  return nInEdges_ + nOutEdges_;
1272  }
1273 
1284  VertexValue& value() { return value_; }
1285  const VertexValue& value() const { return value_; }
1287  };
1288 
1289 private:
1290  typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
1291  typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1292 
1293  EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1294  VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1295  EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1296  VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1297 
1299  // Serialization
1301 private:
1302  friend class boost::serialization::access;
1303 
1304  struct SerializableEdge {
1305  size_t srcId, tgtId;
1306  EdgeValue value;
1307 
1308  SerializableEdge()
1309  : srcId(-1), tgtId(-1) {}
1310 
1311  SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1312  : srcId(srcId), tgtId(tgtId), value(value) {}
1313 
1314  template<class S>
1315  void serialize(S &s, const unsigned /*version*/) {
1316  s & BOOST_SERIALIZATION_NVP(srcId);
1317  s & BOOST_SERIALIZATION_NVP(tgtId);
1318  s & BOOST_SERIALIZATION_NVP(value);
1319  }
1320  };
1321 
1322  template<class S>
1323  void save(S &s, const unsigned /*version*/) const {
1324  size_t nv = nVertices();
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());
1328 
1329  size_t ne = nEdges();
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);
1335  }
1336  }
1337 
1338  template<class S>
1339  void load(S &s, const unsigned /*version*/) {
1340  clear();
1341  size_t nv = 0;
1342  s >>BOOST_SERIALIZATION_NVP(nv);
1343  for (size_t i=0; i<nv; ++i) {
1344  VertexValue vv;
1345  s >>boost::serialization::make_nvp("vertex", vv);
1346  insertVertex(vv);
1347  }
1348 
1349  size_t ne = 0;
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);
1355  insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1356  }
1357  }
1358 
1359  BOOST_SERIALIZATION_SPLIT_MEMBER();
1360 
1361 
1363  // Initialization
1365 public:
1366 
1372  Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1373 
1384  Graph(const Graph &other)
1385  : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1386  *this = other;
1387  }
1388 
1397  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1398  Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
1399  : edges_(allocator), vertices_(allocator) {
1400  *this = other;
1401  }
1402 
1410  Graph& operator=(const Graph &other) {
1411  return operator=<V, E>(other);
1412  }
1413 
1425  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1427  clear();
1428  for (size_t i=0; i<other.nVertices(); ++i) {
1430  VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1431  ASSERT_require(inserted->id() == i);
1432  }
1433  for (size_t i=0; i<other.nEdges(); ++i) {
1435  VertexIterator vsrc = findVertex(edge->source()->id());
1436  VertexIterator vtgt = findVertex(edge->target()->id());
1437  insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1438  }
1439  return *this;
1440  }
1441 
1445  const Allocator& allocator() {
1446  return vertices_.allocator();
1447  }
1448 
1450 public:
1451 
1460  boost::iterator_range<VertexIterator> vertices() {
1461  return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1462  VertexIterator(vertices_.nodes().end()));
1463  }
1464  boost::iterator_range<ConstVertexIterator> vertices() const {
1465  return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1466  ConstVertexIterator(vertices_.nodes().end()));
1467  }
1487  boost::iterator_range<VertexValueIterator> vertexValues() {
1488  return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1489  VertexValueIterator(vertices_.nodes().end()));
1490  }
1491  boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1492  return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1493  ConstVertexValueIterator(vertices_.nodes().end()));
1494  }
1507  VertexIterator findVertex(size_t id) {
1508  return VertexIterator(vertices_.find(id));
1509  }
1510  ConstVertexIterator findVertex(size_t id) const {
1511  return ConstVertexIterator(vertices_.find(id));
1512  }
1525  VertexIterator findVertexKey(const VertexKey &key) {
1526  if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1527  return findVertex((*ov)->id());
1528  return vertices().end();
1529  }
1530  ConstVertexIterator findVertexKey(const VertexKey &key) const {
1531  return vertexIndex_.lookup(key).orElse(vertices().end());
1532  }
1545  VertexIterator findVertexValue(const VertexValue &value) {
1546  return findVertexKey(VertexKey(value));
1547  }
1548  ConstVertexIterator findVertexValue(const VertexValue &value) const {
1549  return findVertexKey(VertexKey(value));
1550  }
1557  bool isValidVertex(const ConstVertexIterator &vertex) const {
1558  return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1559  }
1560 
1569  boost::iterator_range<EdgeIterator> edges() {
1570  return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1571  EdgeIterator(edges_.nodes().end()));
1572  }
1573  boost::iterator_range<ConstEdgeIterator> edges() const {
1574  return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1575  ConstEdgeIterator(edges_.nodes().end()));
1576  }
1596  boost::iterator_range<EdgeValueIterator> edgeValues() {
1597  return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1598  EdgeValueIterator(edges_.nodes().end()));
1599  }
1600  boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1601  return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1602  ConstEdgeValueIterator(edges_.nodes().end()));
1603  }
1616  EdgeIterator findEdge(size_t id) {
1617  return EdgeIterator(edges_.find(id));
1618  }
1619  ConstEdgeIterator findEdge(size_t id) const {
1620  return ConstEdgeIterator(edges_.find(id));
1621  }
1634  EdgeIterator findEdgeKey(const EdgeKey &key) {
1635  if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1636  return findEdge((*oe)->id());
1637  return edges().end();
1638  }
1639  ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
1640  return edgeIndex_.lookup(key).orElse(edges().end());
1641  }
1654  EdgeIterator findEdgeValue(const EdgeValue &value) {
1655  return findEdgeKey(EdgeKey(value));
1656  }
1657  ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
1658  return findEdgeValue(EdgeKey(value));
1659  }
1666  bool isValidEdge(const ConstEdgeIterator &edge) const {
1667  return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1668  }
1669 
1676  size_t nVertices() const {
1677  return vertices_.size();
1678  }
1679 
1686  size_t nEdges() const {
1687  return edges_.size();
1688  }
1689 
1695  bool isEmpty() const {
1696  ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1697  return vertices_.isEmpty();
1698  }
1699 
1712  VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
1713  return insertVertexImpl(value, true /*strict*/);
1714  }
1715 
1724  VertexIterator insertVertexMaybe(const VertexValue &value) {
1725  return insertVertexImpl(value, false /*non-strict*/);
1726  }
1727 
1742  EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1743  const EdgeValue &value = EdgeValue()) {
1744  return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1745  }
1746  EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1747  const EdgeValue &value = EdgeValue()) {
1748  ASSERT_require(isValidVertex(sourceVertex));
1749  ASSERT_require(isValidVertex(targetVertex));
1750  return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1751  }
1764  EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1765  const EdgeValue &value = EdgeValue()) {
1766  return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1767  }
1768  EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1769  const EdgeValue &value = EdgeValue()) {
1770  ASSERT_require(isValidVertex(sourceVertex));
1771  ASSERT_require(isValidVertex(targetVertex));
1772  return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1773  }
1780  EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1781  const EdgeValue &edgeValue = EdgeValue()) {
1782  VertexIterator source = insertVertexMaybe(sourceValue);
1783  VertexIterator target = insertVertexMaybe(targetValue);
1784  return insertEdge(source, target, edgeValue);
1785  }
1786 
1802  EdgeIterator eraseEdge(const EdgeIterator &edge) {
1803  ASSERT_require(isValidEdge(edge));
1804  EdgeIterator next = edge; ++next; // advance before we delete edge
1805  edgeIndex_.erase(EdgeKey(edge->value()));
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_); // edge is now deleted
1811  return next;
1812  }
1813  EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
1814  ASSERT_require(isValidEdge(edge));
1815  return eraseEdge(findEdge(edge->id()));
1816  }
1828  EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
1829  ASSERT_require(isValidEdge(edge));
1830  VertexIterator source = edge->source();
1831  VertexIterator target = edge->target();
1832  EdgeIterator retval = eraseEdge(edge);
1833  if (source == target) {
1834  if (source->degree() == 0)
1835  eraseVertex(source);
1836  } else {
1837  if (source->degree() == 0)
1838  eraseVertex(source);
1839  if (target->degree() == 0)
1840  eraseVertex(target);
1841  }
1842  return retval;
1843  }
1844 
1854  void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1855  ASSERT_require(isValidVertex(source));
1856  ASSERT_require(isValidVertex(target));
1857  if (source->nOutEdges() < target->nInEdges()) {
1858  EdgeIterator iter = source->outEdges().begin();
1859  while (iter != source->outEdges().end()) {
1860  if (iter->target() == target) {
1861  iter = eraseEdge(iter);
1862  } else {
1863  ++iter;
1864  }
1865  }
1866  } else {
1867  EdgeIterator iter = target->inEdges().begin();
1868  while (iter != target->inEdges().end()) {
1869  if (iter->source() == source) {
1870  iter = eraseEdge(iter);
1871  } else {
1872  ++iter;
1873  }
1874  }
1875  }
1876  }
1877  void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1878  ASSERT_require(isValidVertex(source));
1879  ASSERT_require(isValidVertex(target));
1880  eraseEdges(findVertex(source->id()), findVertex(target->id()));
1881  }
1900  VertexIterator eraseVertex(const VertexIterator &vertex) {
1901  ASSERT_require(isValidVertex(vertex));
1902  VertexIterator next = vertex; ++next; // advance before we delete vertex
1903  clearEdges(vertex);
1904  vertexIndex_.erase(VertexKey(vertex->value()));
1905  vertices_.eraseAt(vertex->self_); // vertex is now deleted
1906  return next;
1907  }
1908  VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
1909  ASSERT_require(isValidVertex(vertex));
1910  return eraseVertex(findVertex(vertex->id()));
1911  }
1920  void clearEdges() {
1921  for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
1922  vertex->inEdges().reset();
1923  vertex->outEdges().reset();
1924  }
1925  edges_.clear();
1926  edgeIndex_.clear();
1927  }
1928 
1939  void clearEdges(const VertexIterator &vertex) {
1940  clearOutEdges(vertex);
1941  clearInEdges(vertex);
1942  }
1943  void clearEdges(const ConstVertexIterator &vertex) {
1944  clearOutEdges(vertex);
1945  clearInEdges(vertex);
1946  }
1958  void clearOutEdges(const VertexIterator &vertex) {
1959  ASSERT_forbid(vertex==vertices().end());
1960  for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
1961  edge = eraseEdge(edge);
1962  }
1963  void clearOutEdges(const ConstVertexIterator &vertex) {
1964  ASSERT_forbid(vertex==vertices().end());
1965  clearOutEdges(findVertex(vertex->id()));
1966  }
1978  void clearInEdges(const VertexIterator &vertex) {
1979  ASSERT_forbid(vertex==vertices().end());
1980  for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
1981  edge = eraseEdge(edge);
1982  }
1983  void clearInEdges(const ConstVertexIterator &vertex) {
1984  ASSERT_forbid(vertex==vertices().end());
1985  clearInEdges(findVertex(vertex->id()));
1986  }
1996  void clear() {
1997  edges_.clear();
1998  vertices_.clear();
1999  edgeIndex_.clear();
2000  vertexIndex_.clear();
2001  }
2002 
2004  // Internal implementation details
2006 private:
2007  VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
2008  const VertexKey key(value);
2009  if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
2010  if (strict)
2011  throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
2012  return findVertex((*found)->id());
2013  }
2014  typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
2015  inserted->value().self_ = inserted;
2016  inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
2017  VertexIterator retval = VertexIterator(inserted);
2018  vertexIndex_.insert(key, retval);
2019  return retval;
2020  }
2021 
2022  EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2023  const EdgeValue &value, bool strict) {
2024  const EdgeKey key(value);
2025  ASSERT_require(isValidVertex(sourceVertex));
2026  ASSERT_require(isValidVertex(targetVertex));
2027  if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2028  if (strict)
2029  throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2030  return findEdge((*found)->id());
2031  }
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);
2041  return newEdge;
2042  }
2043 
2044 
2046  // Deprecated stuff
2048 public:
2049  // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
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");
2056 };
2057 
2058 } // namespace
2059 } // namespace
2060 
2061 #endif
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &) const
Look up iterator for vertex or edge key.
Definition: Graph.h:145
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:836
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1676
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1958
Derived operator++(int)
Increment.
Definition: Graph.h:784
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition: Graph.h:1828
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition: Graph.h:1657
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1920
void clear()
Erase all data from this index.
Definition: Graph.h:126
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
Definition: Graph.h:1712
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1208
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1900
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1135
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
ConstVertexIterator findVertexKey(const VertexKey &key) const
Finds a vertex given its key.
Definition: Graph.h:1530
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:559
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1686
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:820
G::Edge Edge
Edge type including user type and connectivity.
Definition: Graph.h:304
Bidirectional edge value iterator.
Definition: Graph.h:970
Bidirectional vertex node iterator.
Definition: Graph.h:1021
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition: Graph.h:1491
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1908
const EdgeValue & value() const
User-defined value.
Definition: Graph.h:1172
Bidirectional edge value iterator.
Definition: Graph.h:993
Traits for graphs.
Definition: Graph.h:287
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
Definition: Graph.h:217
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Definition: Graph.h:1219
Alloc Allocator
Allocator for vertex and edge nodes.
Definition: Graph.h:631
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
Definition: Graph.h:1557
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition: Graph.h:183
bool isEmpty() const
True if iterator doesn't point to anything.
Definition: Graph.h:842
Derived & operator--()
Decrement.
Definition: Graph.h:890
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1813
VKey VertexKey
Type for looking up a vertex.
Definition: Graph.h:629
EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1746
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:872
VertexValue & value()
User-defined value.
Definition: Graph.h:1284
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition: Graph.h:1666
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition: Graph.h:1224
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition: Graph.h:1545
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition: Graph.h:1464
Holds a value or nothing.
Definition: Optional.h:49
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition: Graph.h:1426
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1939
void clear()
Erase all data from this index.
Definition: Graph.h:162
Type of vertex key for graphs that do not index their vertices.
Definition: Graph.h:92
Default allocator.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1460
Bidirectional vertex value iterator.
Definition: Graph.h:1087
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1854
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1742
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:689
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1978
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition: Graph.h:1654
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition: Graph.h:1596
Bidirectional vertex node iterator.
Definition: Graph.h:1042
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition: Graph.h:139
Graph(const Graph &other)
Copy constructor.
Definition: Graph.h:1384
G::Vertex Vertex
Vertex type including user type and connectivity.
Definition: Graph.h:301
Traits for vertex and edge indexing.
Definition: Graph.h:241
Name space for the entire library.
Definition: FeasiblePath.h:773
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1764
Base class for vertex iterators.
Definition: Graph.h:853
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:763
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
Definition: Graph.h:210
Hash-based indexing.
Definition: Graph.h:196
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
Definition: Graph.h:1240
GraphBimapIndex< VertexOrEdgeKey, VertexOrEdgeConstIterator > Index
Type of index to use for the specified key type.
Definition: Graph.h:243
G::VertexValueIterator VertexValueIterator
Const or non-const vertex value iterator.
Definition: Graph.h:298
VertexIterator insertVertexMaybe(const VertexValue &value)
Optionally insert a new vertex.
Definition: Graph.h:1724
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1983
const VertexIterator & source()
Source vertex.
Definition: Graph.h:1145
EdgeValue & value()
User-defined value.
Definition: Graph.h:1171
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition: Graph.h:1600
void clear()
Erase all data from this index.
Definition: Graph.h:203
Derived & operator++()
Increment.
Definition: Graph.h:776
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:900
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition: Graph.h:1619
ConstVertexIterator source() const
Source vertex.
Definition: Graph.h:1146
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1877
bool isEmpty() const
True if iterator doesn't point to anything.
Definition: Graph.h:904
Derived operator++(int)
Increment.
Definition: Graph.h:881
const char * EdgePhase(int64_t)
Convert Sawyer::Container::Graph::EdgePhase enum constant to a string.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition: Graph.h:224
EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue, const EdgeValue &edgeValue=EdgeValue())
Insert an edge and its vertex end points.
Definition: Graph.h:1780
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
Definition: Graph.h:289
VertexIterator findVertexKey(const VertexKey &key)
Finds a vertex given its key.
Definition: Graph.h:1525
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition: Graph.h:1487
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1507
G::VertexValue VertexValue
User-defined vertex type without connectivity information.
Definition: Graph.h:307
ConstVertexIterator findVertex(size_t id) const
Finds the vertex with specified ID number.
Definition: Graph.h:1510
G::EdgeValue EdgeValue
User-defined edge type without connectivity information.
Definition: Graph.h:310
Error for existing values.
Bidirectional vertex value iterator.
Definition: Graph.h:1065
Extends std::map with methods that return optional values.
Definition: Map.h:10
Map based index is the default index type when indexes are present.
Definition: Graph.h:156
ConstEdgeIterator findEdgeKey(const EdgeKey &key) const
Finds an edge given its key.
Definition: Graph.h:1639
void clear()
Remove all vertices and edges.
Definition: Graph.h:1996
size_t degree() const
Number of incident edges.
Definition: Graph.h:1270
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition: Graph.h:1634
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
Definition: Graph.h:169
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
Definition: Graph.h:1616
Fake index for graphs that don't have an index.
Definition: Graph.h:121
boost::iterator_range< ConstEdgeIterator > outEdges() const
List of outgoing edges.
Definition: Graph.h:1245
size_t nInEdges() const
Number of incoming edges.
Definition: Graph.h:1255
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1943
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:701
Type of edge key for graphs that do not index their edges.
Definition: Graph.h:105
Base class for edge iterators.
Definition: Graph.h:731
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:603
Bidirectional edge node iterator.
Definition: Graph.h:943
Bidirectional edge node iterator.
Definition: Graph.h:920
const Allocator & allocator()
Allocator.
Definition: Graph.h:1445
Derived & operator--()
Decrement.
Definition: Graph.h:797
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
Definition: Graph.h:176
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition: Graph.h:295
Graph(const Allocator &allocator=Allocator())
Default constructor.
Definition: Graph.h:1372
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
size_t nOutEdges() const
Number of outgoing edges.
Definition: Graph.h:1262
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition: Graph.h:1548
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1768
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition: Graph.h:1573
Derived operator--(int)
Decrement.
Definition: Graph.h:805
Represents no value.
Definition: Optional.h:32
EKey EdgeKey
Type for looking up an edge.
Definition: Graph.h:630
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition: Graph.h:1569
bool isEmpty() const
True if graph is empty.
Definition: Graph.h:1695
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:899
Graph & operator=(const Graph &other)
Assignment.
Definition: Graph.h:1410
Derived & operator++()
Increment.
Definition: Graph.h:880
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1802
ConstVertexIterator target() const
Target vertex.
Definition: Graph.h:1158
const VertexIterator & target()
Target vertex.
Definition: Graph.h:1157
G::EdgeValueIterator EdgeValueIterator
Const or non-const edge value iterator.
Definition: Graph.h:292
Graph(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other, const Allocator &allocator=Allocator())
Copy constructor.
Definition: Graph.h:1398
void insert(const VertexOrEdgeKey &, const VertexOrEdgeConstIterator &)
Insert a new element into the map.
Definition: Graph.h:134
E EdgeValue
User-level data associated with edges.
Definition: Graph.h:628
void clearOutEdges(const ConstVertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1963
Derived operator--(int)
Decrement.
Definition: Graph.h:891
const VertexValue & value() const
User-defined value.
Definition: Graph.h:1285
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition: Graph.h:1179