Data structure for undirected graph with edge weights. More...

#include <Wgraph.h>

Inheritance diagram for grafalgo::Wgraph:

Collaboration diagram for grafalgo::Wgraph:

Public Member Functions
	Wgraph (int=1, int=1)
	Construct a Wgraph with space for a specified number of vertices and edges.
	~Wgraph ()
	Free space used by Wgraph.
void	resize (int, int)
	Resize a Wgraph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Wgraph.
void	expand (int numv)
void	copyFrom (const Wgraph &)
	Copy into list from source.
int	weight (edge) const
	Get the weight of an edge.
void	setWeight (edge, int)
	Set the weight of an edge.
string &	edge2string (edge, vertex, string &) const
	Create a string representation of an edge.
string &	toDotString (string &) const
	Construct a string in dot file format representation of the Weighted Graph object.
void	randWeight (int, int)
	Assign edges a random weight in given range.
Private Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Wgraph.
void	freeSpace ()
	Free space used by graph.
bool	readAdjList (istream &)
	Read adjacency list from an input stream, add it to the graph.
string &	adjList2string (vertex, string &) const
	Create a string representation of an adjacency list.
Private Attributes
int *	wt
	weight of the edge

Detailed Description

Data structure for undirected graph with edge weights.

Wgraph size (number of vertices and max number of edges) must be specified when a Wgraph object is instantiated. Edges can be added and removed from the graph. Methods are provided to facilitate graph traversal, either by iterating through all edges of the graph or all edges incident to a specific vertex.

Definition at line 28 of file Wgraph.h.

Constructor & Destructor Documentation

grafalgo::Wgraph::Wgraph	(	int	numv = `1`,
		int	maxe = `1`
	)

Construct a Wgraph with space for a specified number of vertices and edges.

Parameters:

numv	is number of vertices in the graph
maxEdge1	is the maximum number of edges

Definition at line 18 of file Wgraph.cpp.

Here is the call graph for this function:

Member Function Documentation

string & grafalgo::Wgraph::adjList2string	(	vertex	u,
		string &	s
	)		const `[private, virtual]`

Create a string representation of an adjacency list.

Parameters:

u	is a vertex number
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Reimplemented from grafalgo::Graph.

Definition at line 125 of file Wgraph.cpp.

Here is the call graph for this function:

void grafalgo::Wgraph::copyFrom ( const Wgraph & source )

Copy into list from source.

Definition at line 69 of file Wgraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Wgraph::edge2string	(	edge	e,
		vertex	u,
		string &	s
	)		const `[virtual]`

Create a string representation of an edge.

Parameters:

e	is an edge number
u	is one of the endponts of e; it will appear first in the string
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Reimplemented from grafalgo::Graph.

Definition at line 111 of file Wgraph.cpp.

Here is the call graph for this function:

void grafalgo::Wgraph::expand	(	int	numv,
		int	maxe
	)		`[virtual]`

Expand the space available for this Wgraph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::Graph.

Definition at line 62 of file Wgraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Wgraph::freeSpace ( ) [private]

Free space used by graph.

Reimplemented from grafalgo::Graph.

Definition at line 42 of file Wgraph.cpp.

Here is the caller graph for this function:

void grafalgo::Wgraph::makeSpace	(	int	numv,
		int	maxe
	)		`[private]`

Allocate and initialize dynamic storage for Wgraph.

Parameters:

numv	is the number of vertices to allocate space for
maxe	is the number of edges to allocate space for

Reimplemented from grafalgo::Graph.

Definition at line 29 of file Wgraph.cpp.

Here is the caller graph for this function:

void grafalgo::Wgraph::randWeight	(	int	lo,
		int	hi
	)

Assign edges a random weight in given range.

Parameters:

lo	is the low end of the range
hi	is the high end of the range

Definition at line 146 of file Wgraph.cpp.

Here is the call graph for this function:

bool grafalgo::Wgraph::readAdjList ( istream & in ) [private, virtual]

Read adjacency list from an input stream, add it to the graph.

Parameters:

in	is an open input stream

Returns:: true on success, false on error.

Reimplemented from grafalgo::Graph.

Definition at line 85 of file Wgraph.cpp.

Here is the call graph for this function:

void grafalgo::Wgraph::resize	(	int	numv,
		int	maxe
	)		`[virtual]`

Resize a Wgraph object.

The old value is discarded.

Parameters:

numv	is the number of vertices to allocate space for
maxe	is the number of edges to allocate space for

Reimplemented from grafalgo::Graph.

Definition at line 49 of file Wgraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Wgraph::setWeight	(	edge	e,
		int	w
	)		`[inline]`

Set the weight of an edge.

Parameters:

e	is the edge of interest
w	is the desired weight

Definition at line 69 of file Wgraph.h.

Here is the caller graph for this function:

string & grafalgo::Wgraph::toDotString ( string & s ) const [virtual]

Construct a string in dot file format representation of the Weighted Graph object.

For small graphs (at most 26 vertices), vertices are represented in the string as lower case letters. For larger graphs, vertices are represented by integers.

Parameters:

s	is a string object provided by the caller which is modified to provide a representation of the Graph.

Returns:: a reference to the string

Reimplemented from grafalgo::Graph.

Definition at line 160 of file Wgraph.cpp.

Here is the call graph for this function:

int grafalgo::Wgraph::weight ( edge e ) const [inline]

Get the weight of an edge.

Parameters:

e	is the edge of interest

Returns:: the weight of e, or 0 if e is not a valid edge.

Definition at line 60 of file Wgraph.h.

Here is the caller graph for this function:

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

/Users/jst/src/grafalgo/cpp/include/Wgraph.h
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Wgraph.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation