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:

typedef Sawyer::Container::Graph<std::string, double> MyGraph;
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:

VertexValueIterator refers to user-defined mutable values
ConstVertexValueIterator refers to user-defined constant values
VertexIterator refers to mutable vertex storage nodes
ConstVertexIterator refers to constant vertex storage nodes

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:

typedef Sawyer::Container::Graph<City, TravelTime, CityKey> CityGraph;

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.

typedef Sawyer::Container::Graph<std::string, double, Sawyer::PoolAllocator> MyGraphFast;

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;
typedef Sawyer::ProxyAllocator<Sawyer::PoolAllocator> PoolProxy;
MyGraphFast g1(PoolProxy(pool));
MyGraphFast g2(PoolProxy(pool));

Complexity guarantees

Time complexity guarantees for graphs without indexes:

Vertex insertion: amortized constant
Edge insertion: amortized constant
Vertex iterator dereference: constant
Edge iterator dereference: constant
Vertex erasure: O(|Ev|), where |Ev| is the number of edges incident to the vertex.
Edge erasure: constant
Vertex lookup by ID: constant
Edge lookup by ID: constant
Graph vertex list: constant
Graph edge list: constant
Vertex in/out edge list: constant
Count graph vertices: constant
Count graph edges: constant
Count in/out edges: constant
Graph deletion: O(|V|+|E|)
Graph copy: O(|V|+|E|)

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 <util/Sawyer/Graph.h>

Inheritance diagram for Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >:

[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...

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...

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 1381 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 1393 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 1407 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 1419 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 1435 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 1454 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

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 1469 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<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 1473 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 1496 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 1500 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

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 1516 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 >::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 1519 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 1534 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 1539 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 findEdge and findEdgeKey.

Definition at line 1666 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 1675 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

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 1685 of file Graph.h.

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 1695 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 1704 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 1721 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 1733 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 1751 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 1755 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 1773 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 1777 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 1789 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 1811 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 1822 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 1837 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 1863 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 1886 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 1909 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 1917 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 1929 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 1948 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 1952 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 1967 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 1972 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 1987 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 1992 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 2005 of file Graph.h.

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

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

Graph.h

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 >

Vertices and Edges

Iterators

Identification Numbers

Graph connectivity

Indexing

BGL Compatibility

Custom allocators

Complexity guarantees

Classes

Public Types

Public Member Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

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 >