Represents a graph of vertices and edges and allows basic operations to be performed on it. More...

#include "graph.h"

Collaboration diagram for Graph:

Public Member Functions
	Graph (bool isWeighted)
	Constructor to create an empty graph. More...

	Graph (bool isWeighted, int numVertices, unsigned long seed)
	Constructor to create a random, connected graph. More...

vector< Vertex >	getAdjacent (Vertex v) const
	Gets all adjacent vertices to the parameter vertex. More...

Vertex	getStartingVertex () const
	Returns one vertex in the graph. More...

vector< Vertex >	getVertices () const
	Gets all vertices in the graph. More...

Vertex	getVertexByLabel (string label) const
	Gets a vertex based on the label of a vertex. More...

Edge	getEdge (Vertex u, Vertex v) const
	Gets an edge between two vertices. More...

vector< Edge >	getEdges () const
	Gets all the edges in the graph. More...

void	setVertexName (Vertex v, string name)
	Creates a name for a vertex. More...

string	getVertexName (Vertex v) const
	Gets the name of a vertex. More...

void	setVertexLabel (Vertex v, string label)
	Labels a vertex with a string. More...

string	getVertexLabel (Vertex v) const
	Gets the label of a vertex. More...

void	setEdgeLabel (Vertex u, Vertex v, string label)
	Sets the edge label of an edge between vertices u and v. More...

string	getEdgeLabel (Vertex u, Vertex v) const
	Gets the edge label of an edge between vertices u and v. More...

int	getEdgeWeight (Vertex u, Vertex v) const
	Gets the weight of an edge between two vertices. More...

Vertex	insertVertex (string label="")
	Inserts a new vertex into the graph and labels it. More...

void	removeVertex (Vertex v)
	Removes a given vertex from the graph. More...

bool	insertEdge (Vertex u, Vertex v)
	Inserts an edge between two vertices. More...

void	removeEdge (Vertex u, Vertex v)
	Removes an edge between two vertices. More...

void	setEdgeWeight (Vertex u, Vertex v, int weight)
	Sets the weight of an edge between two vertices. More...

void	initSnapshot (string title)
	Creates a name for snapshots of the graph. More...

void	snapshot ()
	Saves a snapshot of the graph to file. More...

void	print () const
	Prints the graph to stdout. More...

void	savePNG (string title) const
	Saves the graph as a PNG image. More...

Private Member Functions
Vertex	nextVertex ()
	Creates a new vertex an inserts it into the graph. More...

void	assertExists (Vertex v, string functionName) const
	Returns whether a given vertex exists in the graph. More...

void	assertConnected (Vertex u, Vertex v, string functionName) const
	Returns whether two vertices are connected in the graph. More...

void	error (string message) const
	Prints a graph error and quits the program. More...

Private Attributes
VertexMap	graph
	a mapping of vertices to edge lists More...

VertexLabelMap	vertexLabels
	a mapping of vertices to their labels More...

VertexNameMap	vertexNames
	a mapping of vertices to their names More...

Random	random
	a random number generator More...

Detailed Description

Represents a graph of vertices and edges and allows basic operations to be performed on it.

Constructor & Destructor Documentation

Graph::Graph ( bool isWeighted )

Constructor to create an empty graph.

Parameters

isWeighted - specifies whether the graph is a weighted graph or not

Graph::Graph	(	bool	isWeighted,
		int	numVertices,
		unsigned long	seed
	)

Constructor to create a random, connected graph.

Parameters

isWeighted	- specifies whether the graph is a weighted graph or not
numVertices	- the number of vertices the graph will have
seed	- a random seed to create the graph with

Member Function Documentation

vector< Vertex > Graph::getAdjacent ( Vertex v ) const

Gets all adjacent vertices to the parameter vertex.

Parameters

v	- the vertex to get neighbors from

Returns: a vector of vertices

Vertex Graph::getStartingVertex ( ) const

Returns one vertex in the graph.

This function can be used to find a random vertex with which to start a traversal.

Returns: a vertex from the graph

vector< Vertex > Graph::getVertices ( ) const

Gets all vertices in the graph.

Returns: a vector of all vertex labels in the graph

Vertex Graph::getVertexByLabel ( string label ) const

Gets a vertex based on the label of a vertex.

