ROSE  0.9.11.158
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 isEmpty() const {
834  if (N_PHASES == phase_) {
835  return iter_.isAtEnd();
836  } else {
837  return vlist_->isHead();
838  }
839  }
840  };
841 
843  template<class Derived, class Value, class Node, class BaseIter>
844  class VertexBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
845  BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
846  protected:
847  friend class Graph;
848  VertexBaseIterator() {}
849  VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
850  VertexBaseIterator(const BaseIter &base): base_(base) {}
851  Node& dereference() const { return base_->value(); }
852  public:
854  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
855 
862  Derived& operator++() { ++base_; return *derived(); }
863  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
872  Derived& operator--() { --base_; return *derived(); }
873  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
881  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
882  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
886  bool isEmpty() const {
887  return base_.base() == NULL;
888  }
889 
890  private:
891  Derived* derived() { return static_cast<Derived*>(this); }
892  const Derived* derived() const { return static_cast<const Derived*>(this); }
893  };
894 
895 public:
902  class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
903  VirtualList<Edge> > {
904  typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
905  VirtualList<Edge> > Super;
906  public:
907  typedef Edge& Reference;
908  typedef Edge* Pointer;
909  EdgeIterator() {}
910  EdgeIterator(const EdgeIterator &other): Super(other) {}
911  Edge& operator*() const { return this->dereference(); }
912  Edge* operator->() const { return &this->dereference(); }
913  private:
914  friend class Graph;
915  EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
916  EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
917  };
918 
925  class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
926  typename EdgeList::ConstNodeIterator,
927  const VirtualList<Edge> > {
928  typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
929  typename EdgeList::ConstNodeIterator,
930  const VirtualList<Edge> > Super;
931  public:
932  typedef const Edge& Reference;
933  typedef const Edge* Pointer;
934  ConstEdgeIterator() {}
935  ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
936  ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
937  const Edge& operator*() const { return this->dereference(); }
938  const Edge* operator->() const { return &this->dereference(); }
939  private:
940  friend class Graph;
941  ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
942  ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
943  };
952  class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
953  VirtualList<Edge> > {
954  typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
955  VirtualList<Edge> > Super;
956  public:
957  typedef EdgeValue& Reference;
958  typedef EdgeValue* Pointer;
959  EdgeValueIterator() {}
960  EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
961  EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
962  EdgeValue& operator*() const { return this->dereference().value(); }
963  EdgeValue* operator->() const { return &this->dereference().value(); }
964  private:
965  friend class Graph;
966  EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
967  EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
968  };
969 
975  class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
976  typename EdgeList::ConstNodeIterator,
977  const VirtualList<Edge> > {
979  typename EdgeList::ConstNodeIterator,
980  const VirtualList<Edge> > Super;
981  public:
982  typedef const EdgeValue& Reference;
983  typedef const EdgeValue* Pointer;
984  ConstEdgeValueIterator() {}
985  ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
986  ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
987  ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
988  ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
989  const EdgeValue& operator*() const { return this->dereference().value(); }
990  const EdgeValue* operator->() const { return &this->dereference().value(); }
991  private:
992  friend class Graph;
993  ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
994  ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
995  };
996 
1003  class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1004  typename VertexList::NodeIterator> {
1005  typedef VertexBaseIterator<VertexIterator, Vertex, Vertex,
1006  typename VertexList::NodeIterator> Super;
1007  public:
1008  typedef Vertex& Reference;
1009  typedef Vertex* Pointer;
1010  VertexIterator() {}
1011  VertexIterator(const VertexIterator &other): Super(other) {}
1012  Vertex& operator*() const { return this->dereference(); }
1013  Vertex* operator->() const { return &this->dereference(); }
1014  private:
1015  friend class Graph;
1016  VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1017  };
1018 
1024  class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1025  typename VertexList::ConstNodeIterator> {
1026  typedef VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1027  typename VertexList::ConstNodeIterator> Super;
1028  public:
1029  typedef const Vertex& Reference;
1030  typedef const Vertex* Pointer;
1031  ConstVertexIterator() {}
1032  ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1033  ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1034  const Vertex& operator*() const { return this->dereference(); }
1035  const Vertex* operator->() const { return &this->dereference(); }
1036  private:
1037  friend class Graph;
1038  ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1039  };
1040 
1047  class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1048  typename VertexList::NodeIterator> {
1050  typename VertexList::NodeIterator> Super;
1051  public:
1052  typedef VertexValue& Reference;
1053  typedef VertexValue* Pointer;
1054  VertexValueIterator() {}
1055  VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1056  VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1057  VertexValue& operator*() const { return this->dereference().value(); }
1058  VertexValue* operator->() const { return &this->dereference().value(); }
1059  private:
1060  friend class Graph;
1061  VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1062  };
1063 
1069  class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1070  typename VertexList::ConstNodeIterator> {
1072  typename VertexList::ConstNodeIterator> Super;
1073  public:
1074  typedef const VertexValue& Reference;
1075  typedef const VertexValue* Pointer;
1076  ConstVertexValueIterator() {}
1077  ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
1078  ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1079  ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1080  ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1081  const VertexValue& operator*() const { return this->dereference().value(); }
1082  const VertexValue* operator->() const { return &this->dereference().value(); }
1083  private:
1084  friend class Graph;
1085  ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1086  };
1087 
1088 
1090  // Storage nodes
1092 public:
1093 
1098  class Edge {
1099  VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1100  EdgeValue value_; // user-defined data for each edge
1101  typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1102  VertexIterator source_, target_; // starting and ending points of the edge are always required
1103  private:
1104  friend class Graph;
1105  Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
1106  : value_(value), source_(source), target_(target) {}
1107  public:
1117  const size_t& id() const { return self_->id(); }
1118 
1127  const VertexIterator& source() { return source_; }
1128  ConstVertexIterator source() const { return source_; }
1139  const VertexIterator& target() { return target_; }
1140  ConstVertexIterator target() const { return target_; }
1153  EdgeValue& value() { return value_; }
1154  const EdgeValue& value() const { return value_; }
1161  bool isSelfEdge() const {
1162  return source_ == target_;
1163  }
1164  };
1165 
1170  class Vertex {
1171  VertexValue value_; // user data for this vertex
1172  typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1173  VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1174  size_t nInEdges_; // number of incoming edges
1175  size_t nOutEdges_; // number of outgoing edges
1176  private:
1177  friend class Graph;
1178  Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1179  public:
1190  const size_t& id() const { return self_->id(); }
1191 
1201  boost::iterator_range<EdgeIterator> inEdges() {
1202  EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1203  EdgeIterator end(IN_EDGES, &edgeLists_);
1204  return boost::iterator_range<EdgeIterator>(begin, end);
1205  }
1206  boost::iterator_range<ConstEdgeIterator> inEdges() const {
1207  ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1208  ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1209  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1210  }
1222  boost::iterator_range<EdgeIterator> outEdges() {
1223  EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1224  EdgeIterator end(OUT_EDGES, &edgeLists_);
1225  return boost::iterator_range<EdgeIterator>(begin, end);
1226  }
1227  boost::iterator_range<ConstEdgeIterator> outEdges() const {
1228  ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1229  ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1230  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1231  }
1237  size_t nInEdges() const {
1238  return nInEdges_;
1239  }
1240 
1244  size_t nOutEdges() const {
1245  return nOutEdges_;
1246  }
1247 
1252  size_t degree() const {
1253  return nInEdges_ + nOutEdges_;
1254  }
1255 
1266  VertexValue& value() { return value_; }
1267  const VertexValue& value() const { return value_; }
1269  };
1270 
1271 private:
1272  typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
1273  typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1274 
1275  EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1276  VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1277  EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1278  VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1279 
1281  // Serialization
1283 private:
1284  friend class boost::serialization::access;
1285 
1286  struct SerializableEdge {
1287  size_t srcId, tgtId;
1288  EdgeValue value;
1289 
1290  SerializableEdge()
1291  : srcId(-1), tgtId(-1) {}
1292 
1293  SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1294  : srcId(srcId), tgtId(tgtId), value(value) {}
1295 
1296  template<class S>
1297  void serialize(S &s, const unsigned /*version*/) {
1298  s & BOOST_SERIALIZATION_NVP(srcId);
1299  s & BOOST_SERIALIZATION_NVP(tgtId);
1300  s & BOOST_SERIALIZATION_NVP(value);
1301  }
1302  };
1303 
1304  template<class S>
1305  void save(S &s, const unsigned /*version*/) const {
1306  size_t nv = nVertices();
1307  s <<BOOST_SERIALIZATION_NVP(nv);
1308  for (size_t i=0; i<nv; ++i)
1309  s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
1310 
1311  size_t ne = nEdges();
1312  s <<BOOST_SERIALIZATION_NVP(ne);
1313  for (size_t i=0; i<ne; ++i) {
1314  ConstEdgeIterator edge = findEdge(i);
1315  SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1316  s <<BOOST_SERIALIZATION_NVP(se);
1317  }
1318  }
1319 
1320  template<class S>
1321  void load(S &s, const unsigned /*version*/) {
1322  clear();
1323  size_t nv = 0;
1324  s >>BOOST_SERIALIZATION_NVP(nv);
1325  for (size_t i=0; i<nv; ++i) {
1326  VertexValue vv;
1327  s >>boost::serialization::make_nvp("vertex", vv);
1328  insertVertex(vv);
1329  }
1330 
1331  size_t ne = 0;
1332  s >>BOOST_SERIALIZATION_NVP(ne);
1333  for (size_t i=0; i<ne; ++i) {
1334  SerializableEdge se;
1335  s >>BOOST_SERIALIZATION_NVP(se);
1336  ASSERT_require(se.srcId < nv && se.tgtId < nv);
1337  insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1338  }
1339  }
1340 
1341  BOOST_SERIALIZATION_SPLIT_MEMBER();
1342 
1343 
1345  // Initialization
1347 public:
1348 
1354  Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1355 
1366  Graph(const Graph &other)
1367  : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1368  *this = other;
1369  }
1370 
1379  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1380  Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
1381  : edges_(allocator), vertices_(allocator) {
1382  *this = other;
1383  }
1384 
1392  Graph& operator=(const Graph &other) {
1393  return operator=<V, E>(other);
1394  }
1395 
1407  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1409  clear();
1410  for (size_t i=0; i<other.nVertices(); ++i) {
1412  VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1413  ASSERT_require(inserted->id() == i);
1414  }
1415  for (size_t i=0; i<other.nEdges(); ++i) {
1417  VertexIterator vsrc = findVertex(edge->source()->id());
1418  VertexIterator vtgt = findVertex(edge->target()->id());
1419  insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1420  }
1421  return *this;
1422  }
1423 
1427  const Allocator& allocator() {
1428  return vertices_.allocator();
1429  }
1430 
1432 public:
1433 
1442  boost::iterator_range<VertexIterator> vertices() {
1443  return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1444  VertexIterator(vertices_.nodes().end()));
1445  }
1446  boost::iterator_range<ConstVertexIterator> vertices() const {
1447  return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1448  ConstVertexIterator(vertices_.nodes().end()));
1449  }
1469  boost::iterator_range<VertexValueIterator> vertexValues() {
1470  return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1471  VertexValueIterator(vertices_.nodes().end()));
1472  }
1473  boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1474  return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1475  ConstVertexValueIterator(vertices_.nodes().end()));
1476  }
1489  VertexIterator findVertex(size_t id) {
1490  return VertexIterator(vertices_.find(id));
1491  }
1492  ConstVertexIterator findVertex(size_t id) const {
1493  return ConstVertexIterator(vertices_.find(id));
1494  }
1507  VertexIterator findVertexKey(const VertexKey &key) {
1508  if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1509  return findVertex((*ov)->id());
1510  return vertices().end();
1511  }
1512  ConstVertexIterator findVertexKey(const VertexKey &key) const {
1513  return vertexIndex_.lookup(key).orElse(vertices().end());
1514  }
1527  VertexIterator findVertexValue(const VertexValue &value) {
1528  return findVertexKey(VertexKey(value));
1529  }
1530  ConstVertexIterator findVertexValue(const VertexValue &value) const {
1531  return findVertexKey(VertexKey(value));
1532  }
1539  bool isValidVertex(const ConstVertexIterator &vertex) const {
1540  return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1541  }
1542 
1551  boost::iterator_range<EdgeIterator> edges() {
1552  return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1553  EdgeIterator(edges_.nodes().end()));
1554  }
1555  boost::iterator_range<ConstEdgeIterator> edges() const {
1556  return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1557  ConstEdgeIterator(edges_.nodes().end()));
1558  }
1578  boost::iterator_range<EdgeValueIterator> edgeValues() {
1579  return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1580  EdgeValueIterator(edges_.nodes().end()));
1581  }
1582  boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1583  return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1584  ConstEdgeValueIterator(edges_.nodes().end()));
1585  }
1598  EdgeIterator findEdge(size_t id) {
1599  return EdgeIterator(edges_.find(id));
1600  }
1601  ConstEdgeIterator findEdge(size_t id) const {
1602  return ConstEdgeIterator(edges_.find(id));
1603  }
1616  EdgeIterator findEdgeKey(const EdgeKey &key) {
1617  if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1618  return findEdge((*oe)->id());
1619  return edges().end();
1620  }
1621  ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
1622  return edgeIndex_.lookup(key).orElse(edges().end());
1623  }
1636  EdgeIterator findEdgeValue(const EdgeValue &value) {
1637  return findEdgeKey(EdgeKey(value));
1638  }
1639  ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
1640  return findEdgeValue(EdgeKey(value));
1641  }
1648  bool isValidEdge(const ConstEdgeIterator &edge) const {
1649  return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1650  }
1651 
1658  size_t nVertices() const {
1659  return vertices_.size();
1660  }
1661 
1668  size_t nEdges() const {
1669  return edges_.size();
1670  }
1671 
1677  bool isEmpty() const {
1678  ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1679  return vertices_.isEmpty();
1680  }
1681 
1694  VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
1695  return insertVertexImpl(value, true /*strict*/);
1696  }
1697 
1706  VertexIterator insertVertexMaybe(const VertexValue &value) {
1707  return insertVertexImpl(value, false /*non-strict*/);
1708  }
1709 
1724  EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1725  const EdgeValue &value = EdgeValue()) {
1726  return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1727  }
1728  EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1729  const EdgeValue &value = EdgeValue()) {
1730  ASSERT_require(isValidVertex(sourceVertex));
1731  ASSERT_require(isValidVertex(targetVertex));
1732  return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1733  }
1746  EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1747  const EdgeValue &value = EdgeValue()) {
1748  return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1749  }
1750  EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1751  const EdgeValue &value = EdgeValue()) {
1752  ASSERT_require(isValidVertex(sourceVertex));
1753  ASSERT_require(isValidVertex(targetVertex));
1754  return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1755  }
1762  EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1763  const EdgeValue &edgeValue = EdgeValue()) {
1764  VertexIterator source = insertVertexMaybe(sourceValue);
1765  VertexIterator target = insertVertexMaybe(targetValue);
1766  return insertEdge(source, target, edgeValue);
1767  }
1768 
1784  EdgeIterator eraseEdge(const EdgeIterator &edge) {
1785  ASSERT_require(isValidEdge(edge));
1786  EdgeIterator next = edge; ++next; // advance before we delete edge
1787  edgeIndex_.erase(EdgeKey(edge->value()));
1788  --edge->source_->nOutEdges_;
1789  edge->edgeLists_.remove(OUT_EDGES);
1790  --edge->target_->nInEdges_;
1791  edge->edgeLists_.remove(IN_EDGES);
1792  edges_.eraseAt(edge->self_); // edge is now deleted
1793  return next;
1794  }
1795  EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
1796  ASSERT_require(isValidEdge(edge));
1797  return eraseEdge(findEdge(edge->id()));
1798  }
1810  EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
1811  ASSERT_require(isValidEdge(edge));
1812  VertexIterator source = edge->source();
1813  VertexIterator target = edge->target();
1814  EdgeIterator retval = eraseEdge(edge);
1815  if (source == target) {
1816  if (source->degree() == 0)
1817  eraseVertex(source);
1818  } else {
1819  if (source->degree() == 0)
1820  eraseVertex(source);
1821  if (target->degree() == 0)
1822  eraseVertex(target);
1823  }
1824  return retval;
1825  }
1826 
1836  void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1837  ASSERT_require(isValidVertex(source));
1838  ASSERT_require(isValidVertex(target));
1839  if (source->nOutEdges() < target->nInEdges()) {
1840  EdgeIterator iter = source->outEdges().begin();
1841  while (iter != source->outEdges().end()) {
1842  if (iter->target() == target) {
1843  iter = eraseEdge(iter);
1844  } else {
1845  ++iter;
1846  }
1847  }
1848  } else {
1849  EdgeIterator iter = target->inEdges().begin();
1850  while (iter != target->inEdges().end()) {
1851  if (iter->source() == source) {
1852  iter = eraseEdge(iter);
1853  } else {
1854  ++iter;
1855  }
1856  }
1857  }
1858  }
1859  void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1860  ASSERT_require(isValidVertex(source));
1861  ASSERT_require(isValidVertex(target));
1862  eraseEdges(findVertex(source->id()), findVertex(target->id()));
1863  }
1882  VertexIterator eraseVertex(const VertexIterator &vertex) {
1883  ASSERT_require(isValidVertex(vertex));
1884  VertexIterator next = vertex; ++next; // advance before we delete vertex
1885  clearEdges(vertex);
1886  vertexIndex_.erase(VertexKey(vertex->value()));
1887  vertices_.eraseAt(vertex->self_); // vertex is now deleted
1888  return next;
1889  }
1890  VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
1891  ASSERT_require(isValidVertex(vertex));
1892  return eraseVertex(findVertex(vertex->id()));
1893  }
1902  void clearEdges() {
1903  for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
1904  vertex->inEdges().reset();
1905  vertex->outEdges().reset();
1906  }
1907  edges_.clear();
1908  edgeIndex_.clear();
1909  }
1910 
1921  void clearEdges(const VertexIterator &vertex) {
1922  clearOutEdges(vertex);
1923  clearInEdges(vertex);
1924  }
1925  void clearEdges(const ConstVertexIterator &vertex) {
1926  clearOutEdges(vertex);
1927  clearInEdges(vertex);
1928  }
1940  void clearOutEdges(const VertexIterator &vertex) {
1941  ASSERT_forbid(vertex==vertices().end());
1942  for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
1943  edge = eraseEdge(edge);
1944  }
1945  void clearOutEdges(const ConstVertexIterator &vertex) {
1946  ASSERT_forbid(vertex==vertices().end());
1947  clearOutEdges(findVertex(vertex->id()));
1948  }
1960  void clearInEdges(const VertexIterator &vertex) {
1961  ASSERT_forbid(vertex==vertices().end());
1962  for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
1963  edge = eraseEdge(edge);
1964  }
1965  void clearInEdges(const ConstVertexIterator &vertex) {
1966  ASSERT_forbid(vertex==vertices().end());
1967  clearInEdges(findVertex(vertex->id()));
1968  }
1978  void clear() {
1979  edges_.clear();
1980  vertices_.clear();
1981  edgeIndex_.clear();
1982  vertexIndex_.clear();
1983  }
1984 
1986  // Internal implementation details
1988 private:
1989  VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
1990  const VertexKey key(value);
1991  if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
1992  if (strict)
1993  throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
1994  return findVertex((*found)->id());
1995  }
1996  typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
1997  inserted->value().self_ = inserted;
1998  inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
1999  VertexIterator retval = VertexIterator(inserted);
2000  vertexIndex_.insert(key, retval);
2001  return retval;
2002  }
2003 
2004  EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2005  const EdgeValue &value, bool strict) {
2006  const EdgeKey key(value);
2007  ASSERT_require(isValidVertex(sourceVertex));
2008  ASSERT_require(isValidVertex(targetVertex));
2009  if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2010  if (strict)
2011  throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2012  return findEdge((*found)->id());
2013  }
2014  typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
2015  inserted->value().self_ = inserted;
2016  inserted->value().edgeLists_.reset(&inserted->value());
2017  EdgeIterator newEdge(inserted);
2018  sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2019  ++sourceVertex->nOutEdges_;
2020  targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2021  ++targetVertex->nInEdges_;
2022  edgeIndex_.insert(key, newEdge);
2023  return newEdge;
2024  }
2025 
2026 
2028  // Deprecated stuff
2030 public:
2031  // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
2032  typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
2033  typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
2034  typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
2035  typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
2036  typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
2037  typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
2038 };
2039 
2040 } // namespace
2041 } // namespace
2042 
2043 #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:1658
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1940
Derived operator++(int)
Increment.
Definition: Graph.h:775
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition: Graph.h:1810
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition: Graph.h:1639
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1902
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:1694
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1190
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1882
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1117
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:1512
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:1668
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:952
Bidirectional vertex node iterator.
Definition: Graph.h:1003
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition: Graph.h:1473
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1890
const EdgeValue & value() const
User-defined value.
Definition: Graph.h:1154
Bidirectional edge value iterator.
Definition: Graph.h:975
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:1201
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:1539
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:833
Derived & operator--()
Decrement.
Definition: Graph.h:872
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1795
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:1728
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:854
VertexValue & value()
User-defined value.
Definition: Graph.h:1266
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition: Graph.h:1648
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition: Graph.h:1206
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition: Graph.h:1527
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition: Graph.h:1446
Holds a value or nothing.
Definition: Optional.h:49
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition: Graph.h:1408
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1921
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:1442
Bidirectional vertex value iterator.
Definition: Graph.h:1069
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1836
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1724
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:680
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1960
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition: Graph.h:1636
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition: Graph.h:1578
Bidirectional vertex node iterator.
Definition: Graph.h:1024
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition: Graph.h:139
Graph(const Graph &other)
Copy constructor.
Definition: Graph.h:1366
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:1746
Base class for vertex iterators.
Definition: Graph.h:844
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:1222
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:1706
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1965
const VertexIterator & source()
Source vertex.
Definition: Graph.h:1127
EdgeValue & value()
User-defined value.
Definition: Graph.h:1153
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition: Graph.h:1582
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:882
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition: Graph.h:1601
ConstVertexIterator source() const
Source vertex.
Definition: Graph.h:1128
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1859
bool isEmpty() const
True if iterator doesn't point to anything.
Definition: Graph.h:886
Derived operator++(int)
Increment.
Definition: Graph.h:863
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:1762
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:1507
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition: Graph.h:1469
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1489
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:1492
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:1047
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:1621
void clear()
Remove all vertices and edges.
Definition: Graph.h:1978
size_t degree() const
Number of incident edges.
Definition: Graph.h:1252
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition: Graph.h:1616
const char * EdgePhase(int64_t)
Convert Sawyer::Container::Graph::EdgePhase enum constant to a string.
Definition: stringify.C:13767
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:1598
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:1227
size_t nInEdges() const
Number of incoming edges.
Definition: Graph.h:1237
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1925
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:925
Bidirectional edge node iterator.
Definition: Graph.h:902
const Allocator & allocator()
Allocator.
Definition: Graph.h:1427
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:1354
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
size_t nOutEdges() const
Number of outgoing edges.
Definition: Graph.h:1244
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition: Graph.h:1530
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1750
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition: Graph.h:1555
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:1551
bool isEmpty() const
True if graph is empty.
Definition: Graph.h:1677
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:881
Graph & operator=(const Graph &other)
Assignment.
Definition: Graph.h:1392
Derived & operator++()
Increment.
Definition: Graph.h:862
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1784
ConstVertexIterator target() const
Target vertex.
Definition: Graph.h:1140
const VertexIterator & target()
Target vertex.
Definition: Graph.h:1139
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:1380
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:1945
Derived operator--(int)
Decrement.
Definition: Graph.h:873
const VertexValue & value() const
User-defined value.
Definition: Graph.h:1267
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition: Graph.h:1161