class BasicGraph : Graph<Vertex, Edge>
This class represents a simplified and expanded implementation of a directed, weighted graph.
Unlike with the Graph
class, you do not need to supply the vertex and edge types via templates in < >
.
The vertex / node type has been set to Vertex
and the edge / arc type has been set to Edge
.
The BasicGraph
also chooses to use the terminology of 'vertex' and 'edge' rather than 'node' and 'arc' in member names, though the other terminology is still supported for backward compatibility.
Since BasicGraph
is a subclass of Graph
, it also contains all of the members of the Graph
class, which clients can call in their code.
See the Graph class documentation for more details.
If you want to use this class to represent an undirected graph, doubly add each edge.
For example, every time you call addEdge(a, b);
, also call addEdge(b, a);
.
If you want to use this class to represent a weighted graph, set each edge's cost
field and use it in your own graph algorithms.
The internal representation of this graph is an adjacency list, which is very efficient for iterating over neighbors of a given vertex, but less efficient for asking whether two given vertexes are neighbors.
Until the 2014/10/20 version of the library, unlike with several of the other collections, you could not directly perform a foreach loop over a BasicGraph
.
You can, however, foreach over the vertexes by calling getVertexSet
on the BasicGraph
, or over the edges by calling getEdgeSet
on the BasicGraph
.
Since 2014/10/20 version of the library, performing a foreach loop over a BasicGraph
is supported and is equivalent to looping over the vertex set.
Note about pointers:
Several BasicGraph
members return various pointers to vertexes and edges.
Any such pointers returned are direct pointers to the internal structures inside of this graph.
If the graph itself falls out of scope, is cleared, etc., or if the given vertex/edge is removed from the graph, this pointer will become invalid.
Undefined behavior and crashes will result if you retain pointers to vertexes/edges that live on beyond the life span of the graph.
Clients also should not free or delete
any pointers to vertex or edge structures that were obtained by calling methods on a basic graph.
For the purposes of BigOh listing, some members are proportional to the number of vertexes V, and some are proportional to the number of edges E.
Constructor  
O(1)  Creates an empty BasicGraph object. 

Methods  
addEdge(edge) 
O(log V + log E)  Adds a directed edge to the graph from v1 to v2. 
O(log V)  Adds a vertex to the graph.  
O(V + E)  Removes all vertexes and edges from the graph.  
clearEdges(v) 
O(E)  Removes all edges from the graph, or all edges outbound from a given vertex. 
O(log E)  Returns whether the graph has an edge from v1 to v2.  
O(log V)  Returns whether the graph contains the given vertex, and/or contains a vertex with the given name.  
O(1)  Returns the number of edges in the graph.  
O(log V + log E)  Returns the edge from v1 to v2, if present.  
O(1)  Returns the set of all edges in the graph.  
O(log V)  Returns the set of all edges that start at the specified vertex.  
O(E)  Returns the edge that is the opposite of the given edge; that is, if the specified edge e starts at v1 and ends at v2, will return the edge that starts at v2 and ends at v1, if such an edge exists in the graph.  
O(log V)  Returns the set of all edges that end at the specified vertex.  
O(E)  Returns a set of the names of vertexes for which v is a neighbor; that is, the ones for which there is an edge from that vertex to v.  
O(E)  Returns the set of vertexes for which v is a neighbor; that is, the ones for which there is an edge from that vertex to v.  
O(log V)  Returns a set of the names of all vertexes that are neighbors of the specified vertex.  
O(log V)  Returns the set of vertexes N for which there is an edge from v to N.  
O(log V)  Returns a pointer to the graph's internal Vertex structure with information about a given vertex. 

O(V)  Returns a set of the names of all vertexes in the graph.  
O(1)  Returns the set of the graph's internal Vertex structures for all vertexes in the graph. 

O(1)  Returns true if the graph contains no vertexes or edges. 

O(log V)  Returns true if the graph contains an edge from v1 to v2. 