Returns: The first vertex with the given label, or -1 if no vertex is found.

Edge Graph::getEdge	(	Vertex	u,
		Vertex	v
	)		const

Gets an edge between two vertices.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

Returns: the edge between u and v

vector< Edge > Graph::getEdges ( ) const

Gets all the edges in the graph.

Returns: a vector of all the edges in the graph

void Graph::setVertexName	(	Vertex	v,
		string	name
	)

Creates a name for a vertex.

This is NOT for marking as unvisited, cross, etc. Use setVertexLabel instead for that. This is only really used for the premade graphs where particular nodes have fun names, such as cities.

Parameters

v	- the vertex to label
label	- label of the vertex to change

string Graph::getVertexName ( Vertex v ) const

Gets the name of a vertex.

This is only really used for the premade graphs where particular nodes have fun names, such as cities.

Parameters

v	- vertex to get the name from

Returns: the vertex name

void Graph::setVertexLabel	(	Vertex	v,
		string	label
	)

Labels a vertex with a string.

This is a method.

Parameters

v	- the vertex to label
label	- label of the vertex to change

string Graph::getVertexLabel ( Vertex v ) const

Gets the label of a vertex.

Parameters

v	- vertex to get label from

Returns: the vertex label

void Graph::setEdgeLabel	(	Vertex	u,
		Vertex	v,
		string	label
	)

Sets the edge label of an edge between vertices u and v.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

string Graph::getEdgeLabel	(	Vertex	u,
		Vertex	v
	)		const

Gets the edge label of an edge between vertices u and v.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

Returns: the edge label between u and v

int Graph::getEdgeWeight	(	Vertex	u,
		Vertex	v
	)		const

Gets the weight of an edge between two vertices.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

Returns: the weight of the edge

Vertex Graph::insertVertex ( string label = "" )

Inserts a new vertex into the graph and labels it.

Parameters

label the label for the vertex

Returns: a copy of the vertex that was inserted

void Graph::removeVertex ( Vertex v )

Removes a given vertex from the graph.

Parameters

v	- the vertex to remove

bool Graph::insertEdge	(	Vertex	u,
		Vertex	v
	)

Inserts an edge between two vertices.

A boolean is returned for use with the random graph generation. Hence, an error is not thrown when it fails to insert an edge.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

Returns: whether inserting the edge was successful

void Graph::removeEdge	(	Vertex	u,
		Vertex	v
	)

Removes an edge between two vertices.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to

void Graph::setEdgeWeight	(	Vertex	u,
		Vertex	v,
		int	weight
	)

Sets the weight of an edge between two vertices.

Parameters

u	- one vertex the edge is connected to
v	- the other vertex the edge is connected to
weight	- the weight to set the edge

void Graph::initSnapshot ( string title )

Creates a name for snapshots of the graph.

Parameters

title - the name to save the snapshots as

void Graph::snapshot ( )

Saves a snapshot of the graph to file.

initSnapshot() must be run first.

void Graph::print ( ) const

Prints the graph to stdout.

void Graph::savePNG ( string title ) const

Saves the graph as a PNG image.

Parameters

title - the filename of the PNG image

Vertex Graph::nextVertex ( )

private

Creates a new vertex an inserts it into the graph.

Returns: a copy of the inserted vertex

void Graph::assertExists	(	Vertex	v,
		string	functionName
	)		const

private

Returns whether a given vertex exists in the graph.

Parameters

v	- the vertex to check
functionName	- the name of the calling function to return in the event of an error

void Graph::assertConnected	(	Vertex	u,
		Vertex	v,
		string	functionName
	)		const

private

Returns whether two vertices are connected in the graph.

Parameters

u	- one vertex
v	- another vertex
functionName	- the name of the calling function to return in the event of an error

void Graph::error ( string message ) const

private

Prints a graph error and quits the program.

The program is exited with a segfault to provide a stack trace.

Parameters

message - the error message that is printed

Member Data Documentation

VertexMap Graph::graph

private

a mapping of vertices to edge lists

VertexLabelMap Graph::vertexLabels

private

a mapping of vertices to their labels

VertexNameMap Graph::vertexNames

private

a mapping of vertices to their names

Random Graph::random

private

a random number generator

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation