ROSE
0.9.10.95

Graph containing userdefined vertices and edges.
This container stores userdefined data at each vertex and edge, along with information about the connectivity of vertices through edges. Semantics with respect to storing of userdefined data is similar to the STL's std::list
type; namely, user values are copied into the container when they are inserted, and not copied thereafter. Accessors return references to those values. Edges are always directed and have source and target vertices. Self edges (an edge whose source and target vertex are the same) and parallel edges (two edges both having the same source vertex and both having the same target vertex) are supported.
Here's an example of declaring a graph that stores a string name for each vertex and a floating point weight for each edge:
This example shows a few features of the design: First, like STL containers, there is a clear separation of concerns related to managing the storage and connectivity versus managing the userdefined 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 userdefined value for the edge or vertex, plus an ID number and connectivity information. Within this documentation, the term "vertex" is always used as the name of a graph component (i.e., a graph has vertices and edges), and the term "node" always refers to a unit of storage.
A graph doesn't necessarily need to store data at each vertex or edge. The vertex and edge types default to Nothing, which is similar to void
.
Vertices and edges are referenced via iterators, which are stable across insertion and erasure. That is, an iterator will continue to point to the same vertex or edge even when other vertices or edges are added or removed from the graph. Iterators are the preferred mechanism for referring to a vertex or edge, and are lightweight objects. Iterators, as their name suggests, are also used for iterating over a list of vertices or edges, and "end" iterators indicate the list termination–they point to onepasttheend 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 userdefined value, or the entire storage node. A storage node contains the userdefined 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 constiterator points to information that is const qualified. Constiterators can be converted to nonconst iterators in linear time if one has the nonconst graph available:
Edge iterators are similar.
The previous example (using vertex iterators to refer to newlyinserted vertices) should make more sense now. Here's an example using iterators to actually iterate over something:
The graph maintains a graphwide 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 userdefined value for that vertex or edge. The "value" iterators are equalitycomparable (==
and !=
) with their "node" iterator counterparts and implicitly constructed from them, but are unable to return information about vertex and edge connectivity (only userdefined values).
Here's a couple easier ways to do the same thing as the previous example:
Sawyer also defines numerous graph traversals that can traverse vertices or edges in certain orders by following the graph connectivity. See Sawyer::Container::Algorithm::GraphTraversal.
Vertices and edges are also given small, consecutive ID numbers beginning at zero–one set for vertices and another set for edges. ID numbers are stable across insertion but not erasure. That is, if an edge is erased from the container then the ID numbers for other edges in the same container may change. Similarly for vertices. An ID number can be converted to an iterator in constant time, and vice versa. Inserting or erasing a vertex or edge is a constanttime operation.
Here's an example that lists all the edges in order of edge ID:
One very useful side effect of having small, consecutive identification numbers is that they can be used as constant time indexing into auxiliary tables. For instance, here's how one might construct a table that contains hash values for all the vertex names:
Each vertex has two additional edge lists: a list of incoming edges where this vertex serves as the edges' target, and a list of outgoing edges where this vertex serves as the edges' source. The lists are returned by the Vertex::inEdges and Vertex::outEdges methods. These lists are sublists of the graphwide edge list and iterators are equalitycomparable 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 graphwide edge list. (footnote: Actually, the "end" iterators for the incoming and outgoing lists of a single vertex are equal to each other, but don't depend on this.)
Each edge has two methods, Edge::source and Edge::target that return iterators to the source and target vertices for that edge.
Here's an example similar to the previous edge ID iteration except it presents the graph in terms of vertices:
Users should make every effort to use iterators or ID numbers to point to vertices and edges since these have constanttime 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 lessthan operator. The library also implements hashbased indexing, in which case the key must satisfy the requirements for boost::unordered_map
instead.
In addition, regardless of what kind of index the graph uses, all keys must be (explicitly) constructable from a vertex value. In practice it's often the case that the vertex values and the keys are the same type. For instance, if a vertex stores std::string
then the key can also be an std::string
since that type has all the properties we need. Distinguishing between vertex value type and vertex key types allows the graph to store larger data structures at the vertices, a small part of which becomes the key. In fact, the key need not be a particular data member of the value as long as the key generator always produces the same key for the same data.
For example, lets say the vertex type is information about a city and that it's quite large.
Every city has a unique name + state pair and we'd like to be able to look up cities in the graph by that pair. So we define a lookup key for cities:
Lets say that the edges between cities represent things like travel time by various modes and we keep this information in a type named TravelTime
. Here's how our graph would be declared:
The only new thing we added is the third template argument, which this causes the graph to contain a vertex index and gives us the ability to look up a city by value or key. The following two lines assume you've added the appropriate constructors to the City
and CityKey
types.
The other thing a vertex index does is prevent us from adding two vertices having the same key–we'd get an Exception::AlreadyExists error. And finally a word of warning: if you define a vertex key and index then the values you store at each vertex (at least the parts from which a key is created) must not change, since doing so will give the vertex a new key without ever updating the index. The only way to change the key fields of a vertex is to insert a new vertex and erase the old one. This happens to be how many indexed containers work, including std::unordered_map
. The same is true for edges.
Some indexed graph demos can be found here.
The Boost Graph Library (BGL) defines an API suitable for operating on a wide variety of graph implementations when the appropriate graph and property traits are defined. In order to operate on a Sawyer graph using the BGL API, the GraphBoost.h header file should be included. See the Sawyer::Boost name space for details.
The main philosophical difference between Sawyer graphs and Boost Graphs is how internal and external properties are stored. Sawyer stores internal properties as userdefined value members within the vertex and edge storage nodes, and uses the small, contiguous vertex and edge ID numbers to look up vectorstored external properties in constant time. BGL graphs abstract internal and external properties to property maps (property maps are a separate part of the Boost library but originated as part of BGL). The Sawyer approach tends to be easier for users to understand because of its similarity to STL containers and its much lighter use of C++ templates in its public API.
The tests/Container/graphBoost.C
file in the Sawyer source tree exemplifies the differences between the Sawyer and BGL approaches and gives examples of using the BGL API on Sawyer graphs.
Because a graph allocates memory in terms of vertex and edge nodes, and because these nodes can be quite small, a graph can often benefit by using a memory pool allocation scheme. The third template argument provides the type for the allocator, and the graph constructors take an allocator argument which is copied into the graph. The allocator must implement the Sawyer::DefaultAllocator API (essentially an allocate and a deallocate method), which happens to use the normal C++ global new
and delete
allocators. A couple possibilities are Sawyer::SynchronizedPoolAllocator and Sawyer::UnsynchronizedPoolAllocator.
Here's a mechanism by which the same pool can be used by multiple graphs. A proxy is needed because allocators are copied by value, but we want all the graphs to share the same pool:
Time complexity guarantees for graphs without indexes:
Insertion is amortized constant time due to a vectorbased ID map that may require reallocation.
#include <Graph.h>
Classes  
class  ConstEdgeIterator 
Bidirectional edge node iterator. More...  
class  ConstEdgeValueIterator 
Bidirectional edge value iterator. More...  
class  ConstVertexIterator 
Bidirectional vertex node iterator. More...  
class  ConstVertexValueIterator 
Bidirectional vertex value iterator. More...  
class  Edge 
Edge node. More...  
class  EdgeBaseIterator 
Base class for edge iterators. More...  
class  EdgeIterator 
Bidirectional edge node iterator. More...  
class  EdgeValueIterator 
Bidirectional edge value iterator. More...  
class  Vertex 
Vertex node. More...  
class  VertexBaseIterator 
Base class for vertex iterators. More...  
class  VertexIterator 
Bidirectional vertex node iterator. More...  
class  VertexValueIterator 
Bidirectional vertex value iterator. More...  
Public Types  
typedef V  VertexValue 
Userlevel data associated with vertices. More...  
typedef E  EdgeValue 
Userlevel 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...  
typedef V Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::VertexValue 
typedef E Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::EdgeValue 
typedef VKey Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::VertexKey 
typedef EKey Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::EdgeKey 
typedef Alloc Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Allocator 

inline 

inline 
Copy constructor.
Initializes this graph by copying all node and edge data from the other
graph and initializing the same vertex connectivity. Vertices and edges in this new graph will have the same ID numbers as the other
graph, but the order of vertex and edges traversals is not expected to be the same.
The new graph's allocator is copy constructed from the source graph's allocator, which results in the new allocator having the same settings but sharing none of the original data.
Time complexity is linear in the total number of vertices and edges in other
.

inline 
Copy constructor.
Initializes this graph by copying all node and edge data from the other
graph and initializing the same vertex connectivity. The vertices and edges of other
must be convertible to the types of vertices and edges in this graph, and the will have the same ID numbers as in the other
graph. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the total number of vertices and edges in other
.

inline 
Assignment.
Causes this graph to look like other
in that this graph will have copies of all the other
vertex and edge data and the same vertex connectivity as other
. The vertices and edges will have the same ID numbers as in other
. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the sum of the number of vertices and edges in this graph and other
.

inline 
Assignment.
Causes this graph to look like other
in that this graph will have copies of all the other
vertex and edge data and the same vertex connectivity as other
. The vertices and edges of other
must be convertible to the types of vertices and edges in this graph, and they will have the same ID numbers as in other
. The order of vertex and edge traversals is not expected to be identical between the two graphs.
Time complexity is linear in the sum of the number of vertices and edges in this graph and other
.
Warning: Assignment is not currently exception safe. If an exception occurs (e.g., OOM) then the destination graph could be left in an inconsistent state.

inline 

inline 
Iterators for all vertices.
Returns a pair of vertex node iterators that deliniate the list of all vertices of this graph. The traversal of this list is in no particular order.
Time complexity is constant.
Definition at line 1448 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearInEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearOutEdges(), Rose::BinaryAnalysis::Partitioner2::Partitioner::findPlaceholder(), Rose::BinaryAnalysis::Partitioner2::DataFlow::findReturnVertex(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findVertexKey(), Rose::BinaryAnalysis::get_ast_node(), Sawyer::Container::Algorithm::graphAllVertices(), Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphEraseParallelEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidVertex(), and Rose::BinaryAnalysis::put_ast_node().

inline 

inline 
Iterators for all vertices.
Returns a pair of vertex value iterators that deliniate the list of all vertices of the graph. The traversal of this list is in no particular order.
Although vertex node iterators are implicitly convertible to vertex value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.
Definition at line 1475 of file Graph.h.
Referenced by Rose::BinaryAnalysis::Partitioner2::FunctionCallGraph::functions().

inline 
Iterators for all vertices.
Returns a pair of vertex value iterators that deliniate the list of all vertices of the graph. The traversal of this list is in no particular order.
Although vertex node iterators are implicitly convertible to vertex value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.

inline 
Finds the vertex with specified ID number.
Returns a vertex node iterator for the vertex with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of vertices contained in this graph.
Time complexity is constant.
See also findVertexValue and findVertexKey.
Definition at line 1495 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearInEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearOutEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdges(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findVertexKey(), Rose::BinaryAnalysis::get_ast_node(), Sawyer::Container::Algorithm::graphBreakCycles(), Sawyer::Container::Algorithm::graphContainsCycle(), Sawyer::Container::Algorithm::graphCopySubgraph(), Sawyer::Container::Algorithm::graphDependentOrder(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdge(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeMaybe(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidVertex(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=(), and Rose::BinaryAnalysis::put_ast_node().

inline 
Finds the vertex with specified ID number.
Returns a vertex node iterator for the vertex with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of vertices contained in this graph.
Time complexity is constant.
See also findVertexValue and findVertexKey.

inline 
Finds a vertex given its key.
Finds a vertex having the specified key and returns an itertor pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index.
Time complexity depends on the vertex index type, but is usually logarithmic in the number of vertices.
See also findVertex and findVertexValue.
Definition at line 1513 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findVertexValue().

inline 
Finds a vertex given its key.
Finds a vertex having the specified key and returns an itertor pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no vertex index.
Time complexity depends on the vertex index type, but is usually logarithmic in the number of vertices.
See also findVertex and findVertexValue.

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.

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.

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 1545 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().

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 1557 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeKey(), Sawyer::Container::Algorithm::graphAllEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidEdge().

inline 

inline 
Iterators for all edges.
Returns a pair of edge value iterators that deliniate the list of all edges of the graph. The traversal of this list is in no particular order.
Although edge node iterators are implicitly convertible to edge value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.

inline 
Iterators for all edges.
Returns a pair of edge value iterators that deliniate the list of all edges of the graph. The traversal of this list is in no particular order.
Although edge node iterators are implicitly convertible to edge value iterators, this method proves useful in conjuction with "foreach" loops:
Time complexity is constant.

inline 
Finds the edge with specified ID number.
Returns an edge node iterator for the edge with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of edges contained in this graph.
Time complexity is constant.
See also findEdgeValue and findEdgeKey.
Definition at line 1604 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=().

inline 
Finds the edge with specified ID number.
Returns an edge node iterator for the edge with the specified ID. ID numbers are consecutive integers beginning at zero. Do not call this method with an ID number greater than or equal to the number of edges contained in this graph.
Time complexity is constant.
See also findEdgeValue and findEdgeKey.

inline 
Finds an edge given its key.
Finds an edge having the specified key and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no edge index.
Time complexity depends on the edge index type, but is usually logarithmic in the number of edges.
See also findEdge and findEdgeValue.
Definition at line 1622 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeValue().

inline 
Finds an edge given its key.
Finds an edge having the specified key and returns an iterator pointing to it, or the end iterator if such a vertex does not exist. The end iterator is always returned for graphs that have no edge index.
Time complexity depends on the edge index type, but is usually logarithmic in the number of edges.
See also findEdge and findEdgeValue.

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 1642 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::findEdgeValue().

inline 
Finds an edge given its value.
Finds an edge having the specified value and returns an iterator pointing to it, or the end iterator if such an edge does not exist. The end iterator is always returned for graphs that have no edge index. This method is just a wrapper around an edge key constructor followed by a call to findEdgeKey for the convenience of the user that doesn't what to remember how to construct a key.
See also findEdge and findEdgeKey.

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 1654 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdge(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdgeWithVertices().

inline 
Total number of vertices.
Returns the total number of vertices in the graph. Vertex ID numbers are guaranteed to be less than this value and greater than or equal to zero.
Time complexity is constant.
Definition at line 1664 of file Graph.h.
Referenced by Rose::BinaryAnalysis::Partitioner2::GraphViz::BaseEmitter< ControlFlowGraph >::graph(), Sawyer::Container::Algorithm::graphAllVertices(), Sawyer::Container::Algorithm::graphBreakCycles(), Sawyer::Container::Algorithm::graphContainsCycle(), Sawyer::Container::Algorithm::graphDependentOrder(), Sawyer::Container::Algorithm::graphDirectedDominators(), Sawyer::Container::Algorithm::graphFindConnectedComponents(), Sawyer::Container::Algorithm::graphIsConnected(), Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::isValidVertex(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

inline 
Total number of edges.
Returns the total number of edges in the graph. Edge ID numbers are guaranteed to be less than this value and greater than or equal to zero.
Time complexity is constant.
Definition at line 1674 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=().

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 1683 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphIsConnected().

inline 
Insert a new vertex.
Inserts a new vertex and copies value
(if specified, or else defaultconstructed) into the vertex node. Returns an iterator that points to the new vertex. All other vertex iterators that were not already positioned at the onepastlast 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 1700 of file Graph.h.
Referenced by Sawyer::Container::Algorithm::graphCopySubgraph(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::operator=().

inline 
Optionally insert a new vertex.
Same as insertVertex except if this graph has a vertex index and a vertex already exists with the same key then a new vertex is not inserted and the iterator of the existing vertex is returned instead. This function always inserts a new vertex for graphs that do not have a vertex index.
Time complexity is constant for graphs without a vertex index. Looking up the vertex in the index has time complexity depending on the type of index (usually logarithmic in the number of vertices).
Definition at line 1712 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeWithVertices().

inline 
Insert a new edge.
Inserts a new edge and copies value
(if specified, or else defaultconstructed) into the edge node. Returns an iterator that points to the new edge. All other edge iterators that were not already positioned at the onepastlast 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 1730 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=().

inline 
Insert a new edge.
Inserts a new edge and copies value
(if specified, or else defaultconstructed) into the edge node. Returns an iterator that points to the new edge. All other edge iterators that were not already positioned at the onepastlast 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).

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 1752 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::insertEdgeMaybe().

inline 
Optionally insert a new edge.
Same as insertEdge except if this graph has an edge index and an edge already exists with the same key then a new edge is not inserted and the iterator of the existing edge is returned instead. This function always inserts a new edge for graphs that do not have an edge index.
Time complexity is constant for graphs without an edge index. Looking up the edge in the index has time complexity depending on the type of index (usually logirithmic in the number of edges).

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.

inline 
Erases an edge.
The edge specified by the iterator (which must not be a onepastlast 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 neartheend 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 onepastlast 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 1790 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().

inline 
Erases an edge.
The edge specified by the iterator (which must not be a onepastlast 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 neartheend 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 onepastlast 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).

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 onpastlast iterator if the last edge was erased).

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 1842 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdges().

inline 
Erases all edges connecting two vertices.
Given two vertex iterators, erase all edges whose source is the first vertex and whose target is the second vertex.
For graphs without an edge index, time complexity is linear in the number of incoming or outgoing edges (whichever is smaller). If an edge index is present then time complexity depends on the type of edge index (most indexes have logarithmic lookup time).

inline 
Erases a vertex and its incident edges.
The vertex specified by the iterator (which must not be a onepastlast 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 neartheend 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 onepastlast 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 1888 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseEdgeWithVertices(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex().

inline 
Erases a vertex and its incident edges.
The vertex specified by the iterator (which must not be a onepastlast 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 neartheend 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 onepastlast 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.

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 1908 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::eraseVertex().

inline 
Erase all edges incident to a vertex.
This method erases (withdraws and deletes) all edges that are incident to the specified vertex. That is, all edges whose source or target is the vertex. It is logically equivalent to calling clearOutEdges followed by clearInEdges, and has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.

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.

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 1946 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearOutEdges().

inline 
Erase all edges emanating from a vertex.
This method erases (withdraws and deletes) all edges whose source is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time.

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 1966 of file Graph.h.
Referenced by Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearEdges(), and Sawyer::Container::Graph< AbstractLocation, DataFlowEdge >::clearInEdges().

inline 
Erase all edges targeting a vertex.
This method erases (withdraws and deletes) all edges whose target is the specified vertex. It has the same effects on iterators and edge ID numbers as erasing edges individually.
Time complexity is linear in the number of edges erased, multiplied by the time complexity for edge index lookups if any. Most edge indexes have logarithmic lookup time..

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 1984 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().