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(); }
882 Derived
operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
892 Derived
operator--(
int) { Derived old=*derived(); --*
this;
return old; }
900 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base_; }
901 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base_; }
906 return base_.base() == NULL;
910 Derived* derived() {
return static_cast<Derived*
>(
this); }
911 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
922 VirtualList<Edge> > {
924 VirtualList<Edge> >
Super;
929 EdgeIterator(
const EdgeIterator &other): Super(other) {}
930 EdgeIterator& operator=(
const EdgeIterator &other) { this->
Super::operator=(other);
return *
this; }
931 Edge& operator*()
const {
return this->dereference(); }
932 Edge* operator->()
const {
return &this->dereference(); }
935 EdgeIterator(
const typename EdgeList::NodeIterator &base): Super(base) {}
936 EdgeIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
946 typename EdgeList::ConstNodeIterator,
947 const VirtualList<Edge> > {
949 typename EdgeList::ConstNodeIterator,
950 const VirtualList<Edge> >
Super;
954 ConstEdgeIterator() {}
955 ConstEdgeIterator(
const ConstEdgeIterator &other): Super(other) {}
956 ConstEdgeIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
957 ConstEdgeIterator& operator=(
const ConstEdgeIterator &other) { this->
Super::operator=(other);
return *
this; }
958 const Edge& operator*()
const {
return this->dereference(); }
959 const Edge* operator->()
const {
return &this->dereference(); }
962 ConstEdgeIterator(
const typename EdgeList::ConstNodeIterator &base): Super(base) {}
963 ConstEdgeIterator(EdgePhase phase,
const VirtualList<Edge> *vlist): Super(phase, vlist) {}
974 VirtualList<Edge> > {
976 VirtualList<Edge> >
Super;
978 typedef EdgeValue& Reference;
979 typedef EdgeValue* Pointer;
980 EdgeValueIterator() {}
981 EdgeValueIterator(
const EdgeValueIterator &other): Super(other) {}
982 EdgeValueIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
983 EdgeValueIterator& operator=(
const EdgeValueIterator &other) { this->
Super::operator=(other);
return *
this; }
984 EdgeValue& operator*()
const {
return this->dereference().
value(); }
985 EdgeValue* operator->()
const {
return &this->dereference().
value(); }
988 EdgeValueIterator(
const typename EdgeList::NodeIterator &base): Super(base) {}
989 EdgeValueIterator(EdgePhase phase, VirtualList<Edge> *vlist): Super(phase, vlist) {}
998 typename EdgeList::ConstNodeIterator,
999 const VirtualList<Edge> > {
1001 typename EdgeList::ConstNodeIterator,
1002 const VirtualList<Edge> >
Super;
1004 typedef const EdgeValue& Reference;
1005 typedef const EdgeValue* Pointer;
1006 ConstEdgeValueIterator() {}
1007 ConstEdgeValueIterator(
const ConstEdgeValueIterator &other): Super(other) {}
1008 ConstEdgeValueIterator(
const EdgeValueIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1009 ConstEdgeValueIterator(
const EdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1010 ConstEdgeValueIterator(
const ConstEdgeIterator &other): Super(other.phase_, other.iter_, other.vlist_) {}
1012 const EdgeValue& operator*()
const {
return this->dereference().
value(); }
1013 const EdgeValue* operator->()
const {
return &this->dereference().
value(); }
1016 ConstEdgeValueIterator(
const typename EdgeList::ConstNodeIterator &base): Super(base) {}
1017 ConstEdgeValueIterator(EdgePhase phase,
const VirtualList<Edge> *vlist): Super(phase, vlist) {}
1027 typename VertexList::NodeIterator> {
1029 typename VertexList::NodeIterator>
Super;
1034 VertexIterator(
const VertexIterator &other): Super(other) {}
1035 VertexIterator& operator=(
const VertexIterator &other) { this->
Super::operator=(other);
return *
this; }
1036 Vertex& operator*()
const {
return this->dereference(); }
1037 Vertex* operator->()
const {
return &this->dereference(); }
1040 VertexIterator(
const typename VertexList::NodeIterator &base): Super(base) {}
1049 typename VertexList::ConstNodeIterator> {
1051 typename VertexList::ConstNodeIterator>
Super;
1054 typedef const Vertex*
Pointer;
1055 ConstVertexIterator() {}
1056 ConstVertexIterator(
const ConstVertexIterator &other): Super(other) {}
1057 ConstVertexIterator(
const VertexIterator &other): Super(other.base_) {}
1058 ConstVertexIterator& operator=(
const ConstVertexIterator &other) { this->
Super::operator=(other);
return *
this; }
1059 const Vertex& operator*()
const {
return this->dereference(); }
1060 const Vertex* operator->()
const {
return &this->dereference(); }
1063 ConstVertexIterator(
const typename VertexList::ConstNodeIterator &base): Super(base) {}
1073 typename VertexList::NodeIterator> {
1075 typename VertexList::NodeIterator>
Super;
1077 typedef VertexValue& Reference;
1078 typedef VertexValue* Pointer;
1079 VertexValueIterator() {}
1080 VertexValueIterator(
const VertexValueIterator &other): Super(other) {}
1081 VertexValueIterator(
const VertexIterator &other): Super(other.base_) {}
1082 VertexValueIterator& operator=(
const VertexValueIterator &other) { this->
Super::operator=(other);
return *
this; }
1083 VertexValue& operator*()
const {
return this->dereference().
value(); }
1084 VertexValue* operator->()
const {
return &this->dereference().
value(); }
1087 VertexValueIterator(
const typename VertexList::NodeIterator &base): Super(base) {}
1096 typename VertexList::ConstNodeIterator> {
1098 typename VertexList::ConstNodeIterator>
Super;
1100 typedef const VertexValue& Reference;
1101 typedef const VertexValue* Pointer;
1102 ConstVertexValueIterator() {}
1103 ConstVertexValueIterator(
const ConstVertexValueIterator &other): Super(other) {}
1105 ConstVertexValueIterator(
const VertexIterator &other): Super(other.base_) {}
1107 ConstVertexValueIterator& operator=(
const ConstVertexValueIterator &other) { this->
Super::operator=(other);
return *
this; }
1108 const VertexValue& operator*()
const {
return this->dereference().
value(); }
1109 const VertexValue* operator->()
const {
return &this->dereference().
value(); }
1112 ConstVertexValueIterator(
const typename VertexList::ConstNodeIterator &base): Super(base) {}
1126 VirtualList<Edge> edgeLists_;
1128 typename EdgeList::NodeIterator self_;
1133 : value_(value), source_(source), target_(target) {}
1144 const size_t&
id()
const {
return self_->id(); }
1181 const EdgeValue&
value()
const {
return value_; }
1189 return source_ == target_;
1199 typename VertexList::NodeIterator self_;
1200 VirtualList<Edge> edgeLists_;
1205 Vertex(
const VertexValue &
value): value_(value), nInEdges_(0), nOutEdges_(0) {}
1217 const size_t&
id()
const {
return self_->id(); }
1229 EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1231 return boost::iterator_range<EdgeIterator>(begin, end);
1233 boost::iterator_range<ConstEdgeIterator>
inEdges()
const {
1236 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1250 EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1252 return boost::iterator_range<EdgeIterator>(begin, end);
1254 boost::iterator_range<ConstEdgeIterator>
outEdges()
const {
1257 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1280 return nInEdges_ + nOutEdges_;
1294 const VertexValue&
value()
const {
return value_; }
1303 VertexList vertices_;
1304 EdgeIndex edgeIndex_;
1305 VertexIndex vertexIndex_;
1311 friend class boost::serialization::access;
1313 struct SerializableEdge {
1314 size_t srcId, tgtId;
1318 : srcId(-1), tgtId(-1) {}
1320 SerializableEdge(
size_t srcId,
size_t tgtId,
const EdgeValue &value)
1321 : srcId(srcId), tgtId(tgtId), value(value) {}
1324 void serialize(S &s,
const unsigned ) {
1325 s & BOOST_SERIALIZATION_NVP(srcId);
1326 s & BOOST_SERIALIZATION_NVP(tgtId);
1327 s & BOOST_SERIALIZATION_NVP(value);
1332 void save(S &s,
const unsigned )
const {
1334 s <<BOOST_SERIALIZATION_NVP(nv);
1335 for (
size_t i=0; i<nv; ++i)
1336 s <<boost::serialization::make_nvp(
"vertex",
findVertex(i)->value());
1339 s <<BOOST_SERIALIZATION_NVP(ne);
1340 for (
size_t i=0; i<ne; ++i) {
1341 ConstEdgeIterator edge =
findEdge(i);
1342 SerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1343 s <<BOOST_SERIALIZATION_NVP(se);
1348 void load(S &s,
const unsigned ) {
1351 s >>BOOST_SERIALIZATION_NVP(nv);
1352 for (
size_t i=0; i<nv; ++i) {
1354 s >>boost::serialization::make_nvp(
"vertex", vv);
1359 s >>BOOST_SERIALIZATION_NVP(ne);
1360 for (
size_t i=0; i<ne; ++i) {
1361 SerializableEdge se;
1362 s >>BOOST_SERIALIZATION_NVP(se);
1363 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1368 BOOST_SERIALIZATION_SPLIT_MEMBER();
1406 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1420 return operator=<V, E>(other);
1434 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1437 for (
size_t i=0; i<other.
nVertices(); ++i) {
1440 ASSERT_require(inserted->id() == i);
1442 for (
size_t i=0; i<other.
nEdges(); ++i) {
1455 return vertices_.allocator();
1470 return boost::iterator_range<VertexIterator>(VertexIterator(vertices_.nodes().begin()),
1471 VertexIterator(vertices_.nodes().end()));
1473 boost::iterator_range<ConstVertexIterator>
vertices()
const {
1474 return boost::iterator_range<ConstVertexIterator>(ConstVertexIterator(vertices_.nodes().begin()),
1475 ConstVertexIterator(vertices_.nodes().end()));
1497 return boost::iterator_range<VertexValueIterator>(VertexValueIterator(vertices_.nodes().begin()),
1498 VertexValueIterator(vertices_.nodes().end()));
1501 return boost::iterator_range<ConstVertexValueIterator>(ConstVertexValueIterator(vertices_.nodes().begin()),
1502 ConstVertexValueIterator(vertices_.nodes().end()));
1517 return VertexIterator(vertices_.find(
id));
1520 return ConstVertexIterator(vertices_.find(
id));
1540 return vertexIndex_.lookup(key).orElse(
vertices().end());
1578 boost::iterator_range<EdgeIterator>
edges() {
1579 return boost::iterator_range<EdgeIterator>(EdgeIterator(edges_.nodes().begin()),
1580 EdgeIterator(edges_.nodes().end()));
1582 boost::iterator_range<ConstEdgeIterator>
edges()
const {
1583 return boost::iterator_range<ConstEdgeIterator>(ConstEdgeIterator(edges_.nodes().begin()),
1584 ConstEdgeIterator(edges_.nodes().end()));
1606 return boost::iterator_range<EdgeValueIterator>(EdgeValueIterator(edges_.nodes().begin()),
1607 EdgeValueIterator(edges_.nodes().end()));
1609 boost::iterator_range<ConstEdgeValueIterator>
edgeValues()
const {
1610 return boost::iterator_range<ConstEdgeValueIterator>(ConstEdgeValueIterator(edges_.nodes().begin()),
1611 ConstEdgeValueIterator(edges_.nodes().end()));
1626 return EdgeIterator(edges_.find(
id));
1629 return ConstEdgeIterator(edges_.find(
id));
1646 return edges().end();
1649 return edgeIndex_.lookup(key).orElse(
edges().end());
1686 return vertices_.size();
1696 return edges_.size();
1705 ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty());
1706 return vertices_.isEmpty();
1722 return insertVertexImpl(value,
true );
1734 return insertVertexImpl(value,
false );
1751 EdgeIterator
insertEdge(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
1753 return insertEdgeImpl(sourceVertex, targetVertex, value,
true );
1755 EdgeIterator
insertEdge(
const ConstVertexIterator &sourceVertex,
const ConstVertexIterator &targetVertex,
1773 EdgeIterator
insertEdgeMaybe(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
1775 return insertEdgeImpl(sourceVertex, targetVertex, value,
false );
1777 EdgeIterator
insertEdgeMaybe(
const ConstVertexIterator &sourceVertex,
const ConstVertexIterator &targetVertex,
1790 const EdgeValue &edgeValue =
EdgeValue()) {
1793 return insertEdge(source, target, edgeValue);
1813 EdgeIterator next = edge; ++next;
1814 edgeIndex_.erase(
EdgeKey(edge->value()));
1815 --edge->source_->nOutEdges_;
1816 edge->edgeLists_.remove(OUT_EDGES);
1817 --edge->target_->nInEdges_;
1818 edge->edgeLists_.remove(IN_EDGES);
1819 edges_.eraseAt(edge->self_);
1839 VertexIterator source = edge->source();
1840 VertexIterator target = edge->target();
1842 if (source == target) {
1843 if (source->degree() == 0)
1846 if (source->degree() == 0)
1848 if (target->degree() == 0)
1863 void eraseEdges(
const VertexIterator &source,
const VertexIterator &target) {
1866 if (source->nOutEdges() < target->nInEdges()) {
1867 EdgeIterator iter = source->outEdges().begin();
1868 while (iter != source->outEdges().end()) {
1869 if (iter->target() == target) {
1876 EdgeIterator iter = target->inEdges().begin();
1877 while (iter != target->inEdges().end()) {
1878 if (iter->source() == source) {
1886 void eraseEdges(
const ConstVertexIterator &source,
const ConstVertexIterator &target) {
1911 VertexIterator next = vertex; ++next;
1913 vertexIndex_.erase(
VertexKey(vertex->value()));
1914 vertices_.eraseAt(vertex->self_);
1930 for (VertexIterator vertex=
vertices().begin(); vertex!=
vertices().end(); ++vertex) {
1931 vertex->inEdges().reset();
1932 vertex->outEdges().reset();
1968 ASSERT_forbid(vertex==
vertices().end());
1969 for (EdgeIterator edge=vertex->outEdges().begin(); edge!=vertex->outEdges().end(); )
1973 ASSERT_forbid(vertex==
vertices().end());
1988 ASSERT_forbid(vertex==
vertices().end());
1989 for (EdgeIterator edge=vertex->inEdges().begin(); edge!=vertex->inEdges().end(); )
1993 ASSERT_forbid(vertex==
vertices().end());
2009 vertexIndex_.clear();
2016 VertexIterator insertVertexImpl(
const VertexValue &value,
bool strict) {
2017 const VertexKey key(value);
2023 typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(),
Vertex(value));
2024 inserted->
value().self_ = inserted;
2025 inserted->value().edgeLists_.reset(NULL);
2026 VertexIterator retval = VertexIterator(inserted);
2027 vertexIndex_.insert(key, retval);
2031 EdgeIterator insertEdgeImpl(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
2032 const EdgeValue &value,
bool strict) {
2033 const EdgeKey key(value);
2036 if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2038 throw Exception::AlreadyExists(
"cannot insert duplicate edge when graph edges are indexed");
2041 typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(),
Edge(value, sourceVertex, targetVertex));
2042 inserted->
value().self_ = inserted;
2043 inserted->value().edgeLists_.reset(&inserted->value());
2044 EdgeIterator newEdge(inserted);
2045 sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2046 ++sourceVertex->nOutEdges_;
2047 targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2048 ++targetVertex->nInEdges_;
2049 edgeIndex_.insert(key, newEdge);
2059 typedef Edge EdgeNode SAWYER_DEPRECATED(
"use Edge instead");
2060 typedef Vertex VertexNode SAWYER_DEPRECATED(
"use Vertex instead");
2061 typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED(
"use EdgeIterator instead");
2062 typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED(
"use ConstEdgeIterator instead");
2063 typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED(
"use VertexIterator instead");
2064 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.