removeEdge(edge) 
O(E + log V)  Removes an edge from v1 to v2 from the graph. 
O(E + log V)  Removes a vertex from the graph.  
O(V + E)  Clears any temporary internal data stored at each vertex and edge.  
O(1)  Returns the number of vertexes in the graph.  
O(V + E)  Converts the graph to a printable string representation.  
O(1)  Returns the number of vertexes in the graph.  
Operators  
O(V + E)  Outputs the contents of the graph to the given output stream.  
O(V log V + E log E)  Reads the contents of the given input stream into the graph. 
BasicGraph();
BasicGraph
object.
Usage:
BasicGraph g;
Edge* addEdge(string name1, string name2); Edge* addEdge(Vertex* v1, Vertex* v2); Edge* addEdge(Edge* edge);
addEdge
method.
All three of these versions return a pointer to the edge in case the client needs to capture this value.
Note that it is allowed to have multiple edges between the same pair of vertexes.
If either of the vertexes supplied is nullptr
, the function will throw an error.
Otherwise, if either vertex is not found in the graph, said vertex will be added to the graph.
Usage:
g.addEdge(v1, v2); g.addEdge(edge);
Vertex* addVertex(string name); Vertex* addVertex(Vertex* vertex);
One version of this method accepts a string for the vertex's name, creates a new vertex of the appropriate type and initializes its fields.
The other accepts a structure representing the vertex and its data.
Both versions of this method return a pointer to the vertex, though clients need not store that pointer; you can get the pointer again later by calling getVertex
and passing the same name.
The vertexes in a graph must have unique names. If this graph already contains a vertex with the given name, the vertex will not be added and the graph's state will not change.
If nullptr
is passed to the pointer version of this function, an error will be thrown.
If you use the Vertex*
version of this function, you are relinquishing ownership of the Vertex
structure's lifecycle to the graph; our graph will free it when done with it.
Usage:
g.addVertex(vertex);
void clear();
Vertex
and Edge
objects that were internally allocated as heap storage.
(The heap memory associated with all vertexes and edges that have been previously added to the graph will be freed.)
Usage:
g.clear();
void clearEdges(); void clearEdges(string vertexName); void clearEdges(Vertex* v);
Edge
objects that were internally allocated as heap storage.
The second and third versions remove all edges that start from the given vertex.
(The vertexes in the graph will remain. If you want to clear the vertexes as well, use the clear
method.)
Usage:
g.clearEdges(); g.clearEdges(v);
bool containsEdge(string name1, string name2) const; bool containsEdge(Vertex* v1, Vertex* v2) const;
If either of the vertexes supplied is nullptr
or is not found in the graph, this function returns false
.
Usage:
if (g.containsEdge(v1, v2)) ... if (g.containsEdge(edge)) ...
bool containsVertex(string name) const; bool containsVertex(Vertex* vertex) const;
If nullptr
is passed to the pointer version of this function, returns false
.
Usage:
if (g.containsVertex(vertex)) ...
int edgeCount() const;
Usage:
int count = g.edgeCount();
Edge* getEdge(string v1, string v2) const; Edge* getEdge(Vertex* v1, Vertex* v2) const;
If either of the vertexes supplied is nullptr
or is not found in the graph, the function will return nullptr
.
If there are multiple edges between the given pair of vertexes, which of the edges will be returned is unspecified.
Usage:
Edge* e = g.getEdge(v1, v2);
const Set<Edge*>& getEdgeSet() const; const Set<Edge*>& getEdgeSet(string vertexName) const; const Set<Edge*>& getEdgeSet(Vertex* vertex) const;
When calling the two versions of this function that accept a vertex parameter, if the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (Edge* edge : g.getEdgeSet()) ... for (Edge* edge : g.getEdgeSet(vertex)) ...
Edge* getInverseEdge(Edge* e) const;
If the edge supplied is nullptr
, is not found in the graph, or has no inverse, the function will return nullptr
.
If there are multiple edges between the given pair of vertexes, which of the edges will be returned is unspecified.
Usage:
Edge* e2 = g.getInverseEdge(e1);
const Set<Edge*>& getInverseEdgeSet(string vertexName) const; const Set<Edge*>& getInverseEdgeSet(Vertex* vertex) const;
If the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (Edge* edge : g.getInverseEdgeSet(vertex)) ...
const Set<string> getInverseNeighborNames(string vertex) const; const Set<string> getInverseNeighborNames(Vertex* vertex) const;
getNeighborNames
, which returns the names of all vertexes N for which there is an edge from the specified vertex to N.
If the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (string neighbor : g.getInverseNeighborNames(vertex)) ...
const Set<Vertex*> getInverseNeighbors(string vertex) const; const Set<Vertex*> getInverseNeighbors(Vertex* vertex) const;
getNeighbors
, which returns all vertexes N for which there is an edge from the specified vertex to N.
If the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (Vertex* vertex : g.getInverseNeighbors(vertex)) ...
const Set<string> getNeighborNames(string vertex) const; const Set<string> getNeighborNames(Vertex* vertex) const;
If the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (string neighbor : g.getNeighborNames(vertex)) ...
const Set<Vertex*> getNeighbors(string vertex) const; const Set<Vertex*> getNeighbors(Vertex* vertex) const;
If the vertex supplied is nullptr
or is not found in the graph, the function will return an empty set.
Usage:
for (Vertex* vertex : g.getNeighbors(vertex)) ...
Vertex* getVertex(string name) const;
nullptr
.
Usage:
Vertex* vertex = g.getVertex(name);
const Set<string>& getVertexNames() const;
Usage:
for (string vertex : g.getVertexNames()) ...
const Set<Vertex*>& getVertexSet() const;
Usage:
for (Vertex* vertex : g.getVertexSet()) ...
bool isEmpty() const;
true
if the graph contains no vertexes.
Usage:
if (g.isEmpty()) ...
bool isNeighbor(string name1, string name2) const; bool isNeighbor(Vertex* v1, Vertex* v2) const;
true
if the graph contains an edge from v1
to v2
.
If either of the vertexes supplied is nullptr
or is not found in the graph, the function will return false
.
Usage:
if (g.isNeighbor(v1, v2)) ...
void removeEdge(string name1, string name2); void removeEdge(Vertex* v1, Vertex* v2); void removeEdge(Edge* edge);
When calling the singleparameter version of removeEdge
, only that single edge is removed.
When calling either of the twoparameter versions of removeEdge
, if more than one edge connects the specified endpoints, all of them are removed.
If any of the vertexes or edges supplied is nullptr
or is not found in the graph, calling this function will have no effect on the graph.
Usage:
g.removeEdge(v1, v2); g.removeEdge(edge);
void removeVertex(string name); void removeVertex(Vertex* vertex);
If nullptr
is passed to the pointer version of this function, or if this graph does not contain the given vertex or a vertex with the given name, the function has no effect on the graph.
Usage:
g.removeVertex(vertex);
void resetData();
resetData
on every vertex and edge.
Usage:
g.resetData();
int size() const;
vertexCount
.
Usage:
int size = g.size();
string toString() const;
"{A, B, C, D, E, A > B, C > A, D > E}"
.
Edges will be shown in the form A  B
if there is an edge in both directions between the given vertexes, and A > B
if there is an edge in only one directien between them.
You can also use the operator <<
to print a graph to an output stream.
Usage:
string str = g.toString(); cout << g << endl;
int vertexCount() const;
size
.
Usage:
int count = g.vertexCount();