ROSE  0.9.11.56
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 
850  bool isEmpty() const {
851  if (N_PHASES == phase_) {
852  return iter_.isAtEnd();
853  } else {
854  return vlist_->isHead();
855  }
856  }
857  };
858 
860  template<class Derived, class Value, class Node, class BaseIter>
861  class VertexBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
862  BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
863  protected:
864  friend class Graph;
865  VertexBaseIterator() {}
866  VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
867  VertexBaseIterator(const BaseIter &base): base_(base) {}
868  Node& dereference() const { return base_->value(); }
869  public:
871  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
872 
879  Derived& operator++() { ++base_; return *derived(); }
880  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
889  Derived& operator--() { --base_; return *derived(); }
890  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
898  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
899  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
903  bool operator<(const VertexBaseIterator &other) const { return base_ < other.base_; }
904 
906  bool isEmpty() const {
907  return base_.base() == NULL;
908  }
909 
910  private:
911  Derived* derived() { return static_cast<Derived*>(this); }
912  const Derived* derived() const { return static_cast<const Derived*>(this); }
913  };
914 
915 public:
922  class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
923  VirtualList<Edge> > {
924  typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
925  VirtualList<Edge> > Super;
926  public:
927  typedef Edge& Reference;
928  typedef Edge* Pointer;
929  EdgeIterator() {}
930  EdgeIterator(const EdgeIterator &other): Super(other) {}
931  Edge& operator*() const { return this->dereference(); }
932  Edge* operator->() const { return &this->dereference(); }
933  private:
934  friend class Graph;
935  EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
936  EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
937  };
938 
945  class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
946  typename EdgeList::ConstNodeIterator,
947  const VirtualList<Edge> > {
948  typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
949  typename EdgeList::ConstNodeIterator,
950  const VirtualList<Edge> > Super;
951  public:
952  typedef const Edge& Reference;
953  typedef const Edge* Pointer;
954  ConstEdgeIterator() {}
955  ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
956  ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
957  const Edge& operator*() const { return this->dereference(); }
958  const Edge* operator->() const { return &this->dereference(); }
959  private:
960  friend class Graph;
961  ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
962  ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
963  };
972  class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
973  VirtualList<Edge> > {
974  typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
975  VirtualList<Edge> > Super;
976  public:
977  typedef EdgeValue& Reference;
978  typedef EdgeValue* Pointer;
979  EdgeValueIterator() {}
980  EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
981  EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
982  EdgeValue& operator*() const { return this->dereference().value(); }
983  EdgeValue* operator->() const { return &this->dereference().value(); }
984  private:
985  friend class Graph;
986  EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
987  EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
988  };
989 
995  class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
996  typename EdgeList::ConstNodeIterator,
997  const VirtualList<Edge> > {
999  typename EdgeList::ConstNodeIterator,
1000  const VirtualList<Edge> > Super;
1001  public:
1002  typedef const EdgeValue& Reference;
1003  typedef const EdgeValue* Pointer;
1004  ConstEdgeValueIterator() {}
1005  ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
1006  ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1007  ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1008  ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1009  const EdgeValue& operator*() const { return this->dereference().value(); }
1010  const EdgeValue* operator->() const { return &this->dereference().value(); }
1011  private:
1012  friend class Graph;
1013  ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1014  ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1015  };
1016 
1023  class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1024  typename VertexList::NodeIterator> {
1025  typedef VertexBaseIterator<VertexIterator, Vertex, Vertex,
1026  typename VertexList::NodeIterator> Super;
1027  public:
1028  typedef Vertex& Reference;
1029  typedef Vertex* Pointer;
1030  VertexIterator() {}
1031  VertexIterator(const VertexIterator &other): Super(other) {}
1032  Vertex& operator*() const { return this->dereference(); }
1033  Vertex* operator->() const { return &this->dereference(); }
1034  private:
1035  friend class Graph;
1036  VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1037  };
1038 
1044  class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1045  typename VertexList::ConstNodeIterator> {
1046  typedef VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1047  typename VertexList::ConstNodeIterator> Super;
1048  public:
1049  typedef const Vertex& Reference;
1050  typedef const Vertex* Pointer;
1051  ConstVertexIterator() {}
1052  ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1053  ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1054  const Vertex& operator*() const { return this->dereference(); }
1055  const Vertex* operator->() const { return &this->dereference(); }
1056  private:
1057  friend class Graph;
1058  ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1059  };
1060 
1067  class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1068  typename VertexList::NodeIterator> {
1070  typename VertexList::NodeIterator> Super;
1071  public:
1072  typedef VertexValue& Reference;
1073  typedef VertexValue* Pointer;
1074  VertexValueIterator() {}
1075  VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1076  VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1077  VertexValue& operator*() const { return this->dereference().value(); }
1078  VertexValue* operator->() const { return &this->dereference().value(); }
1079  private:
1080  friend class Graph;
1081  VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1082  };
1083 
1089  class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1090  typename VertexList::ConstNodeIterator> {
1092  typename VertexList::ConstNodeIterator> Super;
1093  public:
1094  typedef const VertexValue& Reference;
1095  typedef const VertexValue* Pointer;
1096  ConstVertexValueIterator() {}
1097  ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
1098  ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1099  ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1100  ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1101  const VertexValue& operator*() const { return this->dereference().value(); }
1102  const VertexValue* operator->() const { return &this->dereference().value(); }
1103  private:
1104  friend class Graph;
1105  ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1106  };
1107 
1108 
1110  // Storage nodes
1112 public:
1113 
1118  class Edge {
1119  VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1120  EdgeValue value_; // user-defined data for each edge
1121  typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1122  VertexIterator source_, target_; // starting and ending points of the edge are always required
1123  private:
1124  friend class Graph;
1125  Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
1126  : value_(value), source_(source), target_(target) {}
1127  public:
1137  const size_t& id() const { return self_->id(); }
1138 
1147  const VertexIterator& source() { return source_; }
1148  ConstVertexIterator source() const { return source_; }
1159  const VertexIterator& target() { return target_; }
1160  ConstVertexIterator target() const { return target_; }
1173  EdgeValue& value() { return value_; }
1174  const EdgeValue& value() const { return value_; }
1181  bool isSelfEdge() const {
1182  return source_ == target_;
1183  }
1184  };
1185 
1190  class Vertex {
1191  VertexValue value_; // user data for this vertex
1192  typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1193  VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1194  size_t nInEdges_; // number of incoming edges
1195  size_t nOutEdges_; // number of outgoing edges
1196  private:
1197  friend class Graph;
1198  Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1199  public:
1210  const size_t& id() const { return self_->id(); }
1211 
1221  boost::iterator_range<EdgeIterator> inEdges() {
1222  EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1223  EdgeIterator end(IN_EDGES, &edgeLists_);
1224  return boost::iterator_range<EdgeIterator>(begin, end);
1225  }
1226  boost::iterator_range<ConstEdgeIterator> inEdges() const {
1227  ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1228  ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1229  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1230  }
1242  boost::iterator_range<EdgeIterator> outEdges() {
1243  EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1244  EdgeIterator end(OUT_EDGES, &edgeLists_);
1245  return boost::iterator_range<EdgeIterator>(begin, end);
1246  }
1247  boost::iterator_range<ConstEdgeIterator> outEdges() const {
1248  ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1249  ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1250  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1251  }
1257  size_t nInEdges() const {
1258  return nInEdges_;
1259  }
1260 
1264  size_t nOutEdges() const {
1265  return nOutEdges_;
1266  }
1267 
1272  size_t degree() const {
1273  return nInEdges_ + nOutEdges_;
1274  }
1275 
1286  VertexValue& value() { return value_; }
1287  const VertexValue& value() const { return value_; }
1289  };
1290 
1291 private:
1292  typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
1293  typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1294 
1295  EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1296  VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1297  EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1298  VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1299 
1301  // Serialization
1303 private:
1304  friend class boost::serialization::access;
1305 
1306  struct SerializableEdge {
1307  size_t srcId, tgtId;
1308  EdgeValue value;
1309 
1310  SerializableEdge()
1311  : srcId(-1), tgtId(-1) {}
1312 
1313  SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1314  : srcId(srcId), tgtId(tgtId), value(value) {}
1315 
1316  template<class S>
1317  void serialize(S &s, const unsigned /*version*/) {
1318  s & BOOST_SERIALIZATION_NVP(srcId);
1319  s & BOOST_SERIALIZATION_NVP(tgtId);
1320  s & BOOST_SERIALIZATION_NVP(value);
1321  }
1322  };
1323 
1324  template<class S>
1325  void save(S &s, const unsigned /*version*/) const {
1326  size_t nv = nVertices();
1327  s <<BOOST_SERIALIZATION_NVP(nv);
1328  for (size_t i=0; i<nv; ++i)
1329  s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
1330 
1331  size_t ne = nEdges();
1332  s <<BOOST_SERIALIZATION_NVP(ne);
1333  for (size_t i=0; i<ne; ++i) {
1334  ConstEdgeIterator edge = findEdge(i);
1335  SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1336  s <<BOOST_SERIALIZATION_NVP(se);
1337  }
1338  }
1339 
1340  template<class S>
1341  void load(S &s, const unsigned /*version*/) {
1342  clear();
1343  size_t nv = 0;
1344  s >>BOOST_SERIALIZATION_NVP(nv);
1345  for (size_t i=0; i<nv; ++i) {
1346  VertexValue vv;
1347  s >>boost::serialization::make_nvp("vertex", vv);
1348  insertVertex(vv);
1349  }
1350 
1351  size_t ne = 0;
1352  s >>BOOST_SERIALIZATION_NVP(ne);
1353  for (size_t i=0; i<ne; ++i) {
1354  SerializableEdge se;
1355  s >>BOOST_SERIALIZATION_NVP(se);
1356  ASSERT_require(se.srcId < nv && se.tgtId < nv);
1357  insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1358  }
1359  }
1360 
1361  BOOST_SERIALIZATION_SPLIT_MEMBER();
1362 
1363 
1365  // Initialization
1367 public:
1368 
1374  Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1375 
1386  Graph(const Graph &other)
1387  : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1388  *this = other;
1389  }
1390 
1399  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1400  Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
1401  : edges_(allocator), vertices_(allocator) {
1402  *this = other;
1403  }
1404 
1412  Graph& operator=(const Graph &other) {
1413  return operator=<V, E>(other);
1414  }
1415 
1427  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1429  clear();
1430  for (size_t i=0; i<other.nVertices(); ++i) {
1432  VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1433  ASSERT_require(inserted->id() == i);
1434  }
1435  for (size_t i=0; i<other.nEdges(); ++i) {
1437  VertexIterator vsrc = findVertex(edge->source()->id());
1438  VertexIterator vtgt = findVertex(edge->target()->id());
1439  insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1440  }
1441  return *this;
1442  }
1443 
1447  const Allocator& allocator() {
1448  return vertices_.allocator();
1449  }
1450 
1452 public:
1453 
1462  boost::iterator_range<VertexIterator> vertices() {
1463  return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1464  VertexIterator(vertices_.nodes().end()));
1465  }
1466  boost::iterator_range<ConstVertexIterator> vertices() const {
1467  return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1468  ConstVertexIterator(vertices_.nodes().end()));
1469  }
1489  boost::iterator_range<VertexValueIterator> vertexValues() {
1490  return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1491  VertexValueIterator(vertices_.nodes().end()));
1492  }
1493  boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1494  return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1495  ConstVertexValueIterator(vertices_.nodes().end()));
1496  }
1509  VertexIterator findVertex(size_t id) {
1510  return VertexIterator(vertices_.find(id));
1511  }
1512  ConstVertexIterator findVertex(size_t id) const {
1513  return ConstVertexIterator(vertices_.find(id));
1514  }
1527  VertexIterator findVertexKey(const VertexKey &key) {
1528  if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1529  return findVertex((*ov)->id());
1530  return vertices().end();
1531  }
1532  ConstVertexIterator findVertexKey(const VertexKey &key) const {
1533  return vertexIndex_.lookup(key).orElse(vertices().end());
1534  }
1547  VertexIterator findVertexValue(const VertexValue &value) {
1548  return findVertexKey(VertexKey(value));
1549  }
1550  ConstVertexIterator findVertexValue(const VertexValue &value) const {
1551  return findVertexKey(VertexKey(value));
1552  }
1559  bool isValidVertex(const ConstVertexIterator &vertex) const {
1560  return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1561  }
1562 
1571  boost::iterator_range<EdgeIterator> edges() {
1572  return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1573  EdgeIterator(edges_.nodes().end()));
1574  }
1575  boost::iterator_range<ConstEdgeIterator> edges() const {
1576  return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1577  ConstEdgeIterator(edges_.nodes().end()));
1578  }
1598  boost::iterator_range<EdgeValueIterator> edgeValues() {
1599  return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1600  EdgeValueIterator(edges_.nodes().end()));
1601  }
1602  boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1603  return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1604  ConstEdgeValueIterator(edges_.nodes().end()));
1605  }
1618  EdgeIterator findEdge(size_t id) {
1619  return EdgeIterator(edges_.find(id));
1620  }
1621  ConstEdgeIterator findEdge(size_t id) const {
1622  return ConstEdgeIterator(edges_.find(id));
1623  }
1636  EdgeIterator findEdgeKey(const EdgeKey &key) {
1637  if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1638  return findEdge((*oe)->id());
1639  return edges().end();
1640  }
1641  ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
1642  return edgeIndex_.lookup(key).orElse(edges().end());
1643  }
1656  EdgeIterator findEdgeValue(const EdgeValue &value) {
1657  return findEdgeKey(EdgeKey(value));
1658  }
1659  ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
1660  return findEdgeValue(EdgeKey(value));
1661  }
1668  bool isValidEdge(const ConstEdgeIterator &edge) const {
1669  return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1670  }
1671 
1678  size_t nVertices() const {
1679  return vertices_.size();
1680  }
1681 
1688  size_t nEdges() const {
1689  return edges_.size();
1690  }
1691 
1697  bool isEmpty() const {
1698  ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1699  return vertices_.isEmpty();
1700  }
1701 
1714  VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
1715  return insertVertexImpl(value, true /*strict*/);
1716  }
1717 
1726  VertexIterator insertVertexMaybe(const VertexValue &value) {
1727  return insertVertexImpl(value, false /*non-strict*/);
1728  }
1729 
1744  EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1745  const EdgeValue &value = EdgeValue()) {
1746  return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1747  }
1748  EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1749  const EdgeValue &value = EdgeValue()) {
1750  ASSERT_require(isValidVertex(sourceVertex));
1751  ASSERT_require(isValidVertex(targetVertex));
1752  return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1753  }
1766  EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1767  const EdgeValue &value = EdgeValue()) {
1768  return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1769  }
1770  EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1771  const EdgeValue &value = EdgeValue()) {
1772  ASSERT_require(isValidVertex(sourceVertex));
1773  ASSERT_require(isValidVertex(targetVertex));
1774  return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1775  }
1782  EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1783  const EdgeValue &edgeValue = EdgeValue()) {
1784  VertexIterator source = insertVertexMaybe(sourceValue);
1785  VertexIterator target = insertVertexMaybe(targetValue);
1786  return insertEdge(source, target, edgeValue);
1787  }
1788 
1804  EdgeIterator eraseEdge(const EdgeIterator &edge) {
1805  ASSERT_require(isValidEdge(edge));
1806  EdgeIterator next = edge; ++next; // advance before we delete edge
1807  edgeIndex_.erase(EdgeKey(edge->value()));
1808  --edge->source_->nOutEdges_;
1809  edge->edgeLists_.remove(OUT_EDGES);
1810  --edge->target_->nInEdges_;
1811  edge->edgeLists_.remove(IN_EDGES);
1812  edges_.eraseAt(edge->self_); // edge is now deleted
1813  return next;
1814  }
1815  EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
1816  ASSERT_require(isValidEdge(edge));
1817  return eraseEdge(findEdge(edge->id()));
1818  }
1830  EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
1831  ASSERT_require(isValidEdge(edge));
1832  VertexIterator source = edge->source();
1833  VertexIterator target = edge->target();
1834  EdgeIterator retval = eraseEdge(edge);
1835  if (source == target) {
1836  if (source->degree() == 0)
1837  eraseVertex(source);
1838  } else {
1839  if (source->degree() == 0)
1840  eraseVertex(source);
1841  if (target->degree() == 0)
1842  eraseVertex(target);
1843  }
1844  return retval;
1845  }
1846 
1856  void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1857  ASSERT_require(isValidVertex(source));
1858  ASSERT_require(isValidVertex(target));
1859  if (source->nOutEdges() < target->nInEdges()) {
1860  EdgeIterator iter = source->outEdges().begin();
1861  while (iter != source->outEdges().end()) {
1862  if (iter->target() == target) {
1863  iter = eraseEdge(iter);
1864  } else {
1865  ++iter;
1866  }
1867  }
1868  } else {
1869  EdgeIterator iter = target->inEdges().begin();
1870  while (iter != target->inEdges().end()) {
1871  if (iter->source() == source) {
1872  iter = eraseEdge(iter);
1873  } else {
1874  ++iter;
1875  }
1876  }
1877  }
1878  }
1879  void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1880  ASSERT_require(isValidVertex(source));
1881  ASSERT_require(isValidVertex(target));
1882  eraseEdges(findVertex(source->id()), findVertex(target->id()));
1883  }
1902  VertexIterator eraseVertex(const VertexIterator &vertex) {
1903  ASSERT_require(isValidVertex(vertex));
1904  VertexIterator next = vertex; ++next; // advance before we delete vertex
1905  clearEdges(vertex);
1906  vertexIndex_.erase(VertexKey(vertex->value()));
1907  vertices_.eraseAt(vertex->self_); // vertex is now deleted
1908  return next;
1909  }
1910  VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
1911  ASSERT_require(isValidVertex(vertex));
1912  return eraseVertex(findVertex(vertex->id()));
1913  }
1922  void clearEdges() {
1923  for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
1924  vertex->inEdges().reset();
1925  vertex->outEdges().reset();
1926  }
1927  edges_.clear();
1928  edgeIndex_.clear();
1929  }
1930 
1941  void clearEdges(const VertexIterator &vertex) {
1942  clearOutEdges(vertex);
1943  clearInEdges(vertex);
1944  }
1945  void clearEdges(const ConstVertexIterator &vertex) {
1946  clearOutEdges(vertex);
1947  clearInEdges(vertex);
1948  }
1960  void clearOutEdges(const VertexIterator &vertex) {
1961  ASSERT_forbid(vertex==vertices().end());
1962  for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
1963  edge = eraseEdge(edge);
1964  }
1965  void clearOutEdges(const ConstVertexIterator &vertex) {
1966  ASSERT_forbid(vertex==vertices().end());
1967  clearOutEdges(findVertex(vertex->id()));
1968  }
1980  void clearInEdges(const VertexIterator &vertex) {
1981  ASSERT_forbid(vertex==vertices().end());
1982  for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
1983  edge = eraseEdge(edge);
1984  }
1985  void clearInEdges(const ConstVertexIterator &vertex) {
1986  ASSERT_forbid(vertex==vertices().end());
1987  clearInEdges(findVertex(vertex->id()));
1988  }
1998  void clear() {
1999  edges_.clear();
2000  vertices_.clear();
2001  edgeIndex_.clear();
2002  vertexIndex_.clear();
2003  }
2004 
2006  // Internal implementation details
2008 private:
2009  VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
2010  const VertexKey key(value);
2011  if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
2012  if (strict)
2013  throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
2014  return findVertex((*found)->id());
2015  }
2016  typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
2017  inserted->value().self_ = inserted;
2018  inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
2019  VertexIterator retval = VertexIterator(inserted);
2020  vertexIndex_.insert(key, retval);
2021  return retval;
2022  }
2023 
2024  EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2025  const EdgeValue &value, bool strict) {
2026  const EdgeKey key(value);
2027  ASSERT_require(isValidVertex(sourceVertex));
2028  ASSERT_require(isValidVertex(targetVertex));
2029  if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2030  if (strict)
2031  throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2032  return findEdge((*found)->id());
2033  }
2034  typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
2035  inserted->value().self_ = inserted;
2036  inserted->value().edgeLists_.reset(&inserted->value());
2037  EdgeIterator newEdge(inserted);
2038  sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2039  ++sourceVertex->nOutEdges_;
2040  targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2041  ++targetVertex->nInEdges_;
2042  edgeIndex_.insert(key, newEdge);
2043  return newEdge;
2044  }
2045 
2046 
2048  // Deprecated stuff
2050 public:
2051  // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
2052  typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
2053  typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
2054  typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
2055  typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
2056  typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
2057  typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
2058 };
2059 
2060 } // namespace
2061 } // namespace
2062 
2063 #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:1678
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1960
Derived operator++(int)
Increment.
Definition: Graph.h:775
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition: Graph.h:1830
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition: Graph.h:1659
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1922
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:1714
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1210
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1902
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1137
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:1532
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:550
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1688
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:972
Bidirectional vertex node iterator.
Definition: Graph.h:1023
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition: Graph.h:1493
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1910
const EdgeValue & value() const
User-defined value.
Definition: Graph.h:1174
Bidirectional edge value iterator.
Definition: Graph.h:995
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:1221
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:1559
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:850
Derived & operator--()
Decrement.
Definition: Graph.h:889
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1815
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:1748
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:871
VertexValue & value()
User-defined value.
Definition: Graph.h:1286
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition: Graph.h:1668
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition: Graph.h:1226
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition: Graph.h:1547
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition: Graph.h:1466
Holds a value or nothing.
Definition: Optional.h:49
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition: Graph.h:1428
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1941
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:1462
Bidirectional vertex value iterator.
Definition: Graph.h:1089
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1856
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1744
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:680
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1980
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition: Graph.h:1656
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition: Graph.h:1598
Bidirectional vertex node iterator.
Definition: Graph.h:1044
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition: Graph.h:139
Graph(const Graph &other)
Copy constructor.
Definition: Graph.h:1386
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.
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1766
Base class for vertex iterators.
Definition: Graph.h:861
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:1242
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:1726
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1985
const VertexIterator & source()
Source vertex.
Definition: Graph.h:1147
EdgeValue & value()
User-defined value.
Definition: Graph.h:1173
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition: Graph.h:1602
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:899
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition: Graph.h:1621
ConstVertexIterator source() const
Source vertex.
Definition: Graph.h:1148
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1879
bool isEmpty() const
True if iterator doesn't point to anything.
Definition: Graph.h:906
Derived operator++(int)
Increment.
Definition: Graph.h:880
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:1782
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:1527
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition: Graph.h:1489
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1509
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:1512
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:1067
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:1641
void clear()
Remove all vertices and edges.
Definition: Graph.h:1998
size_t degree() const
Number of incident edges.
Definition: Graph.h:1272
bool operator<(const VertexBaseIterator &other) const
Iterator comparison.
Definition: Graph.h:903
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition: Graph.h:1636
const char * EdgePhase(int64_t)
Convert Sawyer::Container::Graph::EdgePhase enum constant to a string.
Definition: stringify.C:13385
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:1618
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:1247
size_t nInEdges() const
Number of incoming edges.
Definition: Graph.h:1257
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1945
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:692
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:594
Bidirectional edge node iterator.
Definition: Graph.h:945
Bidirectional edge node iterator.
Definition: Graph.h:922
const Allocator & allocator()
Allocator.
Definition: Graph.h:1447
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:1374
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
size_t nOutEdges() const
Number of outgoing edges.
Definition: Graph.h:1264
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition: Graph.h:1550
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1770
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition: Graph.h:1575
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:1571
bool isEmpty() const
True if graph is empty.
Definition: Graph.h:1697
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:898
Graph & operator=(const Graph &other)
Assignment.
Definition: Graph.h:1412
Derived & operator++()
Increment.
Definition: Graph.h:879
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1804
ConstVertexIterator target() const
Target vertex.
Definition: Graph.h:1160
const VertexIterator & target()
Target vertex.
Definition: Graph.h:1159
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:1400
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:1965
Derived operator--(int)
Decrement.
Definition: Graph.h:890
const VertexValue & value() const
User-defined value.
Definition: Graph.h:1287
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition: Graph.h:1181