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>
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>
91 template<
class VertexValue>
104 template<
class EdgeValue>
120 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
134 void insert(
const VertexOrEdgeKey&,
const VertexOrEdgeConstIterator&) {}
139 void erase(
const VertexOrEdgeKey&) {}
155 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
169 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
176 void erase(
const VertexOrEdgeKey &key) {
195 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
197 typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator>
Map;
210 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
217 void erase(
const VertexOrEdgeKey &key) {
225 typename Map::const_iterator found = map_.find(key);
226 if (found == map_.end())
228 return found->second;
240 template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
247 template<
class VertexValue,
class ConstVertexIterator>
253 template<
class EdgeValue,
class ConstEdgeIterator>
260 #define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE) \
262 namespace Container { \
263 template<class VertexOrEdgeConstIterator> \
264 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
265 typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index; \
270 #define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE) \
272 namespace Container { \
273 template<class VertexOrEdgeConstIterator> \
274 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
275 typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index; \
320 typedef const typename G::Vertex
Vertex;
321 typedef const typename G::Edge
Edge;
323 typedef const typename G::EdgeValue
EdgeValue;
636 enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
642 VirtualList *next_[N_PHASES];
643 VirtualList *prev_[N_PHASES];
650 void reset(T* node) {
652 for (
size_t i=0; i<N_PHASES; ++i)
653 next_[i] = prev_[i] =
this;
656 bool isHead()
const {
657 return node_ == NULL;
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;
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;
672 void insert(EdgePhase phase, VirtualList *newNode) {
673 ASSERT_require(phase < N_PHASES);
674 ASSERT_not_null(newNode);
675 ASSERT_forbid(newNode->isHead());
676 ASSERT_require(newNode->isSingleton(phase));
677 prev_[phase]->next_[phase] = newNode;
678 newNode->prev_[phase] = prev_[phase];
679 prev_[phase] = newNode;
680 newNode->next_[phase] =
this;
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;
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]; }
697 ASSERT_forbid(isHead());
701 const T& dereference()
const {
702 ASSERT_forbid(isHead());
703 return *(
const T*)
this;
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";
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);
730 template<
class Derived,
class Value,
class Node,
class BaseIter,
class VList>
734 using iterator_category = std::bidirectional_iterator_tag;
735 using value_type = Value;
736 using difference_type = std::ptrdiff_t;
737 using pointer = Value*;
738 using reference = Value&;
748 EdgeBaseIterator(
const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
749 EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
750 template<
class BaseIter2>
EdgeBaseIterator(EdgePhase phase,
const BaseIter2 &iter, VList *vlist)
751 : phase_(phase), iter_(iter), vlist_(vlist) {}
753 Node& dereference()
const {
754 return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
758 Derived* derived() {
return static_cast<Derived*
>(
this); }
759 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
764 phase_ = other.phase_;
766 vlist_ = other.vlist_;
777 if (N_PHASES==phase_) {
780 vlist_ = &vlist_->next(phase_);
785 Derived old = *derived();
798 if (N_PHASES==phase_) {
801 vlist_ = &vlist_->prev(phase_);
806 Derived old = *derived();
819 template<
class OtherIter>
822 if (N_PHASES==phase_) {
823 a = iter_.isAtEnd() ? NULL : &iter_->value();
825 a = vlist_->isHead() ? NULL : &vlist_->dereference();
828 if (N_PHASES==other.phase_) {
829 b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
831 b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
835 template<
class OtherIter>
837 return !(*
this==other);
843 if (N_PHASES == phase_) {
844 return iter_.isAtEnd();
846 return vlist_->isHead();
852 template<
class Derived,
class Value,
class Node,
class BaseIter>
856 using iterator_category = std::bidirectional_iterator_tag;
857 using value_type = Value;
858 using difference_type = std::ptrdiff_t;
859 using pointer = Value*;
860 using reference = Value&;
869 Node& dereference()
const {
return base_->value(); }
872 Derived&
operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
881 Derived
operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
891 Derived
operator--(
int) { Derived old=*derived(); --*
this;
return old; }
899 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base_; }
900 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base_; }
905 return base_.base() == NULL;
909 Derived* derived() {
return static_cast<Derived*
>(
this); }
910 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
921 VirtualList<Edge> > {
923 VirtualList<Edge> >
Super;
928 EdgeIterator(
const EdgeIterator &other): Super(other) {}
929 Edge& operator*()
const {
return this->dereference(); }
930 Edge* operator->()
const {
return &this->dereference(); }
933 EdgeIterator(
const typename EdgeList::NodeIterator &base): Super(base) {}
934 EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
944 typename EdgeList::ConstNodeIterator,
945 const VirtualList<Edge> > {
947 typename EdgeList::ConstNodeIterator,
948 const VirtualList<Edge> >
Super;
952 ConstEdgeIterator() {}
953 ConstEdgeIterator(
const ConstEdgeIterator &other): Super(other) {}
954 ConstEdgeIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
955 const Edge& operator*()
const {
return this->dereference(); }
956 const Edge* operator->()
const {
return &this->dereference(); }
959 ConstEdgeIterator(
const typename EdgeList::ConstNodeIterator &base): Super(base) {}
960 ConstEdgeIterator(EdgePhase phase,
const VirtualList<Edge> *vlist): Super(phase, vlist) {}
971 VirtualList<Edge> > {
973 VirtualList<Edge> >
Super;
975 typedef EdgeValue& Reference;
976 typedef EdgeValue* Pointer;
977 EdgeValueIterator() {}
978 EdgeValueIterator(
const EdgeValueIterator &other): Super(other) {}
979 EdgeValueIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
980 EdgeValue& operator*()
const {
return this->dereference().
value(); }
981 EdgeValue* operator->()
const {
return &this->dereference().
value(); }
984 EdgeValueIterator(
const typename EdgeList::NodeIterator &base): Super(base) {}
985 EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
994 typename EdgeList::ConstNodeIterator,
995 const VirtualList<Edge> > {
997 typename EdgeList::ConstNodeIterator,
998 const VirtualList<Edge> >
Super;
1000 typedef const EdgeValue& Reference;
1001 typedef const EdgeValue* Pointer;
1002 ConstEdgeValueIterator() {}
1003 ConstEdgeValueIterator(
const ConstEdgeValueIterator &other): Super(other) {}
1004 ConstEdgeValueIterator(
const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1005 ConstEdgeValueIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1006 ConstEdgeValueIterator(
const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1007 const EdgeValue& operator*()
const {
return this->dereference().
value(); }
1008 const EdgeValue* operator->()
const {
return &this->dereference().
value(); }
1011 ConstEdgeValueIterator(
const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1012 ConstEdgeValueIterator(EdgePhase phase,
const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1022 typename VertexList::NodeIterator> {
1024 typename VertexList::NodeIterator>
Super;
1029 VertexIterator(
const VertexIterator &other): Super(other) {}
1030 Vertex& operator*()
const {
return this->dereference(); }
1031 Vertex* operator->()
const {
return &this->dereference(); }
1034 VertexIterator(
const typename VertexList::NodeIterator &base): Super(base) {}
1043 typename VertexList::ConstNodeIterator> {
1045 typename VertexList::ConstNodeIterator>
Super;
1048 typedef const Vertex*
Pointer;
1049 ConstVertexIterator() {}
1050 ConstVertexIterator(
const ConstVertexIterator &other): Super(other) {}
1051 ConstVertexIterator(
const VertexIterator &other): Super(other.base_) {}
1052 const Vertex& operator*()
const {
return this->dereference(); }
1053 const Vertex* operator->()
const {
return &this->dereference(); }
1056 ConstVertexIterator(
const typename VertexList::ConstNodeIterator &base): Super(base) {}
1066 typename VertexList::NodeIterator> {
1068 typename VertexList::NodeIterator>
Super;
1070 typedef VertexValue& Reference;
1071 typedef VertexValue* Pointer;
1072 VertexValueIterator() {}
1073 VertexValueIterator(
const VertexValueIterator &other): Super(other) {}
1074 VertexValueIterator(
const VertexIterator &other): Super(other.base_) {}
1075 VertexValue& operator*()
const {
return this->dereference().
value(); }
1076 VertexValue* operator->()
const {
return &this->dereference().
value(); }
1079 VertexValueIterator(
const typename VertexList::NodeIterator &base): Super(base) {}
1088 typename VertexList::ConstNodeIterator> {
1090 typename VertexList::ConstNodeIterator>
Super;
1092 typedef const VertexValue& Reference;
1093 typedef const VertexValue* Pointer;
1094 ConstVertexValueIterator() {}
1095 ConstVertexValueIterator(
const ConstVertexValueIterator &other): Super(other) {}
1097 ConstVertexValueIterator(
const VertexIterator &other): Super(other.base_) {}
1099 const VertexValue& operator*()
const {
return this->dereference().
value(); }
1100 const VertexValue* operator->()
const {
return &this->dereference().
value(); }
1103 ConstVertexValueIterator(
const typename VertexList::ConstNodeIterator &base): Super(base) {}
1117 VirtualList<Edge> edgeLists_;
1119 typename EdgeList::NodeIterator self_;
1124 : value_(value), source_(source), target_(target) {}
1135 const size_t&
id()
const {
return self_->id(); }
1172 const EdgeValue&
value()
const {
return value_; }
1180 return source_ == target_;
1190 typename VertexList::NodeIterator self_;
1191 VirtualList<Edge> edgeLists_;
1196 Vertex(
const VertexValue &
value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1208 const size_t&
id()
const {
return self_->id(); }
1220 EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1222 return boost::iterator_range<EdgeIterator>(begin, end);
1224 boost::iterator_range<ConstEdgeIterator>
inEdges()
const {
1227 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1241 EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1243 return boost::iterator_range<EdgeIterator>(begin, end);
1245 boost::iterator_range<ConstEdgeIterator>
outEdges()
const {
1248 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1271 return nInEdges_ + nOutEdges_;
1285 const VertexValue&
value()
const {
return value_; }
1294 VertexList vertices_;
1295 EdgeIndex edgeIndex_;
1296 VertexIndex vertexIndex_;
1302 friend class boost::serialization::access;
1304 struct SerializableEdge {
1305 size_t srcId, tgtId;
1309 : srcId(-1), tgtId(-1) {}
1311 SerializableEdge(
size_t srcId,
size_t tgtId,
const EdgeValue &value)
1312 : srcId(srcId), tgtId(tgtId), value(value) {}
1315 void serialize(S &s,
const unsigned ) {
1316 s & BOOST_SERIALIZATION_NVP(srcId);
1317 s & BOOST_SERIALIZATION_NVP(tgtId);
1318 s & BOOST_SERIALIZATION_NVP(value);
1323 void save(S &s,
const unsigned )
const {
1325 s <<BOOST_SERIALIZATION_NVP(nv);
1326 for (
size_t i=0; i<nv; ++i)
1327 s <<boost::serialization::make_nvp(
"vertex",
findVertex(i)->value());
1330 s <<BOOST_SERIALIZATION_NVP(ne);
1331 for (
size_t i=0; i<ne; ++i) {
1332 ConstEdgeIterator edge =
findEdge(i);
1333 SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1334 s <<BOOST_SERIALIZATION_NVP(se);
1339 void load(S &s,
const unsigned ) {
1342 s >>BOOST_SERIALIZATION_NVP(nv);
1343 for (
size_t i=0; i<nv; ++i) {
1345 s >>boost::serialization::make_nvp(
"vertex", vv);
1350 s >>BOOST_SERIALIZATION_NVP(ne);
1351 for (
size_t i=0; i<ne; ++i) {
1352 SerializableEdge se;
1353 s >>BOOST_SERIALIZATION_NVP(se);
1354 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1359 BOOST_SERIALIZATION_SPLIT_MEMBER();
1397 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1411 return operator=<V, E>(other);
1425 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1428 for (
size_t i=0; i<other.
nVertices(); ++i) {
1431 ASSERT_require(inserted->id() == i);
1433 for (
size_t i=0; i<other.
nEdges(); ++i) {
1446 return vertices_.allocator();
1461 return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1462 VertexIterator(vertices_.nodes().end()));
1464 boost::iterator_range<ConstVertexIterator>
vertices()
const {
1465 return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1466 ConstVertexIterator(vertices_.nodes().end()));
1488 return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1489 VertexValueIterator(vertices_.nodes().end()));
1492 return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1493 ConstVertexValueIterator(vertices_.nodes().end()));
1508 return VertexIterator(vertices_.find(
id));
1511 return ConstVertexIterator(vertices_.find(
id));
1531 return vertexIndex_.lookup(key).orElse(
vertices().end());
1569 boost::iterator_range<EdgeIterator>
edges() {
1570 return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1571 EdgeIterator(edges_.nodes().end()));
1573 boost::iterator_range<ConstEdgeIterator>
edges()
const {
1574 return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1575 ConstEdgeIterator(edges_.nodes().end()));
1597 return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1598 EdgeValueIterator(edges_.nodes().end()));
1600 boost::iterator_range<ConstEdgeValueIterator>
edgeValues()
const {
1601 return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1602 ConstEdgeValueIterator(edges_.nodes().end()));
1617 return EdgeIterator(edges_.find(
id));
1620 return ConstEdgeIterator(edges_.find(
id));
1637 return edges().end();
1640 return edgeIndex_.lookup(key).orElse(
edges().end());
1677 return vertices_.size();
1687 return edges_.size();
1696 ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty());
1697 return vertices_.isEmpty();
1713 return insertVertexImpl(value,
true );
1725 return insertVertexImpl(value,
false );
1742 EdgeIterator
insertEdge(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
1744 return insertEdgeImpl(sourceVertex, targetVertex, value,
true );
1746 EdgeIterator
insertEdge(
const ConstVertexIterator &sourceVertex,
const ConstVertexIterator &targetVertex,
1764 EdgeIterator
insertEdgeMaybe(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
1766 return insertEdgeImpl(sourceVertex, targetVertex, value,
false );
1768 EdgeIterator
insertEdgeMaybe(
const ConstVertexIterator &sourceVertex,
const ConstVertexIterator &targetVertex,
1781 const EdgeValue &edgeValue =
EdgeValue()) {
1784 return insertEdge(source, target, edgeValue);
1804 EdgeIterator next = edge; ++next;
1805 edgeIndex_.erase(
EdgeKey(edge->value()));
1806 --edge->source_->nOutEdges_;
1807 edge->edgeLists_.remove(OUT_EDGES);
1808 --edge->target_->nInEdges_;
1809 edge->edgeLists_.remove(IN_EDGES);
1810 edges_.eraseAt(edge->self_);
1830 VertexIterator source = edge->source();
1831 VertexIterator target = edge->target();
1833 if (source == target) {
1834 if (source->degree() == 0)
1837 if (source->degree() == 0)
1839 if (target->degree() == 0)
1854 void eraseEdges(
const VertexIterator &source,
const VertexIterator &target) {
1857 if (source->nOutEdges() < target->nInEdges()) {
1858 EdgeIterator iter = source->outEdges().begin();
1859 while (iter != source->outEdges().end()) {
1860 if (iter->target() == target) {
1867 EdgeIterator iter = target->inEdges().begin();
1868 while (iter != target->inEdges().end()) {
1869 if (iter->source() == source) {
1877 void eraseEdges(
const ConstVertexIterator &source,
const ConstVertexIterator &target) {
1902 VertexIterator next = vertex; ++next;
1904 vertexIndex_.erase(
VertexKey(vertex->value()));
1905 vertices_.eraseAt(vertex->self_);
1921 for (VertexIterator vertex=
vertices().begin(); vertex!=
vertices().end(); ++vertex) {
1922 vertex->inEdges().reset();
1923 vertex->outEdges().reset();
1959 ASSERT_forbid(vertex==
vertices().end());
1960 for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); )
1964 ASSERT_forbid(vertex==
vertices().end());
1979 ASSERT_forbid(vertex==
vertices().end());
1980 for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); )
1984 ASSERT_forbid(vertex==
vertices().end());
2000 vertexIndex_.clear();
2007 VertexIterator insertVertexImpl(
const VertexValue &value,
bool strict) {
2008 const VertexKey key(value);
2014 typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(),
Vertex(value));
2015 inserted->
value().self_ = inserted;
2016 inserted->value().edgeLists_.reset(NULL);
2017 VertexIterator retval = VertexIterator(inserted);
2018 vertexIndex_.insert(key, retval);
2022 EdgeIterator insertEdgeImpl(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
2023 const EdgeValue &value,
bool strict) {
2024 const EdgeKey key(value);
2027 if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2029 throw Exception::AlreadyExists(
"cannot insert duplicate edge when graph edges are indexed");
2032 typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(),
Edge(value, sourceVertex, targetVertex));
2033 inserted->
value().self_ = inserted;
2034 inserted->value().edgeLists_.reset(&inserted->value());
2035 EdgeIterator newEdge(inserted);
2036 sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2037 ++sourceVertex->nOutEdges_;
2038 targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2039 ++targetVertex->nInEdges_;
2040 edgeIndex_.insert(key, newEdge);
2050 typedef Edge EdgeNode SAWYER_DEPRECATED(
"use Edge instead");
2051 typedef Vertex VertexNode SAWYER_DEPRECATED(
"use Vertex instead");
2052 typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED(
"use EdgeIterator instead");
2053 typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED(
"use ConstEdgeIterator instead");
2054 typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED(
"use VertexIterator instead");
2055 typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED(
"use ConstVertexIterator instead");
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &) const
Look up iterator for vertex or edge key.
bool operator!=(const OtherIter &other) const
Equality predicate.
size_t nVertices() const
Total number of vertices.
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
Derived operator++(int)
Increment.
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
void clearEdges()
Erase all edges, but leave all vertices.
void clear()
Erase all data from this index.
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
const size_t & id() const
Unique vertex ID number.
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
const size_t & id() const
Unique edge ID number.
Graph containing user-defined vertices and edges.
ConstVertexIterator findVertexKey(const VertexKey &key) const
Finds a vertex given its key.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
size_t nEdges() const
Total number of edges.
bool operator==(const OtherIter &other) const
Equality predicate.
G::Edge Edge
Edge type including user type and connectivity.
Bidirectional edge value iterator.
Bidirectional vertex node iterator.
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
const EdgeValue & value() const
User-defined value.
Bidirectional edge value iterator.
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Alloc Allocator
Allocator for vertex and edge nodes.
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
bool isEmpty() const
True if iterator doesn't point to anything.
Derived & operator--()
Decrement.
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
VKey VertexKey
Type for looking up a vertex.
EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Derived & operator=(const Derived &other)
Assignment.
VertexValue & value()
User-defined value.
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
Holds a value or nothing.
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
void clear()
Erase all data from this index.
Type of vertex key for graphs that do not index their vertices.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Bidirectional vertex value iterator.
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Map & clear()
Remove all nodes.
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
Bidirectional vertex node iterator.
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
Graph(const Graph &other)
Copy constructor.
G::Vertex Vertex
Vertex type including user type and connectivity.
Name space for the entire library.
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
Base class for vertex iterators.
Derived & operator=(const Derived &other)
Assignment.
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
G::VertexValueIterator VertexValueIterator
Const or non-const vertex value iterator.
VertexIterator insertVertexMaybe(const VertexValue &value)
Optionally insert a new vertex.
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
const VertexIterator & source()
Source vertex.
EdgeValue & value()
User-defined value.
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
void clear()
Erase all data from this index.
Derived & operator++()
Increment.
bool operator!=(const OtherIter &other) const
Equality predicate.
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
ConstVertexIterator source() const
Source vertex.
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
bool isEmpty() const
True if iterator doesn't point to anything.
Derived operator++(int)
Increment.
const char * EdgePhase(int64_t)
Convert Sawyer::Container::Graph::EdgePhase enum constant to a string.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue, const EdgeValue &edgeValue=EdgeValue())
Insert an edge and its vertex end points.
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
VertexIterator findVertexKey(const VertexKey &key)
Finds a vertex given its key.
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
G::VertexValue VertexValue
User-defined vertex type without connectivity information.
ConstVertexIterator findVertex(size_t id) const
Finds the vertex with specified ID number.
G::EdgeValue EdgeValue
User-defined edge type without connectivity information.
Error for existing values.
Bidirectional vertex value iterator.
Extends std::map with methods that return optional values.
Map based index is the default index type when indexes are present.
ConstEdgeIterator findEdgeKey(const EdgeKey &key) const
Finds an edge given its key.
void clear()
Remove all vertices and edges.
size_t degree() const
Number of incident edges.
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
Fake index for graphs that don't have an index.
boost::iterator_range< ConstEdgeIterator > outEdges() const
List of outgoing edges.
size_t nInEdges() const
Number of incoming edges.
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
Map & erase(const Key &key)
Remove a node with specified key.
Type of edge key for graphs that do not index their edges.
Base class for edge iterators.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Bidirectional edge node iterator.
Bidirectional edge node iterator.
const Allocator & allocator()
Allocator.
Derived & operator--()
Decrement.
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Graph(const Allocator &allocator=Allocator())
Default constructor.
V VertexValue
User-level data associated with vertices.
size_t nOutEdges() const
Number of outgoing edges.
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Derived operator--(int)
Decrement.
EKey EdgeKey
Type for looking up an edge.
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
bool isEmpty() const
True if graph is empty.
bool operator==(const OtherIter &other) const
Equality predicate.
Graph & operator=(const Graph &other)
Assignment.
Derived & operator++()
Increment.
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
ConstVertexIterator target() const
Target vertex.
const VertexIterator & target()
Target vertex.
G::EdgeValueIterator EdgeValueIterator
Const or non-const edge value iterator.
Graph(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other, const Allocator &allocator=Allocator())
Copy constructor.
void insert(const VertexOrEdgeKey &, const VertexOrEdgeConstIterator &)
Insert a new element into the map.
E EdgeValue
User-level data associated with edges.
void clearOutEdges(const ConstVertexIterator &vertex)
Erase all edges emanating from a vertex.
Derived operator--(int)
Decrement.
const VertexValue & value() const
User-defined value.
bool isSelfEdge() const
Determines if edge is a self-edge.