ROSE
0.11.96.11
|
Graph containing user-defined vertices and edges.
This container stores user-defined data at each vertex and edge, along with information about the connectivity of vertices through edges. Semantics with respect to storing of user-defined data is similar to the STL's std::list
type; namely, user values are copied into the container when they are inserted, and not copied thereafter. Accessors return references to those values. Edges are always directed and have source and target vertices. Self edges (an edge whose source and target vertex are the same) and parallel edges (two edges both having the same source vertex and both having the same target vertex) are supported.
Here's an example of declaring a graph that stores a string name for each vertex and a floating point weight for each edge:
This example shows a few features of the design: First, like STL containers, there is a clear separation of concerns related to managing the storage and connectivity versus managing the user-defined data stored in the container. Just as an STL container like std::list
is reponsible for managing the list's vertices and the linear connectivity between those vertices, Sawyer is responsible for managing the vertex storage and the connectivity (edges) between the vertices, and the user is responsible for their data (the first two graph template arguments).
Another feature of the design is that iterators serve a dual purpose. Just like an int*
pointing into an array of integers can be used as a pointer to a single element or incremented to iterate through elements, Sawyer graph iterators are both pointers to a particular vertex or edge and at other times incremented to iterate over vertices and edges. Oftentimes incrementing an iterator that's being used as a pointer doesn't really make much sense, just as incrementing an int*
for an array implementation of a lattice/heap/tree/etc might not make much sense.
In this documentation, the term "node" refers to the unit of storage for an edge or vertex, which contains the user-defined value for the edge or vertex, plus an ID number and connectivity information. Within this documentation, the term "vertex" is always used as the name of a graph component (i.e., a graph has vertices and edges), and the term "node" always refers to a unit of storage.
A graph doesn't necessarily need to store data at each vertex or edge. The vertex and edge types default to Nothing, which is similar to void
.
Vertices and edges are referenced via iterators, which are stable across insertion and erasure. That is, an iterator will continue to point to the same vertex or edge even when other vertices or edges are added or removed from the graph. Iterators are the preferred mechanism for referring to a vertex or edge, and are lightweight objects. Iterators, as their name suggests, are also used for iterating over a list of vertices or edges, and "end" iterators indicate the list termination–they point to one-past-the-end of the list. End iterators are generally specific to each list, so any two end iterators from two different lists will typically compare as unequal.
Iterators can refer to just the user-defined value, or the entire storage node. A storage node contains the user-defined value, an ID number, and graph connectivity information and can be implicitly converted to a value iterator. Orthogonally, iterator's referent can be constant or mutable. Vertex iterator names are:
A const-iterator points to information that is const qualified. Const-iterators can be converted to non-const iterators in linear time if one has the non-const graph available:
Edge iterators are similar.
The previous example (using vertex iterators to refer to newly-inserted vertices) should make more sense now. Here's an example using iterators to actually iterate over something:
The graph maintains a graph-wide list of vertices and edges, iterators to which are returned by the vertices and edges methods. The vertexValues and edgeValues methods are related, but return iterators which, when dereferenced, return a reference to the user-defined value for that vertex or edge. The "value" iterators are equality-comparable (==
and !=
) with their "node" iterator counterparts and implicitly constructed from them, but are unable to return information about vertex and edge connectivity (only user-defined values).
Here's a couple easier ways to do the same thing as the previous example:
Sawyer also defines numerous graph traversals that can traverse vertices or edges in certain orders by following the graph connectivity. See Sawyer::Container::Algorithm::GraphTraversal.
Vertices and edges are also given small, consecutive ID numbers beginning at zero–one set for vertices and another set for edges. ID numbers are stable across insertion but not erasure. That is, if an edge is erased from the container then the ID numbers for other edges in the same container may change. Similarly for vertices. An ID number can be converted to an iterator in constant time, and vice versa. Inserting or erasing a vertex or edge is a constant-time operation.
Here's an example that lists all the edges in order of edge ID:
One very useful side effect of having small, consecutive identification numbers is that they can be used as constant time indexing into auxiliary tables. For instance, here's how one might construct a table that contains hash values for all the vertex names:
Each vertex has two additional edge lists: a list of incoming edges where this vertex serves as the edges' target, and a list of outgoing edges where this vertex serves as the edges' source. The lists are returned by the Vertex::inEdges and Vertex::outEdges methods. These lists are sublists of the graph-wide edge list and iterators are equality-comparable and return references to the same underlying edges. However, the "end" iterators for these sublists are all distinct from one another and distinct from the graph-wide edge list. (footnote: Actually, the "end" iterators for the in-coming and out-going lists of a single vertex are equal to each other, but don't depend on this.)
Each edge has two methods, Edge::source and Edge::target that return iterators to the source and target vertices for that edge.
Here's an example similar to the previous edge ID iteration except it presents the graph in terms of vertices:
Users should make every effort to use iterators or ID numbers to point to vertices and edges since these have constant-time performance. However, a drawback of iterators is that if you have a data structure that contains a graph and some iterators your copy constructor will need to update all its iterators so they point to the copied graph rather than the original graph. On the other hand, the drawback of using ID numbers is that erasing vertices and edges might change the ID numbers of other vertices and edges. Therefore, graphs also optionally provide a vertex index and/or edge index that can be used to look up a vertex or edge if you know its key. Keys are anything you want as long as they're computed from the value stored in a vertex or edge. By default, graphs have neither vertex nor edge indexes–they must be enabled by supplying extra template arguments. A graph that has an index does not have the same level of performance as a graph without an index.
Indexing works the same for vertices and edges, although it's most commonly used with vertices. By default, the graph implements a vertex index as a balanced binary tree that maps keys to vertices in O(log) time. Therefore the key type must have a copy constructor and a less-than operator. The library also implements hash-based indexing, in which case the key must satisfy the requirements for boost::unordered_map
instead.
In addition, regardless of what kind of index the graph uses, all keys must be (explicitly) constructable from a vertex value. In practice it's often the case that the vertex values and the keys are the same type. For instance, if a vertex stores std::string
then the key can also be an std::string
since that type has all the properties we need. Distinguishing between vertex value type and vertex key types allows the graph to store larger data structures at the vertices, a small part of which becomes the key. In fact, the key need not be a particular data member of the value as long as the key generator always produces the same key for the same data.
For example, lets say the vertex type is information about a city and that it's quite large.
Every city has a unique name + state pair and we'd like to be able to look up cities in the graph by that pair. So we define a lookup key for cities:
Lets say that the edges between cities represent things like travel time by various modes and we keep this information in a type named TravelTime
. Here's how our graph would be declared:
The only new thing we added is the third template argument, which this causes the graph to contain a vertex index and gives us the ability to look up a city by value or key. The following two lines assume you've added the appropriate constructors to the City
and CityKey
types.
The other thing a vertex index does is prevent us from adding two vertices having the same key–we'd get an Exception::AlreadyExists error. And finally a word of warning: if you define a vertex key and index then the values you store at each vertex (at least the parts from which a key is created) must not change, since doing so will give the vertex a new key without ever updating the index. The only way to change the key fields of a vertex is to insert a new vertex and erase the old one. This happens to be how many indexed containers work, including std::unordered_map
. The same is true for edges.
Some indexed graph demos can be found here.
The Boost Graph Library (BGL) defines an API suitable for operating on a wide variety of graph implementations when the appropriate graph and property traits are defined. In order to operate on a Sawyer graph using the BGL API, the GraphBoost.h header file should be included. See the Sawyer::Boost name space for details.
The main philosophical difference between Sawyer graphs and Boost Graphs is how internal and external properties are stored. Sawyer stores internal properties as user-defined value members within the vertex and edge storage nodes, and uses the small, contiguous vertex and edge ID numbers to look up vector-stored external properties in constant time. BGL graphs abstract internal and external properties to property maps (property maps are a separate part of the Boost library but originated as part of BGL). The Sawyer approach tends to be easier for users to understand because of its similarity to STL containers and its much lighter use of C++ templates in its public API.
The tests/Container/graphBoost.C
file in the Sawyer source tree exemplifies the differences between the Sawyer and BGL approaches and gives examples of using the BGL API on Sawyer graphs.
Because a graph allocates memory in terms of vertex and edge nodes, and because these nodes can be quite small, a graph can often benefit by using a memory pool allocation scheme. The third template argument provides the type for the allocator, and the graph constructors take an allocator argument which is copied into the graph. The allocator must implement the Sawyer::DefaultAllocator API (essentially an allocate and a deallocate method), which happens to use the normal C++ global new
and delete
allocators. A couple possibilities are Sawyer::SynchronizedPoolAllocator and Sawyer::UnsynchronizedPoolAllocator.
Here's a mechanism by which the same pool can be used by multiple graphs. A proxy is needed because allocators are copied by value, but we want all the graphs to share the same pool:
Time complexity guarantees for graphs without indexes:
Insertion is amortized constant time due to a vector-based ID map that may require reallocation.
#include <Graph.h>
Classes | |
class | ConstEdgeIterator |
Bidirectional edge node iterator. More... | |
class | ConstEdgeValueIterator |
Bidirectional edge value iterator. More... | |
class | ConstVertexIterator |
Bidirectional vertex node iterator. More... | |
class | ConstVertexValueIterator |
Bidirectional vertex value iterator. More... | |
class | Edge |
Edge node. More... | |
class | EdgeBaseIterator |
Base class for edge iterators. More... | |
class | EdgeIterator |
Bidirectional edge node iterator. More... | |
class | EdgeValueIterator |
Bidirectional edge value iterator. More... | |
class | Vertex |
Vertex node. More... | |
class | VertexBaseIterator |
Base class for vertex iterators. More... | |
class | VertexIterator |
Bidirectional vertex node iterator. More... | |
class | VertexValueIterator |
Bidirectional vertex value iterator. More... | |
Public Types | |
typedef V | VertexValue |
User-level data associated with vertices. | |
typedef E | EdgeValue |
User-level data associated with edges. | |
typedef VKey | VertexKey |
Type for looking up a vertex. | |
typedef EKey | EdgeKey |
Type for looking up an edge. | |
typedef Alloc | Allocator |
Allocator for vertex and edge nodes. | |
typedef Edge EdgeNode | __attribute__((deprecated)) |
typedef Vertex VertexNode | __attribute__((deprecated)) |
typedef EdgeIterator EdgeNodeIterator | __attribute__((deprecated)) |
typedef ConstEdgeIterator ConstEdgeNodeIterator | __attribute__((deprecated)) |
typedef VertexIterator VertexNodeIterator | __attribute__((deprecated)) |
typedef ConstVertexIterator ConstVertexNodeIterator | __attribute__((deprecated)) |
Public Member Functions | |
Graph (const Allocator &allocator=Allocator()) | |
Default constructor. More... | |
Graph (const Graph &other) | |
Copy constructor. More... | |
template<class V2 , class E2 , class VKey2 , class EKey2 , class Alloc2 > | |
Graph (const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other, const Allocator &allocator=Allocator()) | |
Copy constructor. More... | |
Graph & | operator= (const Graph &other) |
Assignment. More... | |
template<class V2 , class E2 , class VKey2 , class EKey2 , class Alloc2 > | |
Graph & | operator= (const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other) |
Assignment. More... | |
const Allocator & | allocator () |
Allocator. More... | |
bool | isValidVertex (const ConstVertexIterator &vertex) const |
Determines whether the vertex iterator is valid. More... | |
bool | isValidEdge (const ConstEdgeIterator &edge) const |
Determines whether the edge iterator is valid. More... | |
size_t | nVertices () const |
Total number of vertices. More... | |
size_t | nEdges () const |
Total number of edges. More... | |
bool | isEmpty () const |
True if graph is empty. More... | |
VertexIterator | insertVertex (const VertexValue &value=VertexValue()) |
Insert a new vertex. More... | |
VertexIterator | insertVertexMaybe (const VertexValue &value) |
Optionally insert a new vertex. More... | |
EdgeIterator | insertEdgeWithVertices (const VertexValue &sourceValue, const VertexValue &targetValue, const EdgeValue &edgeValue=EdgeValue()) |
Insert an edge and its vertex end points. More... | |
EdgeIterator | eraseEdgeWithVertices (const EdgeIterator &edge) |
Erases and edge and possibly vertices. More... | |
void | clearEdges () |
Erase all edges, but leave all vertices. More... | |
void | clear () |
Remove all vertices and edges. More... | |
boost::iterator_range< VertexIterator > | vertices () |
Iterators for all vertices. More... | |
boost::iterator_range< ConstVertexIterator > | vertices () const |
Iterators for all vertices. More... | |
boost::iterator_range< VertexValueIterator > | vertexValues () |
Iterators for all vertices. More... | |
boost::iterator_range< ConstVertexValueIterator > | vertexValues () const |
Iterators for all vertices. More... | |
VertexIterator | findVertex (size_t id) |
Finds the vertex with specified ID number. More... | |
ConstVertexIterator | findVertex (size_t id) const |
Finds the vertex with specified ID number. More... | |
VertexIterator | findVertexKey (const VertexKey &key) |
Finds a vertex given its key. More... | |
ConstVertexIterator | findVertexKey (const VertexKey &key) const |
Finds a vertex given its key. More... | |
VertexIterator | findVertexValue (const VertexValue &value) |
Finds a vertex given its value. More... | |
ConstVertexIterator | findVertexValue (const VertexValue &value) const |
Finds a vertex given its value. More... | |
boost::iterator_range< EdgeIterator > | edges () |
Iterators for all edges. More... | |
boost::iterator_range< ConstEdgeIterator > | edges () const |
Iterators for all edges. More... | |
boost::iterator_range< EdgeValueIterator > | edgeValues () |
Iterators for all edges. More... | |
boost::iterator_range< ConstEdgeValueIterator > | edgeValues () const |
Iterators for all edges. More... | |
EdgeIterator | findEdge (size_t id) |
Finds the edge with specified ID number. More... | |
ConstEdgeIterator | findEdge (size_t id) const |
Finds the edge with specified ID number. More... | |
EdgeIterator | findEdgeKey (const EdgeKey &key) |
Finds an edge given its key. More... | |
ConstEdgeIterator | findEdgeKey (const EdgeKey &key) const |
Finds an edge given its key. More... | |
EdgeIterator | findEdgeValue (const EdgeValue &value) |
Finds an edge given its value. More... | |
ConstEdgeIterator | findEdgeValue (const EdgeValue &value) const |
Finds an edge given its value. More... | |
EdgeIterator | insertEdge (const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue()) |
Insert a new edge. More... | |
EdgeIterator | insertEdge (const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue()) |
Insert a new edge. More... | |
EdgeIterator | insertEdgeMaybe (const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue()) |
Optionally insert a new edge. More... | |
EdgeIterator | insertEdgeMaybe (const ConstVertexIterator &sourceVertex, const ConstVertexIterator &targetVertex, const EdgeValue &value=EdgeValue()) |
Optionally insert a new edge. More... | |
EdgeIterator | eraseEdge (const EdgeIterator &edge) |
Erases an edge. More... | |
EdgeIterator | eraseEdge (const ConstEdgeIterator &edge) |
Erases an edge. More... | |
void | eraseEdges (const VertexIterator &source, const VertexIterator &target) |
Erases all edges connecting two vertices. More... | |
void | eraseEdges (const ConstVertexIterator &source, const ConstVertexIterator &target) |
Erases all edges connecting two vertices. More... | |
VertexIterator | eraseVertex (const VertexIterator &vertex) |
Erases a vertex and its incident edges. More... | |
VertexIterator | eraseVertex (const ConstVertexIterator &vertex) |
Erases a vertex and its incident edges. More... | |
void | clearEdges (const VertexIterator &vertex) |
Erase all edges incident to a vertex. More... | |
void | clearEdges (const ConstVertexIterator &vertex) |
Erase all edges incident to a vertex. More... | |
void | clearOutEdges (const VertexIterator &vertex) |
Erase all edges emanating from a vertex. More... | |
void | clearOutEdges (const ConstVertexIterator &vertex) |
Erase all edges emanating from a vertex. More... | |
void | clearInEdges (const VertexIterator &vertex) |
Erase all edges targeting a vertex. More... | |
void | clearInEdges (const ConstVertexIterator &vertex) |
Erase all edges targeting a vertex. More... | |
|
inline |
|
inline |
Copy constructor.
Initializes this graph by copying all node and edge data from the other
graph and initializing the same vertex connectivity. Vertices and edges in this new graph will have the same ID numbers as the other
graph, but the order of vertex and edges traversals is not expected to be the same.
The new graph's allocator is copy constructed from the source graph's allocator, which results in the new allocator having the same settings but sharing none of the original data.
Time complexity is linear in the total number of vertices and edges in other
.
|
inline |
Copy constructor.
Initializes this graph by copying all node and edge data from the other
graph and initializing the same vertex connectivity. The vertices and edges of other
must be convertible to the types of vertices and edges in this graph, and the will have the same ID numbers as in the other
graph. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the total number of vertices and edges in other
.
|
inline |
Assignment.
Causes this graph to look like other
in that this graph will have copies of all the other
vertex and edge data and the same vertex connectivity as other
. The vertices and edges will have the same ID numbers as in other
. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the sum of the number of vertices and edges in this graph and other
.
|
inline |
Assignment.
Causes this graph to look like other
in that this graph will have copies of all the other
vertex and edge data and the same vertex connectivity as other
. The vertices and edges of other
must be convertible to the types of vertices and edges in this graph, and they will have the same ID numbers as in other
. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the sum of the number of vertices and edges in this graph and other
.
Warning: Assignment is not currently exception safe. If an exception occurs (e.g., OOM) then the destination graph could be left in an inconsistent state.
Definition at line 1426 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clear(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::source(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::value(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::value().
|
inline |
|
inline |
Iterators for all vertices.
Returns a pair of vertex node iterators that deliniate the list of all vertices of this graph. The traversal of this list is in no particular order.
Time complexity is constant.
Definition at line 1460 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey(), Sawyer::Container::Algorithm::graphAllVertices(), Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphEraseParallelEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex().
|
inline |
|
inline |
Iterators for all vertices.
Returns a pair of vertex value iterators that deliniate the list of all vertices of the graph. The traversal of this list is in no particular order.
Although vertex node iterators are implicitly convertible to vertex value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.
|
inline |
Iterators for all vertices.
Returns a pair of vertex value iterators that deliniate the list of all vertices of the graph. The traversal of this list is in no particular order.
Although vertex node iterators are implicitly convertible to vertex value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.
|
inline |
Finds the vertex with specified ID number.
Returns a vertex node iterator for the vertex with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of vertices contained in this graph.
Time complexity is constant.
See also findVertexValue and findVertexKey.
Definition at line 1507 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey(), Sawyer::Container::Algorithm::graphBreakCycles(), Sawyer::Container::Algorithm::graphContainsCycle(), Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Algorithm::graphDependentOrder(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
Finds the vertex with specified ID number.
Returns a vertex node iterator for the vertex with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of vertices contained in this graph.
Time complexity is constant.
See also findVertexValue and findVertexKey.
|
inline |
Finds a vertex given its key.
Finds a vertex having the specified key and returns an itertor pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index.
Time complexity depends on the vertex index type, but is usually logarithmic in the number of vertices.
See also findVertex and findVertexValue.
Definition at line 1525 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexValue().
|
inline |
Finds a vertex given its key.
Finds a vertex having the specified key and returns an itertor pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index.
Time complexity depends on the vertex index type, but is usually logarithmic in the number of vertices.
See also findVertex and findVertexValue.
Definition at line 1530 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
|
inline |
Finds a vertex given its value.
Finds a vertex having the specified value and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index. This method is just a wrapper around a vertex key constructor followed by a call to findVertexKey for the convenience of the user that doesn't what to remember how to construct a key.
See also findVertex and findVertexKey.
Definition at line 1545 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey().
|
inline |
Finds a vertex given its value.
Finds a vertex having the specified value and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index. This method is just a wrapper around a vertex key constructor followed by a call to findVertexKey for the convenience of the user that doesn't what to remember how to construct a key.
See also findVertex and findVertexKey.
Definition at line 1548 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey().
|
inline |
Determines whether the vertex iterator is valid.
Returns true if and only if the specified iterator is not this graph's end iterator and the iterator points to a vertex in this graph.
Definition at line 1557 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe().
|
inline |
Iterators for all edges.
Returns a pair of edge node iterators that deliniate the list of all edges of this graph. The traversal of this list is in no particular order.
Time complexity is constant.
Definition at line 1569 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeKey(), Sawyer::Container::Algorithm::graphAllEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge().
|
inline |
|
inline |
Iterators for all edges.
Returns a pair of edge value iterators that deliniate the list of all edges of the graph. The traversal of this list is in no particular order.
Although edge node iterators are implicitly convertible to edge value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.
|
inline |
Iterators for all edges.
Returns a pair of edge value iterators that deliniate the list of all edges of the graph. The traversal of this list is in no particular order.
Although edge node iterators are implicitly convertible to edge value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.
|
inline |
Finds the edge with specified ID number.
Returns an edge node iterator for the edge with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of edges contained in this graph.
Time complexity is constant.
See also findEdgeValue and findEdgeKey.
Definition at line 1616 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeKey(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
Finds the edge with specified ID number.
Returns an edge node iterator for the edge with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of edges contained in this graph.
Time complexity is constant.
See also findEdgeValue and findEdgeKey.
|
inline |
Finds an edge given its key.
Finds an edge having the specified key and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no edge index.
Time complexity depends on the edge index type, but is usually logarithmic in the number of edges.
See also findEdge and findEdgeValue.
Definition at line 1634 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeValue().
|
inline |
Finds an edge given its key.
Finds an edge having the specified key and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no edge index.
Time complexity depends on the edge index type, but is usually logarithmic in the number of edges.
See also findEdge and findEdgeValue.
Definition at line 1639 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges().
|
inline |
Finds an edge given its value.
Finds an edge having the specified value and returns an iterator pointing to it, or the end iterator if such an edge does not exist. The end iterator is always returned for graphs that have no edge index. This method is just a wrapper around an edge key constructor followed by a call to findEdgeKey for the convenience of the user that doesn't what to remember how to construct a key.
See also findEdge and findEdgeKey.
Definition at line 1654 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeKey().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeValue().
|
inline |
Finds an edge given its value.
Finds an edge having the specified value and returns an iterator pointing to it, or the end iterator if such an edge does not exist. The end iterator is always returned for graphs that have no edge index. This method is just a wrapper around an edge key constructor followed by a call to findEdgeKey for the convenience of the user that doesn't what to remember how to construct a key.
See also findEdge and findEdgeKey.
Definition at line 1657 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeValue().
|
inline |
Determines whether the edge iterator is valid.
Returns true if and only if the specified iterator is not this graph's end iterator and the iterator points to an edge in this graph.
Definition at line 1666 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::id(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nEdges().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdgeWithVertices().
|
inline |
Total number of vertices.
Returns the total number of vertices in the graph. Vertex ID numbers are guaranteed to be less than this value and greater than or equal to zero.
Time complexity is constant.
Definition at line 1676 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphAllVertices(), Sawyer::Container::Algorithm::graphBreakCycles(), Sawyer::Container::Algorithm::graphContainsCycle(), Sawyer::Container::Algorithm::graphDependentOrder(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
Total number of edges.
Returns the total number of edges in the graph. Edge ID numbers are guaranteed to be less than this value and greater than or equal to zero.
Time complexity is constant.
Definition at line 1686 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphAllEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
True if graph is empty.
Returns true if this graph contains no vertices (and therefore no edges).
Time complexity is constant.
Definition at line 1695 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphIsConnected().
|
inline |
Insert a new vertex.
Inserts a new vertex and copies value
(if specified, or else default-constructed) into the vertex node. Returns an iterator that points to the new vertex. All other vertex iterators that were not already positioned at the one-past-last vertex will eventually traverse this new vertex; no iterators, vertex or edge, are invalidated. The new vertex is given the higest vertex ID number; no other ID numbers, vertex or edge, change.
If this graph has a vertex index and a vertex with the same key already exists then an Exception::AlreadyExists is thrown. See also insertVertexMaybe.
Time complexity is constant for graphs without a vertex index. Looking up the vertex in the index has time complexity depending on the type of index (usually logarithmic in the number of vertices).
Definition at line 1712 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphCopySubgraph(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
Optionally insert a new vertex.
Same as insertVertex except if this graph has a vertex index and a vertex already exists with the same key then a new vertex is not inserted and the iterator of the existing vertex is returned instead. This function always inserts a new vertex for graphs that do not have a vertex index.
Time complexity is constant for graphs without a vertex index. Looking up the vertex in the index has time complexity depending on the type of index (usually logarithmic in the number of vertices).
Definition at line 1724 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeWithVertices().
|
inline |
Insert a new edge.
Inserts a new edge and copies value
(if specified, or else default-constructed) into the edge node. Returns an iterator that points to the new edge. All other edge iterators that were not already positioned at the one-past-last edge will eventually traverse this new edge; no iterators, edge or vertex, are invalidated. The new edge is given the highest edge ID number; no other ID numbers, edge or vertex, change.
If this graph has an edge index and an edge with the same key already exists then an Exception::AlreadyExists is thrown. See also insertEdgeMaybe.
Time complexity is constant for graphs without an edge index. Looking up the edge in the index has time complexity depending on the type of index (usually logirithmic in the number of edges).
Definition at line 1742 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeWithVertices(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().
|
inline |
Insert a new edge.
Inserts a new edge and copies value
(if specified, or else default-constructed) into the edge node. Returns an iterator that points to the new edge. All other edge iterators that were not already positioned at the one-past-last edge will eventually traverse this new edge; no iterators, edge or vertex, are invalidated. The new edge is given the highest edge ID number; no other ID numbers, edge or vertex, change.
If this graph has an edge index and an edge with the same key already exists then an Exception::AlreadyExists is thrown. See also insertEdgeMaybe.
Time complexity is constant for graphs without an edge index. Looking up the edge in the index has time complexity depending on the type of index (usually logirithmic in the number of edges).
Definition at line 1746 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex().
|
inline |
Optionally insert a new edge.
Same as insertEdge except if this graph has an edge index and an edge already exists with the same key then a new edge is not inserted and the iterator of the existing edge is returned instead. This function always inserts a new edge for graphs that do not have an edge index.
Time complexity is constant for graphs without an edge index. Looking up the edge in the index has time complexity depending on the type of index (usually logirithmic in the number of edges).
Definition at line 1764 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe().
|
inline |
Optionally insert a new edge.
Same as insertEdge except if this graph has an edge index and an edge already exists with the same key then a new edge is not inserted and the iterator of the existing edge is returned instead. This function always inserts a new edge for graphs that do not have an edge index.
Time complexity is constant for graphs without an edge index. Looking up the edge in the index has time complexity depending on the type of index (usually logirithmic in the number of edges).
Definition at line 1768 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex().
|
inline |
Insert an edge and its vertex end points.
Invoke insertVertexMaybe for both given vertex values, and then invokes insertEdge to connect the two vertices with an edge.
Definition at line 1780 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertVertexMaybe().
|
inline |
Erases an edge.
The edge specified by the iterator (which must not be a one-past-last iterator) is erased from the graph. The term "erasure" is Standard Template Library terminology for the withdrawal and deletion of an object from a container, and differs from the term "remove", which means to move an object to some near-the-end position in a container. Any edge iterator that was pointing at the erased edge becomes invalid and should not be subsequently dereferenced, incremented, decremented, or compared; other iterators, edge and vertex, are unaffected. The edge with the highest ID number will be given the ID of the edge that was erased in order to fill the gap left in the ID sequence. This method returns an iterator for the edge following the one that was erased (possibly the one-past-last iterator if the last edge was erased).
Time complexity is constant unless the graph has an edge index, in which case time complexity is dependent on the index type (usually logarithmic in the number of edges).
Definition at line 1802 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::value().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdgeWithVertices(), Sawyer::Container::Algorithm::graphBreakCycles(), and Sawyer::Container::Algorithm::graphEraseParallelEdges().
|
inline |
Erases an edge.
The edge specified by the iterator (which must not be a one-past-last iterator) is erased from the graph. The term "erasure" is Standard Template Library terminology for the withdrawal and deletion of an object from a container, and differs from the term "remove", which means to move an object to some near-the-end position in a container. Any edge iterator that was pointing at the erased edge becomes invalid and should not be subsequently dereferenced, incremented, decremented, or compared; other iterators, edge and vertex, are unaffected. The edge with the highest ID number will be given the ID of the edge that was erased in order to fill the gap left in the ID sequence. This method returns an iterator for the edge following the one that was erased (possibly the one-past-last iterator if the last edge was erased).
Time complexity is constant unless the graph has an edge index, in which case time complexity is dependent on the index type (usually logarithmic in the number of edges).
Definition at line 1813 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::id(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge().
|
inline |
Erases and edge and possibly vertices.
Erases the specified edge. If this results in the source vertex having no incoming or outgoing edges then the source vertex is also erased. Similarly for the target vertex when the edge is not a self edge. Erasing of the vertices and edges has the semantics of eraseVertex and eraseEdges, including the affects on iterators and ID numbers, and time complexity.
Returns an iterator for the edge following the one that was erased (possibly the on-past-last iterator if the last edge was erased).
Definition at line 1828 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::source(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target().
|
inline |
Erases all edges connecting two vertices.
Given two vertex iterators, erase all edges whose source is the first vertex and whose target is the second vertex.
For graphs without an edge index, time complexity is linear in the number of incoming or outgoing edges (whichever is smaller). If an edge index is present then time complexity depends on the type of edge index (most indexes have logarithmic lookup time).
Definition at line 1854 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::source(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges().
|
inline |
Erases all edges connecting two vertices.
Given two vertex iterators, erase all edges whose source is the first vertex and whose target is the second vertex.
For graphs without an edge index, time complexity is linear in the number of incoming or outgoing edges (whichever is smaller). If an edge index is present then time complexity depends on the type of edge index (most indexes have logarithmic lookup time).
Definition at line 1877 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex().
|
inline |
Erases a vertex and its incident edges.
The vertex specified by the iterator (which must not be a one-past-last iterator) is erased from the graph along with all edges that originate from or terminate at that vertex. The term "erasure" is Standard Template Library terminology for the withdrawal and deletion of an object from a container, and differs from the term "remove", which means to move an object to some near-the-end position in a container. Any iterator that was pointing at the erased vertex or any of its incident edges becomes invalid and should not be subsequently dereferenced, incremented, decremented, or compared; other iterators, edge and vertex, are unaffected. The vertex with the highest ID number will be given the ID of the vertex that was erased in order to fill the gap left in the ID sequence. This method returns an iterator for the vertex following the one that was erased (possibly the one-past-last iterator if the last vertex was erased).
For a vertex with no incident edges, time complexity is constant unless the graph has a vertex index in which case it depends on the type of index (most vertex indexes have logarithmic lookup/erase time). If the vertex being erased has incoming or outgoing edges then the implementation also calls eraseEdges.
Definition at line 1900 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::value().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdgeWithVertices(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex().
|
inline |
Erases a vertex and its incident edges.
The vertex specified by the iterator (which must not be a one-past-last iterator) is erased from the graph along with all edges that originate from or terminate at that vertex. The term "erasure" is Standard Template Library terminology for the withdrawal and deletion of an object from a container, and differs from the term "remove", which means to move an object to some near-the-end position in a container. Any iterator that was pointing at the erased vertex or any of its incident edges becomes invalid and should not be subsequently dereferenced, incremented, decremented, or compared; other iterators, edge and vertex, are unaffected. The vertex with the highest ID number will be given the ID of the vertex that was erased in order to fill the gap left in the ID sequence. This method returns an iterator for the vertex following the one that was erased (possibly the one-past-last iterator if the last vertex was erased).
For a vertex with no incident edges, time complexity is constant unless the graph has a vertex index in which case it depends on the type of index (most vertex indexes have logarithmic lookup/erase time). If the vertex being erased has incoming or outgoing edges then the implementation also calls eraseEdges.
Definition at line 1908 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex().
|
inline |
Erase all edges, but leave all vertices.
This method erases (withdraws and deletes) all edges but leaves all vertices. It is logically equivalent to calling eraseEdge for each edge, but is more efficient.
Time complexity is linear in the number of edges erased.
Definition at line 1920 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex().
|
inline |
Erase all edges incident to a vertex.
This method erases (withdraws and deletes) all edges that are incident to the specified vertex. That is, all edges whose source or target is the vertex. It is logically equivalent to calling clearOutEdges followed by clearInEdges, and has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.
Definition at line 1939 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges().
|
inline |
Erase all edges incident to a vertex.
This method erases (withdraws and deletes) all edges that are incident to the specified vertex. That is, all edges whose source or target is the vertex. It is logically equivalent to calling clearOutEdges followed by clearInEdges, and has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.
Definition at line 1943 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges().
|
inline |
Erase all edges emanating from a vertex.
This method erases (withdraws and deletes) all edges whose source is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.
Definition at line 1958 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges().
|
inline |
Erase all edges emanating from a vertex.
This method erases (withdraws and deletes) all edges whose source is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.
Definition at line 1963 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
|
inline |
Erase all edges targeting a vertex.
This method erases (withdraws and deletes) all edges whose target is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time..
Definition at line 1978 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::inEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges().
|
inline |
Erase all edges targeting a vertex.
This method erases (withdraws and deletes) all edges whose target is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time..
Definition at line 1983 of file Graph.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
|
inline |
Remove all vertices and edges.
This method has the same effect as erasing edges and vertices individually until the container is empty, but is more efficient. All iterators to vertices and edges in this container become invalid and should not be dereferenced, incremented, decremented, or compared.
Time complexity is linear in the number of vertices and edges erased.
Definition at line 1996 of file Graph.h.
Referenced by Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator=().