Data structure for directed graph with edge lengths. More...

#include <Wdigraph.h>

Inheritance diagram for grafalgo::Wdigraph:

Collaboration diagram for grafalgo::Wdigraph:

Public Member Functions
	Wdigraph (int=1, int=1)
	Construct a Wdigraph with space for a specified number of vertices and edges.
void	resize (int, int)
	Resize a Wdigraph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Wdigraph.
void	expand (int numv)
virtual void	copyFrom (const Wdigraph &)
	Copy into list from source.
int	length (edge) const
	Get the length of an edge.
void	setLength (edge, int)
	Set the length of an edge.
string &	edge2string (edge, string &) const
	Create a string representation of an edge.
string &	toDotString (string &) const
	Construct a string in dot file format representation of the Weighted Directed Graph object.
void	randLength (int, int)
	Read one edge from an input stream, add it to the graph.
Private Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Wdigraph.
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.
Wdigraph &	operator= (const Wdigraph &)
Private Attributes
int *	len
	len[e] is length of edge e

Detailed Description

Data structure for directed graph with edge lengths.

Wdigraph size (number of vertices and max number of edges) must be specified when a Wdigraph 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 25 of file Wdigraph.h.

Constructor & Destructor Documentation

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

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

Parameters:

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

Definition at line 17 of file Wdigraph.cpp.

Here is the call graph for this function:

Member Function Documentation

string & grafalgo::Wdigraph::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::Digraph.

Definition at line 108 of file Wdigraph.cpp.

Here is the call graph for this function:

void grafalgo::Wdigraph::copyFrom ( const Wdigraph & source ) [virtual]

Copy into list from source.

Definition at line 67 of file Wdigraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Create a string representation of an edge.

In the returned string, the "left" endpoint of the edge appears first.

Parameters:

e	is an edge 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 132 of file Wdigraph.cpp.

Here is the call graph for this function:

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

Expand the space available for this Wdigraph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::Digraph.

Definition at line 60 of file Wdigraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free space used by graph.

Reimplemented from grafalgo::Digraph.

Definition at line 40 of file Wdigraph.cpp.

Here is the caller graph for this function:

int grafalgo::Wdigraph::length ( edge e ) const [inline]

Get the length of an edge.

Parameters:

e	is the edge of interest

Returns:: the length of e

Definition at line 60 of file Wdigraph.h.

Here is the caller graph for this function:

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

Allocate and initialize dynamic storage for Wdigraph.

Parameters:

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

Reimplemented from grafalgo::Digraph.

Definition at line 27 of file Wdigraph.cpp.

Here is the caller graph for this function:

void grafalgo::Wdigraph::randLength	(	int	lo,
		int	hi
	)

Read one edge from an input stream, add it to the graph.

Parameters:

in	is an open input stream

Returns:: true on success, false on error. Assign edges a random lengths in given range.

Parameters:

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

Definition at line 190 of file Wdigraph.cpp.

Here is the call graph for this function:

bool grafalgo::Wdigraph::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::Digraph.

Definition at line 83 of file Wdigraph.cpp.

Here is the call graph for this function:

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

Resize a Wdigraph 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::Digraph.

Definition at line 47 of file Wdigraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Wdigraph::setLength	(	edge	e,
		int	lng
	)		`[inline]`

Set the length of an edge.

Parameters:

e	is the edge of interest
lng	is the desired length

Definition at line 68 of file Wdigraph.h.

Here is the caller graph for this function:

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

Construct a string in dot file format representation of the Weighted Directed 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::Digraph.

Definition at line 150 of file Wdigraph.cpp.

Here is the call graph for this function:

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

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation