#include "basicgraph.h"

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.

See also: Vertex, Edge

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 for-each loop over a BasicGraph. You can, however, for-each 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 for-each 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 Big-Oh listing, some members are proportional to the number of vertexes V, and some are proportional to the number of edges E.

Constructor
BasicGraph()  O(1) Creates an empty BasicGraph object.
Methods
addEdge(v1, v2)
addEdge(edge) 		 O(log V + log E) Adds a directed edge to the graph from v1 to v2.
addVertex(v) O(log V) Adds a vertex to the graph.
clear()  O(V + E) Removes all vertexes and edges from the graph.
clearEdges()
clearEdges(v)
 O(E) Removes all edges from the graph, or all edges outbound from a given vertex.
containsEdge(v1, v2) O(log E) Returns whether the graph has an edge from v1 to v2.
containsVertex(v) O(log V) Returns whether the graph contains the given vertex, and/or contains a vertex with the given name.
edgeCount() O(1) Returns the number of edges in the graph.
getEdge(v1, v2) O(log V + log E) Returns the edge from v1 to v2, if present.
getEdgeSet() O(1) Returns the set of all edges in the graph.
getEdgeSet(v) O(log V) Returns the set of all edges that start at the specified vertex.
getInverseEdge(e) 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.
getInverseEdgeSet(v) O(log V) Returns the set of all edges that end at the specified vertex.
getInverseNeighborNames(v) 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.
getInverseNeighbors(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.
getNeighborNames(v) O(log V) Returns a set of the names of all vertexes that are neighbors of the specified vertex.
getNeighbors(v) O(log V) Returns the set of vertexes N for which there is an edge from v to N.
getVertex(name)  O(log V) Returns a pointer to the graph's internal Vertex structure with information about a given vertex.
getVertexNames()  O(V) Returns a set of the names of all vertexes in the graph.
getVertexSet()  O(1) Returns the set of the graph's internal Vertex structures for all vertexes in the graph.
isEmpty()  O(1) Returns true if the graph contains no vertexes or edges.
isNeighbor(v1, v2) O(log V) Returns true if the graph contains an edge from v1 to v2.
removeEdge(v1, v2)
removeEdge(edge) 		 O(E + log V) Removes an edge from v1 to v2 from the graph.
removeVertex(v) O(E + log V) Removes a vertex from the graph.
resetData()  O(V + E) Clears any temporary internal data stored at each vertex and edge.
size()  O(1) Returns the number of vertexes in the graph.
toString()  O(V + E) Converts the graph to a printable string representation.
vertexCount() O(1) Returns the number of vertexes in the graph.
Operators
ostream << graph O(V + E) Outputs the contents of the graph to the given output stream.
istream >> graph O(V log V + E log E) Reads the contents of the given input stream into the graph.

Constructor detail

BasicGraph();
Creates an empty BasicGraph object.

Usage:

BasicGraph g;

Method detail

Edge* addEdge(string name1, string name2);
Edge* addEdge(Vertex* v1, Vertex* v2);
Edge* addEdge(Edge* edge);
Adds a directed edge to the graph from vertex 1 to vertex 2. The endpoints of the edge can be specified either as strings indicating the names of the vertexes, or as pointers to the vertex structures. Alternatively, the client can create the edge structure explicitly and pass that pointer to the 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);
Adds a vertex to the graph, if no vertex with that name already exists in the graph.

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();
Reinitializes the graph to be empty of all vertexes and edges, freeing any 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);
The first version removes all edges from the graph, freeing any 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;
Returns whether the graph contains an edge from v1 to v2.

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;
Returns whether the graph contains the given vertex. One version of this method looks up the vertex by name, and the other uses the information supplied in the provided pointer.

If nullptr is passed to the pointer version of this function, returns false.

Usage:

if (g.containsVertex(vertex)) ...

int edgeCount() const;
Returns the number of edges in the graph.

Usage:

int count = g.edgeCount();

Edge* getEdge(string v1, string v2) const;
Edge* getEdge(Vertex* v1, Vertex* v2) const;
Returns the edge from v1 to v2 in the graph.

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;
Returns the set of all edges in the graph or, in the second and third forms, the edges that start at the specified vertex, which can be indicated either as a pointer or by name.

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

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;
Returns the set of all edges in the graph that end at the specified vertex, which can be indicated either as a pointer or by name.

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;
Returns a set of the names of vertexes for which the given vertex is a neighbor; that is, the names of all vertexes N for which there is an edge from N to the specified vertex. This is essentially the opposite of 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;
Returns the set of vertexes for which the given vertex is a neighbor; that is, the set of all vertexes N for which there is an edge from N to the specified vertex. This is essentially the opposite of 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;
Returns a set of the names of vertexes that are neighbors of the specified vertex, which can be indicated either as a pointer or by name. The graph is directed, so this is the set of names of all vertexes N to 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.getNeighborNames(vertex)) ...

const Set<Vertex*> getNeighbors(string vertex) const;
const Set<Vertex*> getNeighbors(Vertex* vertex) const;
Returns the set of vertexes that are neighbors of the specified vertex, which can be indicated either as a pointer or by name. The graph is directed, so this is the set of all vertexes N to 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.getNeighbors(vertex)) ...

Vertex* getVertex(string name) const;
Looks up a vertex in the graph by name and returns a pointer to its internal data structure. If no vertex with the specified name exists, returns nullptr.

Usage:

Vertex* vertex = g.getVertex(name);

const Set<string>& getVertexNames() const;
Returns a set of the names of all vertexes in the graph. The vertexes will be sorted in case-sensitive alphabetical order.

Usage:

for (string vertex : g.getVertexNames()) ...

const Set<Vertex*>& getVertexSet() const;
Returns the set of all vertexes in the graph. The vertexes will be sorted by name.

Usage:

for (Vertex* vertex : g.getVertexSet()) ...

bool isEmpty() const;
Returns 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;
Returns 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);
Removes an edge from the graph, where the edge can be specified in any of three ways: by the names of its endpoints, by the vertex pointers at its endpoints, or as an edge pointer.

When calling the single-parameter version of removeEdge, only that single edge is removed. When calling either of the two-parameter 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);
Removes a vertex from the graph, where the vertex can be specified either by its name or as a pointer value. Removing a vertex also removes all edges that touch that 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();
Sets the data stored in each vertex and edge back to its original value by calling resetData on every vertex and edge.

Usage:

g.resetData();

int size() const;
Returns the number of vertexes in the graph. Equivalent to vertexCount.

Usage:

int size = g.size();

string toString() const;
Converts the graph to a printable string representation, listing all vertex names followed by the start/finish of all edges, such as "{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;
Returns the number of vertexes in the graph. Equivalent to size.

Usage:

int count = g.vertexCount();