ROSE  0.9.9.139
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_this();
662  ASSERT_require(phase < N_PHASES);
663  ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
664  return next_[phase]==this;
665  }
666 
667  bool isEmpty(EdgePhase phase) const {
668  ASSERT_this();
669  ASSERT_require(isHead());
670  ASSERT_require((next_[phase]==this && prev_[phase]==this) || (next_[phase]!=this && prev_[phase]!=this));
671  return next_[phase]==this;
672  }
673 
674  void insert(EdgePhase phase, VirtualList *newNode) { // insert newNode before this
675  ASSERT_this();
676  ASSERT_require(phase < N_PHASES);
677  ASSERT_not_null(newNode);
678  ASSERT_forbid(newNode->isHead());
679  ASSERT_require(newNode->isSingleton(phase)); // cannot be part of another sublist already
680  prev_[phase]->next_[phase] = newNode;
681  newNode->prev_[phase] = prev_[phase];
682  prev_[phase] = newNode;
683  newNode->next_[phase] = this;
684  }
685 
686  void remove(EdgePhase phase) { // Remove this node from the list
687  ASSERT_this();
688  ASSERT_require(phase < N_PHASES);
689  ASSERT_forbid(isHead());
690  prev_[phase]->next_[phase] = next_[phase];
691  next_[phase]->prev_[phase] = prev_[phase];
692  next_[phase] = prev_[phase] = this;
693  }
694 
695  VirtualList& next(EdgePhase phase) { return *next_[phase]; }
696  const VirtualList& next(EdgePhase phase) const { return *next_[phase]; }
697  VirtualList& prev(EdgePhase phase) { return *prev_[phase]; }
698  const VirtualList& prev(EdgePhase phase) const { return *prev_[phase]; }
699 
700  T& dereference() { // Return the Edge to which this VirtualList node belongs
701  ASSERT_this();
702  ASSERT_forbid(isHead()); // list head contains no user-data
703  return *(T*)this; // depends on VirtualList being at the beginning of Edge
704  }
705 
706  const T& dereference() const {
707  ASSERT_this();
708  ASSERT_forbid(isHead());
709  return *(const T*)this;
710  }
711 
712 #if 1 /*DEBUGGING [Robb Matzke 2014-04-21]*/
713  void dump(EdgePhase phase, std::ostream &o) const {
714  const VirtualList *cur = this;
715  o <<" " <<std::setw(18) <<"Node"
716  <<"\t" <<std::setw(18) <<"This"
717  <<"\t" <<std::setw(18) <<"Next"
718  <<"\t" <<std::setw(18) <<"Prev\n";
719  do {
720  o <<" " <<std::setw(18) <<node_
721  <<"\t" <<std::setw(18) <<cur
722  <<"\t" <<std::setw(18) <<cur->next_[phase]
723  <<"\t" <<std::setw(18) <<cur->prev_[phase] <<"\n";
724  cur = cur->next_[phase];
725  } while (cur!=this && cur->next_[phase]!=cur);
726  }
727 #endif
728  };
729 
731  // Iterators
733 public: // public only for the sake of doxygen
736  template<class Derived, class Value, class Node, class BaseIter, class VList>
737  class EdgeBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
738  EdgePhase phase_; // IN_EDGES, OUT_EDGES or N_PHASES (graph edges)
739  BaseIter iter_; // EdgeList::NodeIterator or EdgeList::ConstNodeIterator
740  VList *vlist_; // (const) VirtualList<Edge> when phase_ is IN_EDGES or OUT_EDGES
741  protected:
742  friend class Graph;
743  EdgeBaseIterator() {}
744  EdgeBaseIterator(const EdgeBaseIterator &other): phase_(other.phase_), iter_(other.iter_), vlist_(other.vlist_) {}
745  EdgeBaseIterator(const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
746  EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
747  template<class BaseIter2> EdgeBaseIterator(EdgePhase phase, const BaseIter2 &iter, VList *vlist)
748  : phase_(phase), iter_(iter), vlist_(vlist) {}
749 
750  Node& dereference() const {
751  return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
752  }
753 
754  private:
755  Derived* derived() { return static_cast<Derived*>(this); }
756  const Derived* derived() const { return static_cast<const Derived*>(this); }
757 
758  public:
760  Derived& operator=(const Derived &other) {
761  phase_ = other.phase_;
762  iter_ = other.iter_;
763  vlist_ = other.vlist_;
764  return *derived();
765  }
766 
773  Derived& operator++() {
774  if (N_PHASES==phase_) {
775  ++iter_;
776  } else {
777  vlist_ = &vlist_->next(phase_);
778  }
779  return *derived();
780  }
781  Derived operator++(int) {
782  Derived old = *derived();
783  ++*this;
784  return old;
785  }
794  Derived& operator--() {
795  if (N_PHASES==phase_) {
796  --iter_;
797  } else {
798  vlist_ = &vlist_->prev(phase_);
799  }
800  return *derived();
801  }
802  Derived operator--(int) {
803  Derived old = *derived();
804  --*this;
805  return old;
806  }
816  template<class OtherIter>
817  bool operator==(const OtherIter &other) const {
818  Node *a = NULL;
819  if (N_PHASES==phase_) {
820  a = iter_.isAtEnd() ? NULL : &iter_->value();
821  } else {
822  a = vlist_->isHead() ? NULL : &vlist_->dereference();
823  }
824  Node *b = NULL;
825  if (N_PHASES==other.phase_) {
826  b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
827  } else {
828  b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
829  }
830  return a == b;
831  }
832  template<class OtherIter>
833  bool operator!=(const OtherIter &other) const {
834  return !(*this==other);
835  }
839  bool operator<(const EdgeBaseIterator &other) const {
840  Node *a = NULL;
841  if (N_PHASES==phase_) {
842  a = iter_.isAtEnd() ? NULL : &iter_->value();
843  } else {
844  a = vlist_->isHead() ? NULL : &vlist_->dereference();
845  }
846  Node *b = NULL;
847  if (N_PHASES==other.phase_) {
848  b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
849  } else {
850  b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
851  }
852  return a < b;
853  }
854  };
855 
857  template<class Derived, class Value, class Node, class BaseIter>
858  class VertexBaseIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
859  BaseIter base_; // VertexList::NodeIterator or VertexList::ConstNodeIterator
860  protected:
861  friend class Graph;
862  VertexBaseIterator() {}
863  VertexBaseIterator(const VertexBaseIterator &other): base_(other.base_) {}
864  VertexBaseIterator(const BaseIter &base): base_(base) {}
865  Node& dereference() const { return base_->value(); }
866  public:
868  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
869 
876  Derived& operator++() { ++base_; return *derived(); }
877  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
886  Derived& operator--() { --base_; return *derived(); }
887  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
895  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base_; }
896  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base_; }
900  bool operator<(const VertexBaseIterator &other) const { return base_ < other.base_; }
901 
902  private:
903  Derived* derived() { return static_cast<Derived*>(this); }
904  const Derived* derived() const { return static_cast<const Derived*>(this); }
905  };
906 
907 public:
914  class EdgeIterator: public EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
915  VirtualList<Edge> > {
916  typedef EdgeBaseIterator<EdgeIterator, Edge, Edge, typename EdgeList::NodeIterator,
917  VirtualList<Edge> > Super;
918  public:
919  typedef Edge& Reference;
920  typedef Edge* Pointer;
921  EdgeIterator() {}
922  EdgeIterator(const EdgeIterator &other): Super(other) {}
923  Edge& operator*() const { return this->dereference(); }
924  Edge* operator->() const { return &this->dereference(); }
925  private:
926  friend class Graph;
927  EdgeIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
928  EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
929  };
930 
937  class ConstEdgeIterator: public EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
938  typename EdgeList::ConstNodeIterator,
939  const VirtualList<Edge> > {
940  typedef EdgeBaseIterator<ConstEdgeIterator, const Edge, const Edge,
941  typename EdgeList::ConstNodeIterator,
942  const VirtualList<Edge> > Super;
943  public:
944  typedef const Edge& Reference;
945  typedef const Edge* Pointer;
946  ConstEdgeIterator() {}
947  ConstEdgeIterator(const ConstEdgeIterator &other): Super(other) {}
948  ConstEdgeIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
949  const Edge& operator*() const { return this->dereference(); }
950  const Edge* operator->() const { return &this->dereference(); }
951  private:
952  friend class Graph;
953  ConstEdgeIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
954  ConstEdgeIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
955  };
964  class EdgeValueIterator: public EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
965  VirtualList<Edge> > {
966  typedef EdgeBaseIterator<EdgeValueIterator, EdgeValue, Edge, typename EdgeList::NodeIterator,
967  VirtualList<Edge> > Super;
968  public:
969  typedef EdgeValue& Reference;
970  typedef EdgeValue* Pointer;
971  EdgeValueIterator() {}
972  EdgeValueIterator(const EdgeValueIterator &other): Super(other) {}
973  EdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
974  EdgeValue& operator*() const { return this->dereference().value(); }
975  EdgeValue* operator->() const { return &this->dereference().value(); }
976  private:
977  friend class Graph;
978  EdgeValueIterator(const typename EdgeList::NodeIterator &base): Super(base) {}
979  EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
980  };
981 
987  class ConstEdgeValueIterator: public EdgeBaseIterator<ConstEdgeValueIterator, const EdgeValue, const Edge,
988  typename EdgeList::ConstNodeIterator,
989  const VirtualList<Edge> > {
991  typename EdgeList::ConstNodeIterator,
992  const VirtualList<Edge> > Super;
993  public:
994  typedef const EdgeValue& Reference;
995  typedef const EdgeValue* Pointer;
996  ConstEdgeValueIterator() {}
997  ConstEdgeValueIterator(const ConstEdgeValueIterator &other): Super(other) {}
998  ConstEdgeValueIterator(const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
999  ConstEdgeValueIterator(const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1000  ConstEdgeValueIterator(const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1001  const EdgeValue& operator*() const { return this->dereference().value(); }
1002  const EdgeValue* operator->() const { return &this->dereference().value(); }
1003  private:
1004  friend class Graph;
1005  ConstEdgeValueIterator(const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1006  ConstEdgeValueIterator(EdgePhase phase, const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1007  };
1008 
1015  class VertexIterator: public VertexBaseIterator<VertexIterator, Vertex, Vertex,
1016  typename VertexList::NodeIterator> {
1017  typedef VertexBaseIterator<VertexIterator, Vertex, Vertex,
1018  typename VertexList::NodeIterator> Super;
1019  public:
1020  typedef Vertex& Reference;
1021  typedef Vertex* Pointer;
1022  VertexIterator() {}
1023  VertexIterator(const VertexIterator &other): Super(other) {}
1024  Vertex& operator*() const { return this->dereference(); }
1025  Vertex* operator->() const { return &this->dereference(); }
1026  private:
1027  friend class Graph;
1028  VertexIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1029  };
1030 
1036  class ConstVertexIterator: public VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1037  typename VertexList::ConstNodeIterator> {
1038  typedef VertexBaseIterator<ConstVertexIterator, const Vertex, const Vertex,
1039  typename VertexList::ConstNodeIterator> Super;
1040  public:
1041  typedef const Vertex& Reference;
1042  typedef const Vertex* Pointer;
1043  ConstVertexIterator() {}
1044  ConstVertexIterator(const ConstVertexIterator &other): Super(other) {}
1045  ConstVertexIterator(const VertexIterator &other): Super(other.base_) {}
1046  const Vertex& operator*() const { return this->dereference(); }
1047  const Vertex* operator->() const { return &this->dereference(); }
1048  private:
1049  friend class Graph;
1050  ConstVertexIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1051  };
1052 
1059  class VertexValueIterator: public VertexBaseIterator<VertexValueIterator, VertexValue, Vertex,
1060  typename VertexList::NodeIterator> {
1062  typename VertexList::NodeIterator> Super;
1063  public:
1064  typedef VertexValue& Reference;
1065  typedef VertexValue* Pointer;
1066  VertexValueIterator() {}
1067  VertexValueIterator(const VertexValueIterator &other): Super(other) {}
1068  VertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1069  VertexValue& operator*() const { return this->dereference().value(); }
1070  VertexValue* operator->() const { return &this->dereference().value(); }
1071  private:
1072  friend class Graph;
1073  VertexValueIterator(const typename VertexList::NodeIterator &base): Super(base) {}
1074  };
1075 
1081  class ConstVertexValueIterator: public VertexBaseIterator<ConstVertexValueIterator, const VertexValue, const Vertex,
1082  typename VertexList::ConstNodeIterator> {
1084  typename VertexList::ConstNodeIterator> Super;
1085  public:
1086  typedef const VertexValue& Reference;
1087  typedef const VertexValue* Pointer;
1088  ConstVertexValueIterator() {}
1089  ConstVertexValueIterator(const ConstVertexValueIterator &other): Super(other) {}
1090  ConstVertexValueIterator(const VertexValueIterator &other): Super(other.base_) {}
1091  ConstVertexValueIterator(const VertexIterator &other): Super(other.base_) {}
1092  ConstVertexValueIterator(const ConstVertexIterator &other): Super(other.base_) {}
1093  const VertexValue& operator*() const { return this->dereference().value(); }
1094  const VertexValue* operator->() const { return &this->dereference().value(); }
1095  private:
1096  friend class Graph;
1097  ConstVertexValueIterator(const typename VertexList::ConstNodeIterator &base): Super(base) {}
1098  };
1099 
1100 
1102  // Storage nodes
1104 public:
1105 
1110  class Edge {
1111  VirtualList<Edge> edgeLists_; // links for in- and out-edge sublists; MUST BE FIRST
1112  EdgeValue value_; // user-defined data for each edge
1113  typename EdgeList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1114  VertexIterator source_, target_; // starting and ending points of the edge are always required
1115  private:
1116  friend class Graph;
1117  Edge(const EdgeValue &value, const VertexIterator &source, const VertexIterator &target)
1118  : value_(value), source_(source), target_(target) {}
1119  public:
1129  const size_t& id() const { return self_->id(); }
1130 
1139  const VertexIterator& source() { return source_; }
1140  ConstVertexIterator source() const { return source_; }
1151  const VertexIterator& target() { return target_; }
1152  ConstVertexIterator target() const { return target_; }
1165  EdgeValue& value() { return value_; }
1166  const EdgeValue& value() const { return value_; }
1173  bool isSelfEdge() const {
1174  return source_ == target_;
1175  }
1176  };
1177 
1182  class Vertex {
1183  VertexValue value_; // user data for this vertex
1184  typename VertexList::NodeIterator self_; // always points to itself so we can get to IndexedList::Node
1185  VirtualList<Edge> edgeLists_; // this is the head node; points to the real edges
1186  size_t nInEdges_; // number of incoming edges
1187  size_t nOutEdges_; // number of outgoing edges
1188  private:
1189  friend class Graph;
1190  Vertex(const VertexValue &value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1191  public:
1202  const size_t& id() const { return self_->id(); }
1203 
1213  boost::iterator_range<EdgeIterator> inEdges() {
1214  EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1215  EdgeIterator end(IN_EDGES, &edgeLists_);
1216  return boost::iterator_range<EdgeIterator>(begin, end);
1217  }
1218  boost::iterator_range<ConstEdgeIterator> inEdges() const {
1219  ConstEdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1220  ConstEdgeIterator end(IN_EDGES, &edgeLists_);
1221  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1222  }
1234  boost::iterator_range<EdgeIterator> outEdges() {
1235  EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1236  EdgeIterator end(OUT_EDGES, &edgeLists_);
1237  return boost::iterator_range<EdgeIterator>(begin, end);
1238  }
1239  boost::iterator_range<ConstEdgeIterator> outEdges() const {
1240  ConstEdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1241  ConstEdgeIterator end(OUT_EDGES, &edgeLists_);
1242  return boost::iterator_range<ConstEdgeIterator>(begin, end);
1243  }
1249  size_t nInEdges() const {
1250  return nInEdges_;
1251  }
1252 
1256  size_t nOutEdges() const {
1257  return nOutEdges_;
1258  }
1259 
1264  size_t degree() const {
1265  return nInEdges_ + nOutEdges_;
1266  }
1267 
1278  VertexValue& value() { return value_; }
1279  const VertexValue& value() const { return value_; }
1281  };
1282 
1283 private:
1284  typedef typename GraphIndexTraits<VertexKey, ConstVertexIterator>::Index VertexIndex;
1285  typedef typename GraphIndexTraits<EdgeKey, ConstEdgeIterator>::Index EdgeIndex;
1286 
1287  EdgeList edges_; // all edges with integer ID numbers and O(1) insert/erase
1288  VertexList vertices_; // all vertices with integer ID numbers and O(1) insert/erase
1289  EdgeIndex edgeIndex_; // optional mapping between EdgeValue and ConstEdgeIterator
1290  VertexIndex vertexIndex_; // optional mapping between VertexValue and ConstVertexIterator
1291 
1293  // Serialization
1295 private:
1296  friend class boost::serialization::access;
1297 
1298  struct SerializableEdge {
1299  size_t srcId, tgtId;
1300  EdgeValue value;
1301 
1302  SerializableEdge()
1303  : srcId(-1), tgtId(-1) {}
1304 
1305  SerializableEdge(size_t srcId, size_t tgtId, const EdgeValue &value)
1306  : srcId(srcId), tgtId(tgtId), value(value) {}
1307 
1308  template<class S>
1309  void serialize(S &s, const unsigned /*version*/) {
1310  s & BOOST_SERIALIZATION_NVP(srcId);
1311  s & BOOST_SERIALIZATION_NVP(tgtId);
1312  s & BOOST_SERIALIZATION_NVP(value);
1313  }
1314  };
1315 
1316  template<class S>
1317  void save(S &s, const unsigned /*version*/) const {
1318  size_t nv = nVertices();
1319  s <<BOOST_SERIALIZATION_NVP(nv);
1320  for (size_t i=0; i<nv; ++i)
1321  s <<boost::serialization::make_nvp("vertex", findVertex(i)->value());
1322 
1323  size_t ne = nEdges();
1324  s <<BOOST_SERIALIZATION_NVP(ne);
1325  for (size_t i=0; i<ne; ++i) {
1326  ConstEdgeIterator edge = findEdge(i);
1327  SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1328  s <<BOOST_SERIALIZATION_NVP(se);
1329  }
1330  }
1331 
1332  template<class S>
1333  void load(S &s, const unsigned /*version*/) {
1334  clear();
1335  size_t nv = 0;
1336  s >>BOOST_SERIALIZATION_NVP(nv);
1337  for (size_t i=0; i<nv; ++i) {
1338  VertexValue vv;
1339  s >>boost::serialization::make_nvp("vertex", vv);
1340  insertVertex(vv);
1341  }
1342 
1343  size_t ne = 0;
1344  s >>BOOST_SERIALIZATION_NVP(ne);
1345  for (size_t i=0; i<ne; ++i) {
1346  SerializableEdge se;
1347  s >>BOOST_SERIALIZATION_NVP(se);
1348  ASSERT_require(se.srcId < nv && se.tgtId < nv);
1349  insertEdge(findVertex(se.srcId), findVertex(se.tgtId), se.value);
1350  }
1351  }
1352 
1353  BOOST_SERIALIZATION_SPLIT_MEMBER();
1354 
1355 
1357  // Initialization
1359 public:
1360 
1366  Graph(const Allocator &allocator = Allocator()): edges_(allocator), vertices_(allocator) {};
1367 
1378  Graph(const Graph &other)
1379  : edges_(other.edges_.allocator()), vertices_(other.vertices_.allocator()) {
1380  *this = other;
1381  }
1382 
1391  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1392  Graph(const Graph<V2, E2, VKey2, EKey2, Alloc2> &other, const Allocator &allocator = Allocator())
1393  : edges_(allocator), vertices_(allocator) {
1394  *this = other;
1395  }
1396 
1404  Graph& operator=(const Graph &other) {
1405  return operator=<V, E>(other);
1406  }
1407 
1419  template<class V2, class E2, class VKey2, class EKey2, class Alloc2>
1421  clear();
1422  for (size_t i=0; i<other.nVertices(); ++i) {
1424  VertexIterator inserted SAWYER_ATTR_UNUSED = insertVertex(VertexValue(vertex->value()));
1425  ASSERT_require(inserted->id() == i);
1426  }
1427  for (size_t i=0; i<other.nEdges(); ++i) {
1429  VertexIterator vsrc = findVertex(edge->source()->id());
1430  VertexIterator vtgt = findVertex(edge->target()->id());
1431  insertEdge(vsrc, vtgt, EdgeValue(edge->value()));
1432  }
1433  return *this;
1434  }
1435 
1439  const Allocator& allocator() {
1440  return vertices_.allocator();
1441  }
1442 
1444 public:
1445 
1454  boost::iterator_range<VertexIterator> vertices() {
1455  return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1456  VertexIterator(vertices_.nodes().end()));
1457  }
1458  boost::iterator_range<ConstVertexIterator> vertices() const {
1459  return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1460  ConstVertexIterator(vertices_.nodes().end()));
1461  }
1481  boost::iterator_range<VertexValueIterator> vertexValues() {
1482  return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1483  VertexValueIterator(vertices_.nodes().end()));
1484  }
1485  boost::iterator_range<ConstVertexValueIterator> vertexValues() const {
1486  return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1487  ConstVertexValueIterator(vertices_.nodes().end()));
1488  }
1501  VertexIterator findVertex(size_t id) {
1502  return VertexIterator(vertices_.find(id));
1503  }
1504  ConstVertexIterator findVertex(size_t id) const {
1505  return ConstVertexIterator(vertices_.find(id));
1506  }
1519  VertexIterator findVertexKey(const VertexKey &key) {
1520  if (Optional<ConstVertexIterator> ov = vertexIndex_.lookup(key))
1521  return findVertex((*ov)->id());
1522  return vertices().end();
1523  }
1524  ConstVertexIterator findVertexKey(const VertexKey &key) const {
1525  return vertexIndex_.lookup(key).orElse(vertices().end());
1526  }
1539  VertexIterator findVertexValue(const VertexValue &value) {
1540  return findVertexKey(VertexKey(value));
1541  }
1542  ConstVertexIterator findVertexValue(const VertexValue &value) const {
1543  return findVertexKey(VertexKey(value));
1544  }
1551  bool isValidVertex(const ConstVertexIterator &vertex) const {
1552  return vertex!=vertices().end() && vertex->id()<nVertices() && vertex==findVertex(vertex->id());
1553  }
1554 
1563  boost::iterator_range<EdgeIterator> edges() {
1564  return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1565  EdgeIterator(edges_.nodes().end()));
1566  }
1567  boost::iterator_range<ConstEdgeIterator> edges() const {
1568  return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1569  ConstEdgeIterator(edges_.nodes().end()));
1570  }
1590  boost::iterator_range<EdgeValueIterator> edgeValues() {
1591  return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1592  EdgeValueIterator(edges_.nodes().end()));
1593  }
1594  boost::iterator_range<ConstEdgeValueIterator> edgeValues() const {
1595  return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1596  ConstEdgeValueIterator(edges_.nodes().end()));
1597  }
1610  EdgeIterator findEdge(size_t id) {
1611  return EdgeIterator(edges_.find(id));
1612  }
1613  ConstEdgeIterator findEdge(size_t id) const {
1614  return ConstEdgeIterator(edges_.find(id));
1615  }
1628  EdgeIterator findEdgeKey(const EdgeKey &key) {
1629  if (Optional<ConstEdgeIterator> oe = edgeIndex_.lookup(key))
1630  return findEdge((*oe)->id());
1631  return edges().end();
1632  }
1633  ConstEdgeIterator findEdgeKey(const EdgeKey &key) const {
1634  return edgeIndex_.lookup(key).orElse(edges().end());
1635  }
1648  EdgeIterator findEdgeValue(const EdgeValue &value) {
1649  return findEdgeKey(EdgeKey(value));
1650  }
1651  ConstEdgeIterator findEdgeValue(const EdgeValue &value) const {
1652  return findEdgeValue(EdgeKey(value));
1653  }
1660  bool isValidEdge(const ConstEdgeIterator &edge) const {
1661  return edge!=edges().end() && edge->id()<nEdges() && edge==findEdge(edge->id());
1662  }
1663 
1670  size_t nVertices() const {
1671  return vertices_.size();
1672  }
1673 
1680  size_t nEdges() const {
1681  return edges_.size();
1682  }
1683 
1689  bool isEmpty() const {
1690  ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty()); // existence of edges implies existence of vertices
1691  return vertices_.isEmpty();
1692  }
1693 
1706  VertexIterator insertVertex(const VertexValue &value = VertexValue()) {
1707  return insertVertexImpl(value, true /*strict*/);
1708  }
1709 
1718  VertexIterator insertVertexMaybe(const VertexValue &value) {
1719  return insertVertexImpl(value, false /*non-strict*/);
1720  }
1721 
1736  EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1737  const EdgeValue &value = EdgeValue()) {
1738  return insertEdgeImpl(sourceVertex, targetVertex, value, true /*strict*/);
1739  }
1740  EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1741  const EdgeValue &value = EdgeValue()) {
1742  ASSERT_require(isValidVertex(sourceVertex));
1743  ASSERT_require(isValidVertex(targetVertex));
1744  return insertEdge(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1745  }
1758  EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
1759  const EdgeValue &value = EdgeValue()) {
1760  return insertEdgeImpl(sourceVertex, targetVertex, value, false /*non-strict*/);
1761  }
1762  EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex,
1763  const EdgeValue &value = EdgeValue()) {
1764  ASSERT_require(isValidVertex(sourceVertex));
1765  ASSERT_require(isValidVertex(targetVertex));
1766  return insertEdgeMaybe(findVertex(sourceVertex->id()), findVertex(targetVertex->id()), value);
1767  }
1774  EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue,
1775  const EdgeValue &edgeValue = EdgeValue()) {
1776  VertexIterator source = insertVertexMaybe(sourceValue);
1777  VertexIterator target = insertVertexMaybe(targetValue);
1778  return insertEdge(source, target, edgeValue);
1779  }
1780 
1796  EdgeIterator eraseEdge(const EdgeIterator &edge) {
1797  ASSERT_require(isValidEdge(edge));
1798  EdgeIterator next = edge; ++next; // advance before we delete edge
1799  edgeIndex_.erase(EdgeKey(edge->value()));
1800  --edge->source_->nOutEdges_;
1801  edge->edgeLists_.remove(OUT_EDGES);
1802  --edge->target_->nInEdges_;
1803  edge->edgeLists_.remove(IN_EDGES);
1804  edges_.eraseAt(edge->self_); // edge is now deleted
1805  return next;
1806  }
1807  EdgeIterator eraseEdge(const ConstEdgeIterator &edge) {
1808  ASSERT_require(isValidEdge(edge));
1809  return eraseEdge(findEdge(edge->id()));
1810  }
1822  EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge) {
1823  ASSERT_require(isValidEdge(edge));
1824  VertexIterator source = edge->source();
1825  VertexIterator target = edge->target();
1826  EdgeIterator retval = eraseEdge(edge);
1827  if (source == target) {
1828  if (source->degree() == 0)
1829  eraseVertex(source);
1830  } else {
1831  if (source->degree() == 0)
1832  eraseVertex(source);
1833  if (target->degree() == 0)
1834  eraseVertex(target);
1835  }
1836  return retval;
1837  }
1838 
1848  void eraseEdges(const VertexIterator &source, const VertexIterator &target) {
1849  ASSERT_require(isValidVertex(source));
1850  ASSERT_require(isValidVertex(target));
1851  if (source->nOutEdges() < target->nInEdges()) {
1852  EdgeIterator iter = source->outEdges().begin();
1853  while (iter != source->outEdges().end()) {
1854  if (iter->target() == target) {
1855  iter = eraseEdge(iter);
1856  } else {
1857  ++iter;
1858  }
1859  }
1860  } else {
1861  EdgeIterator iter = target->inEdges().begin();
1862  while (iter != target->inEdges().end()) {
1863  if (iter->source() == source) {
1864  iter = eraseEdge(iter);
1865  } else {
1866  ++iter;
1867  }
1868  }
1869  }
1870  }
1871  void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target) {
1872  ASSERT_require(isValidVertex(source));
1873  ASSERT_require(isValidVertex(target));
1874  eraseEdges(findVertex(source->id()), findVertex(target->id()));
1875  }
1894  VertexIterator eraseVertex(const VertexIterator &vertex) {
1895  ASSERT_require(isValidVertex(vertex));
1896  VertexIterator next = vertex; ++next; // advance before we delete vertex
1897  clearEdges(vertex);
1898  vertexIndex_.erase(VertexKey(vertex->value()));
1899  vertices_.eraseAt(vertex->self_); // vertex is now deleted
1900  return next;
1901  }
1902  VertexIterator eraseVertex(const ConstVertexIterator &vertex) {
1903  ASSERT_require(isValidVertex(vertex));
1904  return eraseVertex(findVertex(vertex->id()));
1905  }
1914  void clearEdges() {
1915  for (VertexIterator vertex=vertices().begin(); vertex!=vertices().end(); ++vertex) {
1916  vertex->inEdges().reset();
1917  vertex->outEdges().reset();
1918  }
1919  edges_.clear();
1920  edgeIndex_.clear();
1921  }
1922 
1933  void clearEdges(const VertexIterator &vertex) {
1934  clearOutEdges(vertex);
1935  clearInEdges(vertex);
1936  }
1937  void clearEdges(const ConstVertexIterator &vertex) {
1938  clearOutEdges(vertex);
1939  clearInEdges(vertex);
1940  }
1952  void clearOutEdges(const VertexIterator &vertex) {
1953  ASSERT_forbid(vertex==vertices().end());
1954  for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); /*void*/)
1955  edge = eraseEdge(edge);
1956  }
1957  void clearOutEdges(const ConstVertexIterator &vertex) {
1958  ASSERT_forbid(vertex==vertices().end());
1959  clearOutEdges(findVertex(vertex->id()));
1960  }
1972  void clearInEdges(const VertexIterator &vertex) {
1973  ASSERT_forbid(vertex==vertices().end());
1974  for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); /*void*/)
1975  edge = eraseEdge(edge);
1976  }
1977  void clearInEdges(const ConstVertexIterator &vertex) {
1978  ASSERT_forbid(vertex==vertices().end());
1979  clearInEdges(findVertex(vertex->id()));
1980  }
1990  void clear() {
1991  edges_.clear();
1992  vertices_.clear();
1993  edgeIndex_.clear();
1994  vertexIndex_.clear();
1995  }
1996 
1998  // Internal implementation details
2000 private:
2001  VertexIterator insertVertexImpl(const VertexValue &value, bool strict) {
2002  const VertexKey key(value);
2003  if (Optional<ConstVertexIterator> found = vertexIndex_.lookup(key)) {
2004  if (strict)
2005  throw Exception::AlreadyExists("cannot insert duplicate vertex when graph vertices are indexed");
2006  return findVertex((*found)->id());
2007  }
2008  typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(), Vertex(value));
2009  inserted->value().self_ = inserted;
2010  inserted->value().edgeLists_.reset(NULL); // this is a sublist head, no edge node
2011  VertexIterator retval = VertexIterator(inserted);
2012  vertexIndex_.insert(key, retval);
2013  return retval;
2014  }
2015 
2016  EdgeIterator insertEdgeImpl(const VertexIterator &sourceVertex, const VertexIterator &targetVertex,
2017  const EdgeValue &value, bool strict) {
2018  const EdgeKey key(value);
2019  ASSERT_require(isValidVertex(sourceVertex));
2020  ASSERT_require(isValidVertex(targetVertex));
2021  if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2022  if (strict)
2023  throw Exception::AlreadyExists("cannot insert duplicate edge when graph edges are indexed");
2024  return findEdge((*found)->id());
2025  }
2026  typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(), Edge(value, sourceVertex, targetVertex));
2027  inserted->value().self_ = inserted;
2028  inserted->value().edgeLists_.reset(&inserted->value());
2029  EdgeIterator newEdge(inserted);
2030  sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2031  ++sourceVertex->nOutEdges_;
2032  targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2033  ++targetVertex->nInEdges_;
2034  edgeIndex_.insert(key, newEdge);
2035  return newEdge;
2036  }
2037 
2038 
2040  // Deprecated stuff
2042 public:
2043  // Deprecated [Robb Matzke 2015-03-28]: to be removed on or after 2015-09-28
2044  typedef Edge EdgeNode SAWYER_DEPRECATED("use Edge instead");
2045  typedef Vertex VertexNode SAWYER_DEPRECATED("use Vertex instead");
2046  typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED("use EdgeIterator instead");
2047  typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED("use ConstEdgeIterator instead");
2048  typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED("use VertexIterator instead");
2049  typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED("use ConstVertexIterator instead");
2050 };
2051 
2052 } // namespace
2053 } // namespace
2054 
2055 #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:833
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Definition: Graph.h:1952
Derived operator++(int)
Increment.
Definition: Graph.h:781
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
Definition: Graph.h:1822
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
Definition: Graph.h:1651
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1914
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:1706
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1202
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1894
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1129
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:1524
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:486
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1680
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:817
G::Edge Edge
Edge type including user type and connectivity.
Definition: Graph.h:304
Bidirectional edge value iterator.
Definition: Graph.h:964
Bidirectional vertex node iterator.
Definition: Graph.h:1015
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Definition: Graph.h:1485
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1902
const EdgeValue & value() const
User-defined value.
Definition: Graph.h:1166
Bidirectional edge value iterator.
Definition: Graph.h:987
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:1213
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:1551
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Definition: Graph.h:183
Derived & operator--()
Decrement.
Definition: Graph.h:886
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1807
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:1740
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:868
VertexValue & value()
User-defined value.
Definition: Graph.h:1278
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
Definition: Graph.h:1660
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
Definition: Graph.h:1218
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
Definition: Graph.h:1539
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Definition: Graph.h:1458
Holds a value or nothing.
Definition: Optional.h:49
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
Definition: Graph.h:1420
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1933
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:1454
Bidirectional vertex value iterator.
Definition: Graph.h:1081
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1848
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1736
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1972
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
Definition: Graph.h:1648
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Definition: Graph.h:1590
Bidirectional vertex node iterator.
Definition: Graph.h:1036
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Definition: Graph.h:139
Graph(const Graph &other)
Copy constructor.
Definition: Graph.h:1378
G::Vertex Vertex
Vertex type including user type and connectivity.
Definition: Graph.h:301
Traits for vertex and edge indexing.
Definition: Graph.h:241
Name space for the entire library.
Definition: Access.h:11
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1758
Base class for vertex iterators.
Definition: Graph.h:858
bool operator<(const EdgeBaseIterator &other) const
Iterator comparison.
Definition: Graph.h:839
Derived & operator=(const Derived &other)
Assignment.
Definition: Graph.h:760
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:1234
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:1718
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
Definition: Graph.h:1977
const VertexIterator & source()
Source vertex.
Definition: Graph.h:1139
EdgeValue & value()
User-defined value.
Definition: Graph.h:1165
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
Definition: Graph.h:1594
void clear()
Erase all data from this index.
Definition: Graph.h:203
Derived & operator++()
Increment.
Definition: Graph.h:773
bool operator!=(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:896
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
Definition: Graph.h:1613
ConstVertexIterator source() const
Source vertex.
Definition: Graph.h:1140
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1871
Derived operator++(int)
Increment.
Definition: Graph.h:877
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:1774
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:1519
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
Definition: Graph.h:1481
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1501
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:1504
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:1059
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:1633
void clear()
Remove all vertices and edges.
Definition: Graph.h:1990
size_t degree() const
Number of incident edges.
Definition: Graph.h:1264
bool operator<(const VertexBaseIterator &other) const
Iterator comparison.
Definition: Graph.h:900
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
Definition: Graph.h:1628
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:1610
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:1239
size_t nInEdges() const
Number of incoming edges.
Definition: Graph.h:1249
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Definition: Graph.h:1937
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:628
Type of edge key for graphs that do not index their edges.
Definition: Graph.h:105
Base class for edge iterators.
Definition: Graph.h:737
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:530
Bidirectional edge node iterator.
Definition: Graph.h:937
Bidirectional edge node iterator.
Definition: Graph.h:914
const Allocator & allocator()
Allocator.
Definition: Graph.h:1439
Derived & operator--()
Decrement.
Definition: Graph.h:794
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:1366
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
size_t nOutEdges() const
Number of outgoing edges.
Definition: Graph.h:1256
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
Definition: Graph.h:1542
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Definition: Graph.h:1762
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Definition: Graph.h:1567
Derived operator--(int)
Decrement.
Definition: Graph.h:802
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:1563
bool isEmpty() const
True if graph is empty.
Definition: Graph.h:1689
bool operator==(const OtherIter &other) const
Equality predicate.
Definition: Graph.h:895
Graph & operator=(const Graph &other)
Assignment.
Definition: Graph.h:1404
Derived & operator++()
Increment.
Definition: Graph.h:876
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1796
ConstVertexIterator target() const
Target vertex.
Definition: Graph.h:1152
const VertexIterator & target()
Target vertex.
Definition: Graph.h:1151
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:1392
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:1957
Derived operator--(int)
Decrement.
Definition: Graph.h:887
const VertexValue & value() const
User-defined value.
Definition: Graph.h:1279
bool isSelfEdge() const
Determines if edge is a self-edge.
Definition: Graph.h:1173