ROSE  0.9.9.139
Classes | Public Types | Public Member Functions | List of all members
Sawyer::Container::Graph< V, E, VKey, EKey, Alloc > Class Template Reference

Description

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
class Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >

Graph containing user-defined vertices and edges.

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:

MyGraph graph;
MyGraph::VertexIterator v1 = graph.insertVertex("first vertex");
MyGraph::VertexIterator v2 = graph.insertVertex("second vertex");
graph.insertEdge(v1, v2, 1.2); // v1 and v2 are the source and target vertices

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.

Iterators

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:

MyGraph graph = ...
MyGraph::ConstVertexIterator constVertex = ...; // not the end iterator
MyGraph::VertexIterator vertex = graph.findVertex(constVertex->id());

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:

std::cout <<"Vertex names:\n";
for (MyGraph::ConstVertexIterator vertex=graph.vertices().begin(); vertex!=graph.vertices().end(); ++vertex)
std::cout <<" " << vertex->value() <<"\n";

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:

BOOST_FOREACH (const MyGraph::Vertex &vertex, graph.vertices())
std::cout <<" " <<vertex.value() <<"\n";
BOOST_FOREACH (const std::string &name, graph.vertexValues())
std::cout <<" " <<name <<"\n";

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.

Identification Numbers

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:

for (size_t edgeId=0; edgeId<graph.nEdges(); ++edgeId) {
MyGraph::ConstEdgeIterator edge = graph.findEdge(edgeId);
std::cout <<"Edge " <<edgeId
<<" from vertex " <<edge->source()->id()
<<" to vertex " <<edge->target()->id() <<"\n";
}

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:

std::vector<unsigned long> vertexHashes(graph.nVertices());
BOOST_FOREACH (const MyGraph::Vertex &vertex, graph.vertices())
vertexHashes[vertex.id()] = hash(vertex.value());

Graph connectivity

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:

BOOST_FOREACH (const MyGraph::Vertex &vertex, graph.vertices()) {
std::cout <<"vertex " <<vertex.id() <<"\n";
BOOST_FOREACH (const MyGraph::Edge &edge, vertex.outEdges()) {
std::cout <<" edge " <<edge.id() <<" to vertex " <<edge.target()->id() <<"\n";
}
}

Indexing

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.

struct City {
std::string name;
const State *state;
unsigned population;
std::vector<std::string> zipCodes;
std::vector<std::string> areaCodes;
PhoneBook phoneBook;
// Pretend there are lots more...
};

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:

class CityKey {
std::string key_;
public:
CityKey(const City &city) {
key_ = city.name + ", " + city.state->abbreviation();
}
bool operator<(const CityKey &other) const {
return key_ < other.key_;
}
};

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.

CityGraph::VertexIterator boston = cityGraph.findVertexValue(City("boston", MA));
CityGraph::VertexIterator boston = cityGraph.findVertexKey(CityKey("boston", MA));

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.

BGL Compatibility

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.

Custom allocators

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.

MyGraphFast graph; //uses a default-constructed pool allocator

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:

Sawyer::PoolAllocator pool;
MyGraphFast g1(PoolProxy(pool));
MyGraphFast g2(PoolProxy(pool));

Complexity guarantees

Time complexity guarantees for graphs without indexes:

Insertion is amortized constant time due to a vector-based ID map that may require reallocation.

Definition at line 625 of file Graph.h.

#include <Graph.h>

Inheritance diagram for Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >:
Inheritance graph
[legend]

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. More...
 
typedef E EdgeValue
 User-level data associated with edges. More...
 
typedef VKey VertexKey
 Type for looking up a vertex. More...
 
typedef EKey EdgeKey
 Type for looking up an edge. More...
 
typedef Alloc Allocator
 Allocator for vertex and edge nodes. More...
 
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...
 
Graphoperator= (const Graph &other)
 Assignment. More...
 
template<class V2 , class E2 , class VKey2 , class EKey2 , class Alloc2 >
Graphoperator= (const Graph< V2, E2, VKey2, EKey2, Alloc2 > &other)
 Assignment. More...
 
const Allocatorallocator ()
 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< VertexIteratorvertices ()
 Iterators for all vertices. More...
 
boost::iterator_range< ConstVertexIteratorvertices () const
 Iterators for all vertices. More...
 
boost::iterator_range< VertexValueIteratorvertexValues ()
 Iterators for all vertices. More...
 
boost::iterator_range< ConstVertexValueIteratorvertexValues () 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< EdgeIteratoredges ()
 Iterators for all edges. More...
 
boost::iterator_range< ConstEdgeIteratoredges () const
 Iterators for all edges. More...
 
boost::iterator_range< EdgeValueIteratoredgeValues ()
 Iterators for all edges. More...
 
boost::iterator_range< ConstEdgeValueIteratoredgeValues () 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...
 

Member Typedef Documentation

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
typedef V Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::VertexValue

User-level data associated with vertices.

Definition at line 627 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
typedef E Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::EdgeValue

User-level data associated with edges.

Definition at line 628 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
typedef VKey Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::VertexKey

Type for looking up a vertex.

Definition at line 629 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
typedef EKey Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::EdgeKey

Type for looking up an edge.

Definition at line 630 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
typedef Alloc Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Allocator

Allocator for vertex and edge nodes.

Definition at line 631 of file Graph.h.

Constructor & Destructor Documentation

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Graph ( const Allocator allocator = Allocator())
inline

Default constructor.

Creates an empty graph.

Time complexity is constant.

Definition at line 1366 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Graph ( const Graph< V, E, VKey, EKey, Alloc > &  other)
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.

Definition at line 1378 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
template<class V2 , class E2 , class VKey2 , class EKey2 , class Alloc2 >
Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Graph ( const Graph< V2, E2, VKey2, EKey2, Alloc2 > &  other,
const Allocator allocator = Allocator() 
)
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.

Definition at line 1392 of file Graph.h.

Member Function Documentation

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
Graph& Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator= ( const Graph< V, E, VKey, EKey, Alloc > &  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.

Definition at line 1404 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
template<class V2 , class E2 , class VKey2 , class EKey2 , class Alloc2 >
Graph& Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::operator= ( const Graph< V2, E2, VKey2, EKey2, Alloc2 > &  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 1420 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
const Allocator& Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::allocator ( )
inline

Allocator.

Returns the allocator used for vertices (and probably edges).

Definition at line 1439 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<VertexIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices ( )
inline
template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<ConstVertexIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices ( ) const
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 1458 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<VertexValueIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertexValues ( )
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:

Sawyer::Container::Graph<std::string, ...> graph = ...;
BOOST_FOREACH (const std::string &vertexName, graph.vertexValues())
std::cout <<"name = " <<*vertexName <<"\n";

Time complexity is constant.

Definition at line 1481 of file Graph.h.

Referenced by Rose::BinaryAnalysis::Partitioner2::FunctionCallGraph::functions().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<ConstVertexValueIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertexValues ( ) const
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:

Sawyer::Container::Graph<std::string, ...> graph = ...;
BOOST_FOREACH (const std::string &vertexName, graph.vertexValues())
std::cout <<"name = " <<*vertexName <<"\n";

Time complexity is constant.

Definition at line 1485 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex ( size_t  id)
inline
template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstVertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex ( size_t  id) const
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 1504 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey ( const VertexKey key)
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 1519 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findVertexValue().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstVertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexKey ( const VertexKey key) const
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 1524 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexValue ( const VertexValue value)
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 1539 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstVertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertexValue ( const VertexValue value) const
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 1542 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
bool Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex ( const ConstVertexIterator vertex) const
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 1551 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdge(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeMaybe().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<EdgeIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges ( )
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 1563 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeKey(), Sawyer::Container::Algorithm::graphAllEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidEdge().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<ConstEdgeIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges ( ) const
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 1567 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<EdgeValueIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edgeValues ( )
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:

Sawyer::Container::Graph<..., std::string> graph = ...;
BOOST_FOREACH (const std::string &edgeName, graph.edgeValues())
std::cout <<"name = " <<*edgeName <<"\n";

Time complexity is constant.

Definition at line 1590 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
boost::iterator_range<ConstEdgeValueIterator> Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edgeValues ( ) const
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:

Sawyer::Container::Graph<..., std::string> graph = ...;
BOOST_FOREACH (const std::string &edgeName, graph.edgeValues())
std::cout <<"name = " <<*edgeName <<"\n";

Time complexity is constant.

Definition at line 1594 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge ( size_t  id)
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 1610 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdge(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeKey(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidEdge(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstEdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdge ( size_t  id) const
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 1613 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeKey ( const EdgeKey key)
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 1628 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeValue().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstEdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeKey ( const EdgeKey key) const
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 1633 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeValue ( const EdgeValue value)
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 1648 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeValue().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
ConstEdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findEdgeValue ( const EdgeValue value) const
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 1651 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
bool Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidEdge ( const ConstEdgeIterator edge) const
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 1660 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdge(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdgeWithVertices().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
size_t Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices ( ) const
inline
template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
size_t Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nEdges ( ) const
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 1680 of file Graph.h.

Referenced by Rose::BinaryAnalysis::Partitioner2::GraphViz::BaseEmitter< ControlFlowGraph >::graph(), Sawyer::Container::Algorithm::graphAllEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidEdge(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
bool Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isEmpty ( ) const
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 1689 of file Graph.h.

Referenced by Sawyer::Container::Algorithm::graphIsConnected().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertVertex ( const VertexValue value = VertexValue())
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 1706 of file Graph.h.

Referenced by Sawyer::Container::Algorithm::graphCopySubgraph(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertVertexMaybe ( const VertexValue value)
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 1718 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeWithVertices().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge ( const VertexIterator sourceVertex,
const VertexIterator targetVertex,
const EdgeValue value = EdgeValue() 
)
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 1736 of file Graph.h.

Referenced by Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdge(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeWithVertices(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge ( const ConstVertexIterator sourceVertex,
const ConstVertexIterator targetVertex,
const EdgeValue value = EdgeValue() 
)
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 1740 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe ( const VertexIterator sourceVertex,
const VertexIterator targetVertex,
const EdgeValue value = EdgeValue() 
)
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 1758 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeMaybe().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeMaybe ( const ConstVertexIterator sourceVertex,
const ConstVertexIterator targetVertex,
const EdgeValue value = EdgeValue() 
)
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 1762 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdgeWithVertices ( const VertexValue sourceValue,
const VertexValue targetValue,
const EdgeValue edgeValue = EdgeValue() 
)
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 1774 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge ( const EdgeIterator edge)
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 1796 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearInEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearOutEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdge(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdgeWithVertices(), Sawyer::Container::Algorithm::graphBreakCycles(), and Sawyer::Container::Algorithm::graphEraseParallelEdges().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge ( const ConstEdgeIterator edge)
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 1807 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
EdgeIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdgeWithVertices ( const EdgeIterator edge)
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 1822 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges ( const VertexIterator source,
const VertexIterator 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 1848 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdges().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdges ( const ConstVertexIterator source,
const ConstVertexIterator 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 1871 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex ( const VertexIterator vertex)
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 1894 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdgeWithVertices(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
VertexIterator Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseVertex ( const ConstVertexIterator vertex)
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 1902 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges ( )
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 1914 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges ( const VertexIterator vertex)
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 1933 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearEdges ( const ConstVertexIterator vertex)
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 1937 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges ( const VertexIterator vertex)
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 1952 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearOutEdges().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearOutEdges ( const ConstVertexIterator vertex)
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 1957 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges ( const VertexIterator vertex)
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 1972 of file Graph.h.

Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearInEdges().

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clearInEdges ( const ConstVertexIterator vertex)
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 1977 of file Graph.h.

template<class V = Nothing, class E = Nothing, class VKey = GraphVertexNoKey<V>, class EKey = GraphEdgeNoKey<E>, class Alloc = DefaultAllocator>
void Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::clear ( )
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 1990 of file Graph.h.

Referenced by Rose::BinaryAnalysis::InstructionSemantics2::DataFlowSemantics::RiscOperators::clearGraph(), Rose::BinaryAnalysis::Partitioner2::GraphViz::BaseEmitter< ControlFlowGraph >::graph(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=(), and Rose::BinaryAnalysis::FeasiblePath::reset().


The documentation for this class was generated from the following file: