ROSE  0.9.10.54
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>
731  class EdgeBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
732  EdgePhase phase_; // IN_EDGES, OUT_EDGES or N_PHASES (graph edges)
733  BaseIter iter_; // EdgeList::NodeIterator or EdgeList::ConstNodeIterator
734  VList *vlist_; // (const) VirtualList<Edge> when phase_ is IN_EDGES or OUT_EDGES
735  protected:
736  friend class Graph;
737  EdgeBaseIterator() {}
738  EdgeBaseIterator(const EdgeBaseIterator &other): phase_(other.phase_), iter_(other.iter_), vlist_(other.vlist_) {}
739  EdgeBaseIterator(const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
740  EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
741  template<class BaseIter2> EdgeBaseIterator(EdgePhase phase, const BaseIter2 &iter, VList *vlist)
742  : phase_(phase), iter_(iter), vlist_(vlist) {}
743 
744  Node& dereference() const {
745  return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
746  }
747 
748  private:
749  Derived* derived() { return static_cast<Derived*>(this); }
750  const Derived* derived() const { return static_cast<const Derived*>(this); }
751 
752  public:
754  Derived& operator=(const Derived &other) {
755  phase_ = other.phase_;
756  iter_ = other.iter_;
757  vlist_ = other.vlist_;
758  return *derived();
759  }
760 
767  Derived& operator++() {
768  if (N_PHASES==phase_) {
769  ++iter_;
770  } else {
771  vlist_ = &vlist_->next(phase_);
772  }
773  return *derived();
774  }
775  Derived operator++(int) {
776  Derived old = *derived();
777  ++*this;
778  return old;
779  }
788  Derived& operator--() {
789  if (N_PHASES==phase_) {
790  --iter_;
791  } else {
792  vlist_ = &vlist_->prev(phase_);
793  }
794  return *derived();
795  }
796  Derived operator--(int) {
797  Derived old = *derived();
798  --*this;
799  return old;
800  }
810  template<class OtherIter>
811  bool operator==(const OtherIter &other) const {
812  Node *a = NULL;
813  if (N_PHASES==phase_) {
814  a = iter_.isAtEnd() ? NULL : &iter_->value();
815  } else {
816  a = vlist_->isHead() ? NULL : &vlist_->dereference();
817  }
818  Node *b = NULL;
819  if (N_PHASES==other.phase_) {
820  b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
821  } else {
822  b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
823  }
824  return a == b;
825  }
826  template<class OtherIter>
827  bool operator!=(const OtherIter &other) const {
828  return !(*this==other);
829  }
833  bool operator<(const EdgeBaseIterator &other) const {
834  Node *a = NULL;
835  if (N_PHASES==phase_) {
836  a = iter_.isAtEnd() ? NULL : &iter_->value();
837  } else {
838  a = vlist_->isHead() ? NULL : &vlist_->dereference();
839  }
840  Node *b = NULL;
841  if (N_PHASES==other.phase_) {
842  b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
843  } else {
844  b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
845  }
846  return a < b;
847  }
848  };
849 
851  template<class Derived, class Value, class Node, class BaseIter>
852  class VertexBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
853  BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
854  protected:
855  friend class Graph;
856  VertexBaseIterator() {}
857  VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
858  VertexBaseIterator(const BaseIter &base): base_(base) {}
859  Node& dereference() const { return base_->value(); }
860  public:
862  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
863 
870  Derived& operator++() { ++base_; return *derived(); }
871  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
880  Derived& operator--() { --base_; return *derived(); }
881  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
889  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
890  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
894  bool operator<(const VertexBaseIterator &other) const { return base_ < other.base_; }
895 
896  private:
897  Derived* derived() { return static_cast<Derived*>(this); }
898  const Derived* derived() const { return static_cast<const Derived*>(this); }
899  };
900 
901 public:
908  class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
909  VirtualList<Edge> > {
910  typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
911  VirtualList<Edge> > Super;
912  public:
913  typedef Edge& Reference;
914  typedef Edge* Pointer;
915  EdgeIterator() {}
916  EdgeIterator(const EdgeIterator &other): Super(other) {}
917  Edge& operator*() const { return this->dereference(); }
918  Edge* operator->() const { return &this->dereference(); }
919  private:
920  friend class Graph;
921  EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
922  EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
923  };
924 
931  class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
932  typename EdgeList::ConstNodeIterator,
933  const VirtualList<Edge> > {
934  typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
935  typename EdgeList::ConstNodeIterator,
936  const VirtualList<Edge> > Super;
937  public:
938  typedef const Edge& Reference;
939  typedef const Edge* Pointer;
940  ConstEdgeIterator() {}
941  ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
942  ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
943  const Edge& operator*() const { return this->dereference(); }
944  const Edge* operator->() const { return &this->dereference(); }
945  private:
946  friend class Graph;
947  ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
948  ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
949  };
958  class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
959  VirtualList<Edge> > {
960  typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
961  VirtualList<Edge> > Super;
962  public:
963  typedef EdgeValue& Reference;
964  typedef EdgeValue* Pointer;
965  EdgeValueIterator() {}
966  EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
967  EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
968  EdgeValue& operator*() const { return this->dereference().value(); }
969  EdgeValue* operator->() const { return &this->dereference().value(); }
970  private:
971  friend class Graph;
972  EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
973  EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
974  };
975 
981  class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
982  typename EdgeList::ConstNodeIterator,
983  const VirtualList<Edge> > {
985  typename EdgeList::ConstNodeIterator,
986  const VirtualList<Edge> > Super;
987  public:
988  typedef const EdgeValue& Reference;
989  typedef const EdgeValue* Pointer;
990  ConstEdgeValueIterator() {}
991  ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
992  ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
993  ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
994  ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
995  const EdgeValue& operator*() const { return this->dereference().value(); }
996  const EdgeValue* operator->() const { return &this->dereference().value(); }
997  private:
998  friend class Graph;
999  ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1000  ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1001  };
1002 
1009  class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1010  typename VertexList::NodeIterator> {
1011  typedef VertexBaseIterator<VertexIterator, Vertex, Vertex,
1012  typename VertexList::NodeIterator> Super;
1013  public:
1014  typedef Vertex& Reference;
1015  typedef Vertex* Pointer;
1016  VertexIterator() {}
1017  VertexIterator(const VertexIterator &other): Super(other) {}
1018  Vertex& operator*() const { return this->dereference(); }
1019  Vertex* operator->() const { return &this->dereference(); }
1020  private:
1021  friend class Graph;
1022  VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1023  };
1024 
1030  class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1031  typename VertexList::ConstNodeIterator> {
1032  typedef VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1033  typename VertexList::ConstNodeIterator> Super;
1034  public:
1035  typedef const Vertex& Reference;
1036  typedef const Vertex* Pointer;
1037  ConstVertexIterator() {}
1038  ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1039  ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1040  const Vertex& operator*() const { return this->dereference(); }
1041  const Vertex* operator->() const { return &this->dereference(); }
1042  private:
1043  friend class Graph;
1044  ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1045  };
1046 
1053  class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1054  typename VertexList::NodeIterator> {
1056  typename VertexList::NodeIterator> Super;
1057  public:
1058  typedef VertexValue& Reference;
1059  typedef VertexValue* Pointer;
1060  VertexValueIterator() {}
1061  VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1062  VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1063  VertexValue& operator*() const { return this->dereference().value(); }
1064  VertexValue* operator->() const { return &this->dereference().value(); }
1065  private:
1066  friend class Graph;
1067  VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1068  };
1069 
1075  class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1076  typename VertexList::ConstNodeIterator> {
1078  typename VertexList::ConstNodeIterator> Super;
1079  public:
1080  typedef const VertexValue& Reference;
1081  typedef const VertexValue* Pointer;
1082  ConstVertexValueIterator() {}
1083  ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
1084  ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1085  ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1086  ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1087  const VertexValue& operator*() const { return this->dereference().value(); }
1088  const VertexValue* operator->() const { return &this->dereference().value(); }
1089  private:
1090  friend class Graph;
1091  ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1092  };
1093 
1094 
1096  // Storage nodes
1098 public:
1099 
1104  class Edge {
1105  VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1106  EdgeValue value_; // user-defined data for each edge
1107  typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1108  VertexIterator source_, target_; // starting and ending points of the edge are always required
1109  private:
1110  friend class Graph;
1111  Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
1112  : value_(value), source_(source), target_(target) {}
1113  public:
1123  const size_t& id() const { return self_->id(); }
1124 
1133  const VertexIterator& source() { return source_; }
1134  ConstVertexIterator source() const { return source_; }
1145  const VertexIterator& target() { return target_; }
1146  ConstVertexIterator target() const { return target_; }
1159  EdgeValue& value() { return value_; }
1160  const EdgeValue& value() const { return value_; }
1167  bool isSelfEdge() const {
1168  return source_ == target_;
1169  }
1170  };
1171 
1176  class Vertex {
1177  VertexValue value_; // user data for this vertex
1178  typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1179  VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1180  size_t nInEdges_; // number of incoming edges
1181  size_t nOutEdges_; // number of outgoing edges
1182  private:
1183  friend class Graph;
1184  Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1185  public:
1196  const size_t& id() const { return self_->id(); }
1197 
1207  boost::iterator_range<EdgeIterator> inEdges() {
1208  EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1209  EdgeIterator end(IN_EDGES, &edgeLists_);
1210  return boost::iterator_range<EdgeIterator>(begin, end);
1211  }
1212  boost::iterator_range<ConstEdgeIterator> inEdges() const {
1213  ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1214  ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1215  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1216  }
1228  boost::iterator_range<EdgeIterator> outEdges() {
1229  EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1230  EdgeIterator end(OUT_EDGES, &edgeLists_);
1231  return boost::iterator_range<EdgeIterator>(begin, end);
1232  }
1233  boost::iterator_range<ConstEdgeIterator> outEdges() const {
1234  ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1235  ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1236  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1237  }
1243  size_t nInEdges() const {
1244  return nInEdges_;
1245  }
1246 
1250  size_t nOutEdges() const {
1251  return nOutEdges_;
1252  }
1253 
1258  size_t degree() const {
1259  return nInEdges_ + nOutEdges_;
1260  }
1261 
1272  VertexValue& value() { return value_; }
1273  const VertexValue& value() const { return value_; }
1275  };
1276 
1277 private:
1278  typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
1279  typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1280 
1281  EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1282  VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1283  EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1284  VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1285 
1287  // Serialization
1289 private:
1290  friend class boost::serialization::access;
1291 
1292  struct SerializableEdge {
1293  size_t srcId, tgtId;
1294  EdgeValue value;
1295 
1296  SerializableEdge()
1297  : srcId(-1), tgtId(-1) {}
1298 
1299  SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1300  : srcId(srcId), tgtId(tgtId), value(value) {}
1301 
1302  template<class S>
1303  void serialize(S &s, const unsigned /*version*/) {
1304  s & BOOST_SERIALIZATION_NVP(srcId);
1305  s & BOOST_SERIALIZATION_NVP(tgtId);
1306  s & BOOST_SERIALIZATION_NVP(value);
1307  }
1308  };
1309 
1310  template<class S>
1311  void save(S &s, const unsigned /*version*/) const {
1312  size_t nv = nVertices();
1313  s <<BOOST_SERIALIZATION_NVP(nv);
1314  for (size_t i=0; i<nv; ++i)
1315  s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
1316 
1317  size_t ne = nEdges();
1318  s <<BOOST_SERIALIZATION_NVP(ne);
1319  for (size_t i=0; i<ne; ++i) {
1320  ConstEdgeIterator edge = findEdge(i);
1321  SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1322  s <<BOOST_SERIALIZATION_NVP(se);
1323  }
1324  }
1325 
1326  template<class S>
1327  void load(S &s, const unsigned /*version*/) {
1328  clear();
1329  size_t nv = 0;
1330  s >>BOOST_SERIALIZATION_NVP(nv);
1331  for (size_t i=0; i<nv; ++i) {
1332  VertexValue vv;
1333  s >>boost::serialization::make_nvp("vertex", vv);
1334  insertVertex(vv);
1335  }
1336 
1337  size_t ne = 0;
1338  s >>BOOST_SERIALIZATION_NVP(ne);
1339  for (size_t i=0; i<ne; ++i) {
1340  SerializableEdge se;
1341  s >>BOOST_SERIALIZATION_NVP(se);
1342  ASSERT_require(se.srcId < nv && se.tgtId < nv);
1343  insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1344  }
1345  }
1346 
1347  BOOST_SERIALIZATION_SPLIT_MEMBER();
1348 
1349 
1351  // Initialization
1353 public:
1354 
1360  Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1361 
1372  Graph(const Graph &other)
1373  : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1374  *this = other;
1375  }
1376 
1385  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1386  Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
1387  : edges_(allocator), vertices_(allocator) {
1388  *this = other;
1389  }
1390 
1398  Graph& operator=(const Graph &other) {
1399  return operator=<V, E>(other);
1400  }
1401 
1413  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1415  clear();
1416  for (size_t i=0; i<other.nVertices(); ++i) {
1418  VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1419  ASSERT_require(inserted->id() == i);
1420  }
1421  for (size_t i=0; i<other.nEdges(); ++i) {
1423  VertexIterator vsrc = findVertex(edge->source()->id());
1424  VertexIterator vtgt = findVertex(edge->target()->id());
1425  insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1426  }
1427  return *this;
1428  }
1429 
1433  const Allocator& allocator() {
1434  return vertices_.allocator();
1435  }
1436 
1438 public:
1439 
1448  boost::iterator_range<VertexIterator> vertices() {
1449  return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1450  VertexIterator(vertices_.nodes().end()));
1451  }
1452  boost::iterator_range<ConstVertexIterator> vertices() const {
1453  return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1454  ConstVertexIterator(vertices_.nodes().end()));
1455  }
1475  boost::iterator_range<VertexValueIterator> vertexValues() {
1476  return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1477  VertexValueIterator(vertices_.nodes().end()));
1478  }
1479  boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1480  return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1481  ConstVertexValueIterator(vertices_.nodes().end()));
1482  }
1495  VertexIterator findVertex(size_t id) {
1496  return VertexIterator(vertices_.find(id));
1497  }
1498  ConstVertexIterator findVertex(size_t id) const {
1499  return ConstVertexIterator(vertices_.find(id));
1500  }
1513  VertexIterator findVertexKey(const VertexKey &key) {
1514  if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1515  return findVertex((*ov)->id());
1516  return vertices().end();
1517  }
1518  ConstVertexIterator findVertexKey(const VertexKey &key) const {
1519  return vertexIndex_.lookup(key).orElse(vertices().end());
1520  }
1533  VertexIterator findVertexValue(const VertexValue &value) {
1534  return findVertexKey(VertexKey(value));
1535  }
1536  ConstVertexIterator findVertexValue(const VertexValue &value) const {
1537  return findVertexKey(VertexKey(value));
1538  }
1545  bool isValidVertex(const ConstVertexIterator &vertex) const {
1546  return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1547  }
1548 
1557  boost::iterator_range<EdgeIterator> edges() {
1558  return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1559  EdgeIterator(edges_.nodes().end()));
1560  }
1561  boost::iterator_range<ConstEdgeIterator> edges() const {
1562  return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1563  ConstEdgeIterator(edges_.nodes().end()));
1564  }
1584  boost::iterator_range<EdgeValueIterator> edgeValues() {
1585  return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1586  EdgeValueIterator(edges_.nodes().end()));
1587  }
1588  boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1589  return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1590  ConstEdgeValueIterator(edges_.nodes().end()));
1591  }
1604  EdgeIterator findEdge(size_t id) {
1605  return EdgeIterator(edges_.find(id));
1606  }
1607  ConstEdgeIterator findEdge(size_t id) const {
1608  return ConstEdgeIterator(edges_.find(id));
1609  }
1622  EdgeIterator findEdgeKey(const EdgeKey &key) {
1623  if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1624  return findEdge((*oe)->id());
1625  return edges().end();
1626  }
1627  ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
1628  return edgeIndex_.lookup(key).orElse(edges().end());
1629  }
1642  EdgeIterator findEdgeValue(const EdgeValue &value) {
1643  return findEdgeKey(EdgeKey(value));
1644  }
1645  ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
1646  return findEdgeValue(EdgeKey(value));
1647  }
1654  bool isValidEdge(const ConstEdgeIterator &edge) const {
1655  return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1656  }
1657 
1664  size_t nVertices() const {
1665  return vertices_.size();
1666  }
1667 
1674  size_t nEdges() const {
1675  return edges_.size();
1676  }
1677 
1683  bool isEmpty() const {
1684  ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1685  return vertices_.isEmpty();
1686  }
1687 
1700  VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
1701  return insertVertexImpl(value, true /*strict*/);
1702  }
1703 
1712  VertexIterator insertVertexMaybe(const VertexValue &value) {
1713  return insertVertexImpl(value, false /*non-strict*/);
1714  }
1715 
1730  EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1731  const EdgeValue &value = EdgeValue()) {
1732  return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1733  }
1734  EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1735  const EdgeValue &value = EdgeValue()) {
1736  ASSERT_require(isValidVertex(sourceVertex));
1737  ASSERT_require(isValidVertex(targetVertex));
1738  return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1739  }
1752  EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1753  const EdgeValue &value = EdgeValue()) {
1754  return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1755  }
1756  EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1757  const EdgeValue &value = EdgeValue()) {
1758  ASSERT_require(isValidVertex(sourceVertex));
1759  ASSERT_require(isValidVertex(targetVertex));
1760  return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1761  }
1768  EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1769  const EdgeValue &edgeValue = EdgeValue()) {
1770  VertexIterator source = insertVertexMaybe(sourceValue);
1771  VertexIterator target = insertVertexMaybe(targetValue);
1772  return insertEdge(source, target, edgeValue);
1773  }
1774 
1790  EdgeIterator eraseEdge(const EdgeIterator &edge) {
1791  ASSERT_require(isValidEdge(edge));
1792  EdgeIterator next = edge; ++next; // advance before we delete edge
1793  edgeIndex_.erase(EdgeKey(edge->value()));
1794  --edge->source_->nOutEdges_;
1795  edge->edgeLists_.remove(OUT_EDGES);
1796  --edge->target_->nInEdges_;
1797  edge->edgeLists_.remove(IN_EDGES);
1798  edges_.eraseAt(edge->self_); // edge is now deleted
1799  return next;
1800  }
1801  EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
1802  ASSERT_require(isValidEdge(edge));
1803  return eraseEdge(findEdge(edge->id()));
1804  }
1816  EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
1817  ASSERT_require(isValidEdge(edge));
1818  VertexIterator source = edge->source();
1819  VertexIterator target = edge->target();
1820  EdgeIterator retval = eraseEdge(edge);
1821  if (source == target) {
1822  if (source->degree() == 0)
1823  eraseVertex(source);
1824  } else {
1825  if (source->degree() == 0)
1826  eraseVertex(source);
1827  if (target->degree() == 0)
1828  eraseVertex(target);
1829  }
1830  return retval;
1831  }
1832 
1842  void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1843  ASSERT_require(isValidVertex(source));
1844  ASSERT_require(isValidVertex(target));
1845  if (source->nOutEdges() < target->nInEdges()) {
1846  EdgeIterator iter = source->outEdges().begin();
1847  while (iter != source->outEdges().end()) {
1848  if (iter->target() == target) {
1849  iter = eraseEdge(iter);
1850  } else {
1851  ++iter;
1852  }
1853  }
1854  } else {
1855  EdgeIterator iter = target->inEdges().begin();
1856  while (iter != target->inEdges().end()) {
1857  if (iter->source() == source) {
1858  iter = eraseEdge(iter);
1859  } else {
1860  ++iter;
1861  }
1862  }
1863  }
1864  }
1865  void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1866  ASSERT_require(isValidVertex(source));
1867  ASSERT_require(isValidVertex(target));
1868  eraseEdges(findVertex(source->id()), findVertex(target->id()));
1869  }
1888  VertexIterator eraseVertex(const VertexIterator &vertex) {
1889  ASSERT_require(isValidVertex(vertex));
1890  VertexIterator next = vertex; ++next; // advance before we delete vertex
1891  clearEdges(vertex);
1892  vertexIndex_.erase(VertexKey(vertex->value()));
1893  vertices_.eraseAt(vertex->self_); // vertex is now deleted
1894  return next;
1895  }
1896  VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
1897  ASSERT_require(isValidVertex(vertex));
1898  return eraseVertex(findVertex(vertex->id()));
1899  }
1908  void clearEdges() {
1909  for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
1910  vertex->inEdges().reset();
1911  vertex->outEdges().reset();
1912  }
1913  edges_.clear();
1914  edgeIndex_.clear();
1915  }
1916 
1927  void clearEdges(const VertexIterator &vertex) {
1928  clearOutEdges(vertex);
1929  clearInEdges(vertex);
1930  }
1931  void clearEdges(const ConstVertexIterator &vertex) {
1932  clearOutEdges(vertex);
1933  clearInEdges(vertex);
1934  }
1946  void clearOutEdges(const VertexIterator &vertex) {
1947  ASSERT_forbid(vertex==vertices().end());
1948  for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
1949  edge = eraseEdge(edge);
1950  }
1951  void clearOutEdges(const ConstVertexIterator &vertex) {
1952  ASSERT_forbid(vertex==vertices().end());
1953  clearOutEdges(findVertex(vertex->id()));
1954  }
1966  void clearInEdges(const VertexIterator &vertex) {
1967  ASSERT_forbid(vertex==vertices().end());
1968  for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
1969  edge = eraseEdge(edge);
1970  }
1971  void clearInEdges(const ConstVertexIterator &vertex) {
1972  ASSERT_forbid(vertex==vertices().end());
1973  clearInEdges(findVertex(vertex->id()));
1974  }
1984  void clear() {
1985  edges_.clear();
1986  vertices_.clear();
1987  edgeIndex_.clear();
1988  vertexIndex_.clear();
1989  }
1990 
1992  // Internal implementation details
1994 private:
1995  VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
1996  const VertexKey key(value);
1997  if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
1998  if (strict)
1999  throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
2000  return findVertex((*found)->id());
2001  }
2002  typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
2003  inserted->value().self_ = inserted;
2004  inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
2005  VertexIterator retval = VertexIterator(inserted);
2006  vertexIndex_.insert(key, retval);
2007  return retval;
2008  }
2009 
2010  EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2011  const EdgeValue &value, bool strict) {
2012  const EdgeKey key(value);
2013  ASSERT_require(isValidVertex(sourceVertex));
2014  ASSERT_require(isValidVertex(targetVertex));
2015  if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2016  if (strict)
2017  throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2018  return findEdge((*found)->id());
2019  }
2020  typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
2021  inserted->value().self_ = inserted;
2022  inserted->value().edgeLists_.reset(&inserted->value());
2023  EdgeIterator newEdge(inserted);
2024  sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2025  ++sourceVertex->nOutEdges_;
2026  targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2027  ++targetVertex->nInEdges_;
2028  edgeIndex_.insert(key, newEdge);
2029  return newEdge;
2030  }
2031 
2032 
2034  // Deprecated stuff
2036 public:
2037  // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
2038  typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
2039  typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
2040  typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
2041  typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
2042  typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
2043  typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
2044 };
2045 
2046 } // namespace
2047 } // namespace
2048 
2049 #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:827
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1664
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1946
Derived operator++(int)
Increment.
Definition: Graph.h:775
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition: Graph.h:1816
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition: Graph.h:1645
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1908
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:1700
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1196
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1888
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1123
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:1518
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:486
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1674
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:811
G::Edge Edge
Edge type including user type and connectivity.
Definition: Graph.h:304
Bidirectional edge value iterator.
Definition: Graph.h:958
Bidirectional vertex node iterator.
Definition: Graph.h:1009
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition: Graph.h:1479
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1896
const EdgeValue & value() const
User-defined value.
Definition: Graph.h:1160
Bidirectional edge value iterator.
Definition: Graph.h:981
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:1207
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:1545
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition: Graph.h:183
Derived & operator--()
Decrement.
Definition: Graph.h:880
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1801
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:1734
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:862
VertexValue & value()
User-defined value.
Definition: Graph.h:1272
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition: Graph.h:1654
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition: Graph.h:1212
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition: Graph.h:1533
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition: Graph.h:1452
Holds a value or nothing.
Definition: Optional.h:49
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition: Graph.h:1414
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1927
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:1448
Bidirectional vertex value iterator.
Definition: Graph.h:1075
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1842
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1730
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1966
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition: Graph.h:1642
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition: Graph.h:1584
Bidirectional vertex node iterator.
Definition: Graph.h:1030
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition: Graph.h:139
Graph(const Graph &other)
Copy constructor.
Definition: Graph.h:1372
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: Access.h:13
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1752
Base class for vertex iterators.
Definition: Graph.h:852
bool operator<(const EdgeBaseIterator &other) const
Iterator comparison.
Definition: Graph.h:833
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:754
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:1228
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:1712
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1971
const VertexIterator & source()
Source vertex.
Definition: Graph.h:1133
EdgeValue & value()
User-defined value.
Definition: Graph.h:1159
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition: Graph.h:1588
void clear()
Erase all data from this index.
Definition: Graph.h:203
Derived & operator++()
Increment.
Definition: Graph.h:767
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:890
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition: Graph.h:1607
ConstVertexIterator source() const
Source vertex.
Definition: Graph.h:1134
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1865
Derived operator++(int)
Increment.
Definition: Graph.h:871
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:1768
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:1513
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition: Graph.h:1475
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1495
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:1498
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:1053
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:1627
void clear()
Remove all vertices and edges.
Definition: Graph.h:1984
size_t degree() const
Number of incident edges.
Definition: Graph.h:1258
bool operator<(const VertexBaseIterator &other) const
Iterator comparison.
Definition: Graph.h:894
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition: Graph.h:1622
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:1604
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:1233
size_t nInEdges() const
Number of incoming edges.
Definition: Graph.h:1243
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1931
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:628
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:530
Bidirectional edge node iterator.
Definition: Graph.h:931
Bidirectional edge node iterator.
Definition: Graph.h:908
const Allocator & allocator()
Allocator.
Definition: Graph.h:1433
Derived & operator--()
Decrement.
Definition: Graph.h:788
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:1360
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
size_t nOutEdges() const
Number of outgoing edges.
Definition: Graph.h:1250
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition: Graph.h:1536
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1756
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition: Graph.h:1561
Derived operator--(int)
Decrement.
Definition: Graph.h:796
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:1557
bool isEmpty() const
True if graph is empty.
Definition: Graph.h:1683
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:889
Graph & operator=(const Graph &other)
Assignment.
Definition: Graph.h:1398
Derived & operator++()
Increment.
Definition: Graph.h:870
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1790
ConstVertexIterator target() const
Target vertex.
Definition: Graph.h:1146
const VertexIterator & target()
Target vertex.
Definition: Graph.h:1145
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:1386
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:1951
Derived operator--(int)
Decrement.
Definition: Graph.h:881
const VertexValue & value() const
User-defined value.
Definition: Graph.h:1273
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition: Graph.h:1167