Data Abstraction and Problem Solving with C++

Walls and Mirrors

by Frank M. Carrano

Graph Class Reference

#include <Graph.h>

List of all members.

Detailed Description

An adjacency list representation of an undirected, weighted graph.

Definition at line 26 of file Graph.h.

Public Member Functions

Graph (int n)

int getNumVertices () const

int getNumEdges () const

int getWeight (Edge e) const

void add (Edge e)

void remove (Edge e)

map< int, int >::iterator findEdge (int v, int w)

Public Attributes

int numVertices

int numEdges

vector< map< int, int > > adjList

Constructor & Destructor Documentation

Graph::Graph ( int n )

Constructor.
Precondition:
The graph is empty.

Postcondition:
The graph is initialized to hold n vertices.

Definition at line 21 of file Graph.cpp.
References adjList, numEdges, and numVertices.

Member Function Documentation

int Graph::getNumVertices ( ) const

Determines the number of vertices in the graph.
Precondition:
None.

Postcondition:
None.

Returns:
The number of vertices in the graph.

Definition at line 29 of file Graph.cpp.
References numVertices.
Referenced by BFS::startSearch().

int Graph::getNumEdges ( ) const

Determines the number of edges in the graph.
Precondition:
None.

Postcondition:
None.

Returns:
The number of edges in the graph.

Definition at line 34 of file Graph.cpp.
References numEdges.

int Graph::getWeight ( Edge e ) const

Determines the weight of an edge.
Precondition:
The edge exists in the graph.

Postcondition:
None.

Returns:
The weight of the edge parameter.

Definition at line 39 of file Graph.cpp.
References Edge::weight.

void Graph::add ( Edge e )

Creates an edge in the graph.
Precondition:
The vertices exist in the graph.

Postcondition:
Adds to both v and w's list.

Definition at line 44 of file Graph.cpp.
References adjList, numEdges, Edge::v, Edge::w, and Edge::weight.

void Graph::remove ( Edge e )

Removes an edge from the graph.
Precondition:
The vertices exist in the graph.

Postcondition:
Removes edges from both v and w's list.

Definition at line 55 of file Graph.cpp.
References adjList, numEdges, Edge::v, Edge::w, and Edge::weight.

map< int, int >::iterator Graph::findEdge ( int v,

int w

)

Finds the edge connecting v and w.
Precondition:
The edge exists.

Postcondition:
None.

Returns:
An iterator to map key w in vector[v].

Definition at line 66 of file Graph.cpp.
References adjList.

Member Data Documentation

int Graph::numVertices

Definition at line 29 of file Graph.h.
Referenced by getNumVertices(), and Graph().

int Graph::numEdges

Number of vertices in the graph.
Definition at line 30 of file Graph.h.
Referenced by add(), getNumEdges(), Graph(), and remove().

vector<map<int, int> > Graph::adjList

Adjacency list representation of the graph; the map pair consists of the second vertex (key) and the edge weight (value).
Definition at line 35 of file Graph.h.
Referenced by add(), findEdge(), Graph(), remove(), and BFS::search().

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

Generated on Sun Aug 27 22:27:08 2006 for

1.4.6