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/unordered_map.hpp>
88template<
class VertexValue>
101template<
class EdgeValue>
117template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
131 void insert(
const VertexOrEdgeKey&,
const VertexOrEdgeConstIterator&) {}
136 void erase(
const VertexOrEdgeKey&) {}
152template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
166 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
173 void erase(
const VertexOrEdgeKey &key) {
192template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
194 typedef boost::unordered_map<VertexOrEdgeKey, VertexOrEdgeConstIterator> Map;
207 void insert(
const VertexOrEdgeKey &key,
const VertexOrEdgeConstIterator &iter) {
214 void erase(
const VertexOrEdgeKey &key) {
222 typename Map::const_iterator found = map_.find(key);
223 if (found == map_.end())
225 return found->second;
237template<
class VertexOrEdgeKey,
class VertexOrEdgeConstIterator>
244template<
class VertexValue,
class ConstVertexIterator>
250template<
class EdgeValue,
class ConstEdgeIterator>
257#define SAWYER_GRAPH_INDEXING_SCHEME_1(KEY_TYPE, INDEX_TYPE) \
259 namespace Container { \
260 template<class VertexOrEdgeConstIterator> \
261 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
262 typedef INDEX_TYPE<VertexOrEdgeConstIterator> Index; \
267#define SAWYER_GRAPH_INDEXING_SCHEME_2(KEY_TYPE, INDEX_TYPE) \
269 namespace Container { \
270 template<class VertexOrEdgeConstIterator> \
271 struct GraphIndexTraits<KEY_TYPE, VertexOrEdgeConstIterator> { \
272 typedef INDEX_TYPE<KEY_TYPE, VertexOrEdgeConstIterator> Index; \
327 typedef const typename G::Vertex
Vertex;
328 typedef const typename G::Edge
Edge;
330 typedef const typename G::EdgeValue
EdgeValue;
645 enum EdgePhase { IN_EDGES=0, OUT_EDGES=1, N_PHASES=2 };
651 VirtualList *next_[N_PHASES];
652 VirtualList *prev_[N_PHASES];
659 void reset(T* node) {
661 for (
size_t i=0; i<N_PHASES; ++i)
662 next_[i] = prev_[i] =
this;
665 bool isHead()
const {
666 return node_ == NULL;
669 bool isSingleton(EdgePhase phase)
const {
670 ASSERT_require(phase < N_PHASES);
671 ASSERT_require((next_[phase]==
this && prev_[phase]==
this) || (next_[phase]!=
this && prev_[phase]!=
this));
672 return next_[phase]==
this;
675 bool isEmpty(EdgePhase phase)
const {
676 ASSERT_require(isHead());
677 ASSERT_require((next_[phase]==
this && prev_[phase]==
this) || (next_[phase]!=
this && prev_[phase]!=
this));
678 return next_[phase]==
this;
681 void insert(EdgePhase phase, VirtualList *newNode) {
682 ASSERT_require(phase < N_PHASES);
683 ASSERT_not_null(newNode);
684 ASSERT_forbid(newNode->isHead());
685 ASSERT_require(newNode->isSingleton(phase));
686 prev_[phase]->next_[phase] = newNode;
687 newNode->prev_[phase] = prev_[phase];
688 prev_[phase] = newNode;
689 newNode->next_[phase] =
this;
692 void remove(EdgePhase phase) {
693 ASSERT_require(phase < N_PHASES);
694 ASSERT_forbid(isHead());
695 prev_[phase]->next_[phase] = next_[phase];
696 next_[phase]->prev_[phase] = prev_[phase];
697 next_[phase] = prev_[phase] =
this;
700 VirtualList& next(EdgePhase phase) {
return *next_[phase]; }
701 const VirtualList& next(EdgePhase phase)
const {
return *next_[phase]; }
702 VirtualList& prev(EdgePhase phase) {
return *prev_[phase]; }
703 const VirtualList& prev(EdgePhase phase)
const {
return *prev_[phase]; }
706 ASSERT_forbid(isHead());
710 const T& dereference()
const {
711 ASSERT_forbid(isHead());
712 return *(
const T*)
this;
716 void dump(EdgePhase phase, std::ostream &o)
const {
717 const VirtualList *cur =
this;
718 o <<
" " <<std::setw(18) <<
"Node"
719 <<
"\t" <<std::setw(18) <<
"This"
720 <<
"\t" <<std::setw(18) <<
"Next"
721 <<
"\t" <<std::setw(18) <<
"Prev\n";
723 o <<
" " <<std::setw(18) <<node_
724 <<
"\t" <<std::setw(18) <<cur
725 <<
"\t" <<std::setw(18) <<cur->next_[phase]
726 <<
"\t" <<std::setw(18) <<cur->prev_[phase] <<
"\n";
727 cur = cur->next_[phase];
728 }
while (cur!=
this && cur->next_[phase]!=cur);
739 template<
class Derived,
class Value,
class Node,
class BaseIter,
class VList>
743 using iterator_category = std::bidirectional_iterator_tag;
744 using value_type = Value;
745 using difference_type = std::ptrdiff_t;
746 using pointer = Value*;
747 using reference = Value&;
757 EdgeBaseIterator(
const BaseIter &iter): phase_(N_PHASES), iter_(iter), vlist_(NULL) {}
758 EdgeBaseIterator(EdgePhase phase, VList *vlist): phase_(phase), vlist_(vlist) {}
759 template<
class BaseIter2>
EdgeBaseIterator(EdgePhase phase,
const BaseIter2 &iter, VList *vlist)
760 : phase_(phase), iter_(iter), vlist_(vlist) {}
762 Node& dereference()
const {
763 return N_PHASES==phase_ ? iter_->value() : vlist_->dereference();
767 Derived* derived() {
return static_cast<Derived*
>(
this); }
768 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
773 phase_ = other.phase_;
775 vlist_ = other.vlist_;
786 if (N_PHASES==phase_) {
789 vlist_ = &vlist_->next(phase_);
794 Derived old = *derived();
807 if (N_PHASES==phase_) {
810 vlist_ = &vlist_->prev(phase_);
815 Derived old = *derived();
828 template<
class OtherIter>
831 if (N_PHASES==phase_) {
832 a = iter_.isAtEnd() ? NULL : &iter_->value();
834 a = vlist_->isHead() ? NULL : &vlist_->dereference();
837 if (N_PHASES==other.phase_) {
838 b = other.iter_.isAtEnd() ? NULL : &other.iter_->value();
840 b = other.vlist_->isHead() ? NULL : &other.vlist_->dereference();
844 template<
class OtherIter>
846 return !(*
this==other);
852 if (N_PHASES == phase_) {
853 return iter_.isAtEnd();
855 return vlist_->isHead();
861 template<
class Derived,
class Value,
class Node,
class BaseIter>
865 using iterator_category = std::bidirectional_iterator_tag;
866 using value_type = Value;
867 using difference_type = std::ptrdiff_t;
868 using pointer = Value*;
869 using reference = Value&;
878 Node& dereference()
const {
return base_->value(); }
881 Derived&
operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
891 Derived
operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
901 Derived
operator--(
int) { Derived old=*derived(); --*
this;
return old; }
909 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base_; }
910 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base_; }
915 return base_.base() == NULL;
919 Derived* derived() {
return static_cast<Derived*
>(
this); }
920 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
931 VirtualList<Edge> > {
933 VirtualList<Edge> >
Super;
940 Edge& operator*()
const {
return this->dereference(); }
941 Edge* operator->()
const {
return &this->dereference(); }
955 typename EdgeList::ConstNodeIterator,
956 const VirtualList<Edge> > {
958 typename EdgeList::ConstNodeIterator,
959 const VirtualList<Edge> >
Super;
967 const Edge& operator*()
const {
return this->dereference(); }
968 const Edge* operator->()
const {
return &this->dereference(); }
982 VirtualList<Edge> > {
984 VirtualList<Edge> >
Super;
992 EdgeValue& operator*()
const {
return this->dereference().
value(); }
993 EdgeValue* operator->()
const {
return &this->dereference().
value(); }
1006 typename EdgeList::ConstNodeIterator,
1007 const VirtualList<Edge> > {
1009 typename EdgeList::ConstNodeIterator,
1010 const VirtualList<Edge> >
Super;
1020 const EdgeValue& operator*()
const {
return this->dereference().
value(); }
1021 const EdgeValue* operator->()
const {
return &this->dereference().
value(); }
1035 typename VertexList::NodeIterator> {
1037 typename VertexList::NodeIterator>
Super;
1044 Vertex& operator*()
const {
return this->dereference(); }
1045 Vertex* operator->()
const {
return &this->dereference(); }
1057 typename VertexList::ConstNodeIterator> {
1059 typename VertexList::ConstNodeIterator>
Super;
1067 const Vertex& operator*()
const {
return this->dereference(); }
1068 const Vertex* operator->()
const {
return &this->dereference(); }
1081 typename VertexList::NodeIterator> {
1083 typename VertexList::NodeIterator>
Super;
1104 typename VertexList::ConstNodeIterator> {
1106 typename VertexList::ConstNodeIterator>
Super;
1116 const VertexValue& operator*()
const {
return this->dereference().
value(); }
1117 const VertexValue* operator->()
const {
return &this->dereference().
value(); }
1134 VirtualList<Edge> edgeLists_;
1136 typename EdgeList::NodeIterator self_;
1152 const size_t&
id()
const {
return self_->id(); }
1197 return source_ == target_;
1207 typename VertexList::NodeIterator self_;
1208 VirtualList<Edge> edgeLists_;
1225 const size_t&
id()
const {
return self_->id(); }
1237 EdgeIterator begin(IN_EDGES, &edgeLists_.next(IN_EDGES));
1239 return boost::iterator_range<EdgeIterator>(begin, end);
1241 boost::iterator_range<ConstEdgeIterator>
inEdges()
const {
1244 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1258 EdgeIterator begin(OUT_EDGES, &edgeLists_.next(OUT_EDGES));
1260 return boost::iterator_range<EdgeIterator>(begin, end);
1262 boost::iterator_range<ConstEdgeIterator>
outEdges()
const {
1265 return boost::iterator_range<ConstEdgeIterator>(begin, end);
1288 return nInEdges_ + nOutEdges_;
1311 VertexList vertices_;
1312 EdgeIndex edgeIndex_;
1313 VertexIndex vertexIndex_;
1318#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
1320 friend class boost::serialization::access;
1322 struct BoostSerializableEdge {
1323 size_t srcId, tgtId;
1326 BoostSerializableEdge()
1327 : srcId(-1), tgtId(-1) {}
1329 BoostSerializableEdge(
size_t srcId,
size_t tgtId,
const EdgeValue &value)
1330 : srcId(srcId), tgtId(tgtId), value(value) {}
1333 void serialize(S &s,
const unsigned ) {
1334 s & BOOST_SERIALIZATION_NVP(srcId);
1335 s & BOOST_SERIALIZATION_NVP(tgtId);
1336 s & BOOST_SERIALIZATION_NVP(value);
1341 void save(S &s,
const unsigned )
const {
1343 s <<BOOST_SERIALIZATION_NVP(nv);
1344 for (
size_t i=0; i<nv; ++i)
1345 s <<boost::serialization::make_nvp(
"vertex",
findVertex(i)->value());
1348 s <<BOOST_SERIALIZATION_NVP(ne);
1349 for (
size_t i=0; i<ne; ++i) {
1350 ConstEdgeIterator edge =
findEdge(i);
1351 BoostSerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1352 s <<BOOST_SERIALIZATION_NVP(se);
1357 void load(S &s,
const unsigned ) {
1360 s >>BOOST_SERIALIZATION_NVP(nv);
1361 for (
size_t i=0; i<nv; ++i) {
1363 s >>boost::serialization::make_nvp(
"vertex", vv);
1368 s >>BOOST_SERIALIZATION_NVP(ne);
1369 for (
size_t i=0; i<ne; ++i) {
1370 BoostSerializableEdge se;
1371 s >>BOOST_SERIALIZATION_NVP(se);
1372 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1377 BOOST_SERIALIZATION_SPLIT_MEMBER();
1380#ifdef SAWYER_HAVE_CEREAL
1382 friend class cereal::access;
1384 struct CerealSerializableEdge {
1385 size_t srcId, tgtId;
1388 CerealSerializableEdge()
1389 : srcId(-1), tgtId(-1) {}
1391 CerealSerializableEdge(
size_t srcId,
size_t tgtId,
const EdgeValue &value)
1392 : srcId(srcId), tgtId(tgtId), value(value) {}
1394 template<
class Archive>
1395 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive &archive) {
1396 archive(CEREAL_NVP(srcId));
1397 archive(CEREAL_NVP(tgtId));
1398 archive(CEREAL_NVP(value));
1402 template<
class Archive>
1403 void CEREAL_SAVE_FUNCTION_NAME(Archive &archive)
const {
1405 archive(CEREAL_NVP(nv));
1406 for (
size_t i = 0; i < nv; ++i)
1407 archive(cereal::make_nvp(
"vertex",
findVertex(i)->value()));
1410 archive(CEREAL_NVP(ne));
1411 for (
size_t i = 0; i < ne; ++i) {
1412 ConstEdgeIterator edge =
findEdge(i);
1413 CerealSerializableEdge se(edge->source()->id(), edge->target()->id(), edge->value());
1414 archive(CERAL_NVP(se));
1418 template<
class Archive>
1419 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
1422 archive(CEREAL_NVP(nv));
1423 for (
size_t i = 0; i < nv; ++i) {
1425 archive(cereal::make_nvp(
"vertex", vv));
1430 archive(CEREAL_NVP(ne));
1431 for (
size_t i = 0; i < ne; ++i) {
1432 CerealSerializableEdge se;
1433 archive(CEREAL_NVP(se));
1434 ASSERT_require(se.srcId < nv && se.tgtId < nv);
1475 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1489 return operator=<V, E>(other);
1503 template<
class V2,
class E2,
class VKey2,
class EKey2,
class Alloc2>
1506 for (
size_t i=0; i<other.
nVertices(); ++i) {
1509 ASSERT_require(inserted->id() == i);
1511 for (
size_t i=0; i<other.
nEdges(); ++i) {
1524 return vertices_.allocator();
1539 return boost::iterator_range<VertexIterator>(
VertexIterator(vertices_.nodes().begin()),
1542 boost::iterator_range<ConstVertexIterator>
vertices()
const {
1543 return boost::iterator_range<ConstVertexIterator>(
ConstVertexIterator(vertices_.nodes().begin()),
1566 return boost::iterator_range<VertexValueIterator>(
VertexValueIterator(vertices_.nodes().begin()),
1609 return vertexIndex_.lookup(key).orElse(
vertices().end());
1647 boost::iterator_range<EdgeIterator>
edges() {
1648 return boost::iterator_range<EdgeIterator>(
EdgeIterator(edges_.nodes().begin()),
1651 boost::iterator_range<ConstEdgeIterator>
edges()
const {
1652 return boost::iterator_range<ConstEdgeIterator>(
ConstEdgeIterator(edges_.nodes().begin()),
1675 return boost::iterator_range<EdgeValueIterator>(
EdgeValueIterator(edges_.nodes().begin()),
1678 boost::iterator_range<ConstEdgeValueIterator>
edgeValues()
const {
1715 return edges().end();
1718 return edgeIndex_.lookup(key).orElse(
edges().end());
1755 return vertices_.size();
1765 return edges_.size();
1774 ASSERT_require(edges_.isEmpty() || !vertices_.isEmpty());
1775 return vertices_.isEmpty();
1791 return insertVertexImpl(value,
true );
1803 return insertVertexImpl(value,
false );
1822 return insertEdgeImpl(sourceVertex, targetVertex, value,
true );
1844 return insertEdgeImpl(sourceVertex, targetVertex, value,
false );
1862 return insertEdge(source, target, edgeValue);
1884 --edge->source_->nOutEdges_;
1885 edge->edgeLists_.remove(OUT_EDGES);
1886 --edge->target_->nInEdges_;
1887 edge->edgeLists_.remove(IN_EDGES);
1888 edges_.eraseAt(edge->self_);
1911 if (source == target) {
1912 if (source->degree() == 0)
1915 if (source->degree() == 0)
1917 if (target->degree() == 0)
1935 if (source->nOutEdges() < target->nInEdges()) {
1937 while (iter != source->outEdges().end()) {
1938 if (iter->
target() == target) {
1946 while (iter != target->inEdges().end()) {
1947 if (iter->
source() == source) {
1983 vertices_.eraseAt(vertex->self_);
2000 vertex->inEdges().reset();
2001 vertex->outEdges().reset();
2037 ASSERT_forbid(vertex==
vertices().end());
2042 ASSERT_forbid(vertex==
vertices().end());
2057 ASSERT_forbid(vertex==
vertices().end());
2062 ASSERT_forbid(vertex==
vertices().end());
2078 vertexIndex_.clear();
2085 VertexIterator insertVertexImpl(
const VertexValue &value,
bool strict) {
2092 typename VertexList::NodeIterator inserted = vertices_.insert(vertices_.nodes().end(),
Vertex(value));
2093 inserted->value().self_ = inserted;
2094 inserted->value().edgeLists_.reset(NULL);
2095 VertexIterator retval = VertexIterator(inserted);
2096 vertexIndex_.insert(key, retval);
2100 EdgeIterator insertEdgeImpl(
const VertexIterator &sourceVertex,
const VertexIterator &targetVertex,
2105 if (Optional<ConstEdgeIterator> found = edgeIndex_.lookup(key)) {
2107 throw Exception::AlreadyExists(
"cannot insert duplicate edge when graph edges are indexed");
2110 typename EdgeList::NodeIterator inserted = edges_.insert(edges_.nodes().end(),
Edge(value, sourceVertex, targetVertex));
2111 inserted->value().self_ = inserted;
2112 inserted->value().edgeLists_.reset(&inserted->value());
2113 EdgeIterator newEdge(inserted);
2114 sourceVertex->edgeLists_.insert(OUT_EDGES, &newEdge->edgeLists_);
2115 ++sourceVertex->nOutEdges_;
2116 targetVertex->edgeLists_.insert(IN_EDGES, &newEdge->edgeLists_);
2117 ++targetVertex->nInEdges_;
2118 edgeIndex_.insert(key, newEdge);
2128 typedef Edge EdgeNode SAWYER_DEPRECATED(
"use Edge instead");
2129 typedef Vertex VertexNode SAWYER_DEPRECATED(
"use Vertex instead");
2130 typedef EdgeIterator EdgeNodeIterator SAWYER_DEPRECATED(
"use EdgeIterator instead");
2131 typedef ConstEdgeIterator ConstEdgeNodeIterator SAWYER_DEPRECATED(
"use ConstEdgeIterator instead");
2132 typedef VertexIterator VertexNodeIterator SAWYER_DEPRECATED(
"use VertexIterator instead");
2133 typedef ConstVertexIterator ConstVertexNodeIterator SAWYER_DEPRECATED(
"use ConstVertexIterator instead");
Map based index is the default index type when indexes are present.
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
void clear()
Erase all data from this index.
Type of edge key for graphs that do not index their edges.
void insert(const VertexOrEdgeKey &key, const VertexOrEdgeConstIterator &iter)
Insert a new element into the map.
void clear()
Erase all data from this index.
void erase(const VertexOrEdgeKey &key)
Erase an element from the map.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &key) const
Lookup iterator for vertex or edge key.
Type of vertex key for graphs that do not index their vertices.
Fake index for graphs that don't have an index.
void clear()
Erase all data from this index.
void erase(const VertexOrEdgeKey &)
Erase an element from the map.
void insert(const VertexOrEdgeKey &, const VertexOrEdgeConstIterator &)
Insert a new element into the map.
Optional< VertexOrEdgeConstIterator > lookup(const VertexOrEdgeKey &) const
Look up iterator for vertex or edge key.
Bidirectional edge node iterator.
Bidirectional edge value iterator.
Bidirectional vertex node iterator.
Bidirectional vertex value iterator.
Base class for edge iterators.
bool operator==(const OtherIter &other) const
Equality predicate.
Derived operator++(int)
Increment.
Derived & operator--()
Decrement.
bool operator!=(const OtherIter &other) const
Equality predicate.
bool isEmpty() const
True if iterator doesn't point to anything.
Derived operator--(int)
Decrement.
Derived & operator=(const Derived &other)
Assignment.
Derived & operator++()
Increment.
Bidirectional edge node iterator.
Bidirectional edge value iterator.
EdgeValue & value()
User-defined value.
const VertexIterator & target()
Target vertex.
ConstVertexIterator source() const
Source vertex.
const VertexIterator & source()
Source vertex.
const EdgeValue & value() const
User-defined value.
ConstVertexIterator target() const
Target vertex.
bool isSelfEdge() const
Determines if edge is a self-edge.
const size_t & id() const
Unique edge ID number.
Base class for vertex iterators.
Derived operator--(int)
Decrement.
Derived & operator--()
Decrement.
bool operator==(const OtherIter &other) const
Equality predicate.
bool operator!=(const OtherIter &other) const
Equality predicate.
Derived operator++(int)
Increment.
Derived & operator=(const Derived &other)
Assignment.
bool isEmpty() const
True if iterator doesn't point to anything.
Derived & operator++()
Increment.
Bidirectional vertex node iterator.
Bidirectional vertex value iterator.
const VertexValue & value() const
User-defined value.
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
boost::iterator_range< ConstEdgeIterator > outEdges() const
List of outgoing edges.
size_t nInEdges() const
Number of incoming edges.
size_t nOutEdges() const
Number of outgoing edges.
size_t degree() const
Number of incident edges.
boost::iterator_range< ConstEdgeIterator > inEdges() const
List of incoming edges.
const size_t & id() const
Unique vertex ID number.
VertexValue & value()
User-defined value.
Graph containing user-defined vertices and edges.
E EdgeValue
User-level data associated with edges.
EdgeIterator insertEdgeMaybe(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
void clearEdges()
Erase all edges, but leave all vertices.
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
bool isValidEdge(const ConstEdgeIterator &edge) const
Determines whether the edge iterator is valid.
EKey EdgeKey
Type for looking up an edge.
void clear()
Remove all vertices and edges.
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
ConstEdgeIterator findEdgeKey(const EdgeKey &key) const
Finds an edge given its key.
void clearInEdges(const VertexIterator &vertex)
Erase all edges targeting a vertex.
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
void clearEdges(const VertexIterator &vertex)
Erase all edges incident to a vertex.
void clearOutEdges(const VertexIterator &vertex)
Erase all edges emanating from a vertex.
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
VKey VertexKey
Type for looking up a vertex.
size_t nVertices() const
Total number of vertices.
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
void clearEdges(const ConstVertexIterator &vertex)
Erase all edges incident to a vertex.
void clearInEdges(const ConstVertexIterator &vertex)
Erase all edges targeting a vertex.
EdgeIterator insertEdgeMaybe(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Optionally insert a new edge.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
ConstVertexIterator findVertex(size_t id) const
Finds the vertex with specified ID number.
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
void clearOutEdges(const ConstVertexIterator &vertex)
Erase all edges emanating from a vertex.
EdgeIterator findEdgeValue(const EdgeValue &value)
Finds an edge given its value.
ConstEdgeIterator findEdge(size_t id) const
Finds the edge with specified ID number.
ConstVertexIterator findVertexKey(const VertexKey &key) const
Finds a vertex given its key.
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
ConstEdgeIterator findEdgeValue(const EdgeValue &value) const
Finds an edge given its value.
void eraseEdges(const ConstVertexIterator &source, const ConstVertexIterator &target)
Erases all edges connecting two vertices.
boost::iterator_range< ConstEdgeValueIterator > edgeValues() const
Iterators for all edges.
bool isEmpty() const
True if graph is empty.
Alloc Allocator
Allocator for vertex and edge nodes.
VertexIterator eraseVertex(const ConstVertexIterator &vertex)
Erases a vertex and its incident edges.
boost::iterator_range< VertexValueIterator > vertexValues()
Iterators for all vertices.
EdgeIterator insertEdgeWithVertices(const VertexValue &sourceValue, const VertexValue &targetValue, const EdgeValue &edgeValue=EdgeValue())
Insert an edge and its vertex end points.
EdgeIterator findEdgeKey(const EdgeKey &key)
Finds an edge given its key.
const Allocator & allocator()
Allocator.
VertexIterator findVertexValue(const VertexValue &value)
Finds a vertex given its value.
ConstVertexIterator findVertexValue(const VertexValue &value) const
Finds a vertex given its value.
EdgeIterator eraseEdge(const ConstEdgeIterator &edge)
Erases an edge.
Graph & operator=(const Graph &other)
Assignment.
EdgeIterator eraseEdgeWithVertices(const EdgeIterator &edge)
Erases and edge and possibly vertices.
V VertexValue
User-level data associated with vertices.
Graph & operator=(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
Assignment.
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
VertexIterator insertVertexMaybe(const VertexValue &value)
Optionally insert a new vertex.
Graph(const Allocator &allocator=Allocator())
Default constructor.
EdgeIterator insertEdge(const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
boost::iterator_range< ConstEdgeIterator > edges() const
Iterators for all edges.
Graph(const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other, const Allocator &allocator=Allocator())
Copy constructor.
VertexIterator findVertexKey(const VertexKey &key)
Finds a vertex given its key.
size_t nEdges() const
Total number of edges.
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
boost::iterator_range< ConstVertexIterator > vertices() const
Iterators for all vertices.
boost::iterator_range< EdgeValueIterator > edgeValues()
Iterators for all edges.
boost::iterator_range< ConstVertexValueIterator > vertexValues() const
Iterators for all vertices.
Graph(const Graph &other)
Copy constructor.
Doubly-linked list with constant-time indexing.
Container associating values with keys.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Map & erase(const Key &key)
Remove a node with specified key.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Map & clear()
Remove all nodes.
Error for existing values.
Holds a value or nothing.
G::EdgeValueIterator EdgeValueIterator
Const or non-const edge value iterator.
G::VertexValueIterator VertexValueIterator
Const or non-const vertex value iterator.
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
G::VertexValue VertexValue
User-defined vertex type without connectivity information.
static bool allEdges(const Edge &)
Predicate returning true for all edges.
static bool allVertices(const Vertex &)
Predicate returning true for all vertices.
G::Edge Edge
Edge type including user type and connectivity.
G::EdgeValue EdgeValue
User-defined edge type without connectivity information.
G::Vertex Vertex
Vertex type including user type and connectivity.