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

#include <Digraph.h>

Inheritance diagram for grafalgo::Digraph:

Collaboration diagram for grafalgo::Digraph:

Public Member Functions
	Digraph (int=1, int=1)
	Construct a Digraph with space for a specified number of vertices and edges.
void	resize (int, int)
	Resize a Digraph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Digraph.
void	expand (int numv)
vertex	tail (edge) const
	Get the tail (starting point) of a directed edge.
vertex	head (edge) const
	Get the head (starting point) of a directed edge.
virtual edge	firstAt (vertex) const
	Get the first edge incident to a vertex.
virtual edge	nextAt (vertex, edge) const
	Get the next edge incident to a specific vertex.
edge	firstIn (vertex) const
	Get the first edge incident to a vertex.
edge	nextIn (vertex, edge) const
	Get the next incoming edge incident to a specific vertex.
edge	firstOut (vertex) const
	Get the first edge leaving a specified vertex.
edge	nextOut (vertex, edge) const
	Get the next outgoing edge incident to a specific vertex.
edge	joinWith (vertex, vertex, edge)
	Join two vertices with a specific edge.
bool	remove (edge)
	Remove an edge from the Diraph.
void	rgraph (int, int)
	Read a graph.
void	rdag (int, int)
	Generate a random directed acyclic graph.
virtual string &	toDotString (string &) const
	Construct a string in dot file format representation of the Directed Graph object.
Protected Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Digraph.
void	freeSpace ()
	Free space used by graph.
string &	adjList2string (vertex, string &) const
	Create a string representation of an adjacency list.
bool	readAdjList (istream &)
	Read one edge from an input stream, add it to the graph.
Private Member Functions
Digraph &	operator= (const Digraph &)
Private Attributes
edge *	fi
	fi[u] is first in edge

Detailed Description

Data structure for undirected graph with edge weights.

Digraph size (number of vertices and max number of edges) must be specified when a Digraph object is constructed. 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 Digraph.h.

Constructor & Destructor Documentation

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

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

Parameters:

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

Definition at line 18 of file Digraph.cpp.

Here is the call graph for this function:

Member Function Documentation

string & grafalgo::Digraph::adjList2string	(	vertex	u,
		string &	s
	)		const `[protected, 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.

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 126 of file Digraph.cpp.

Here is the call graph for this function:

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

Expand the space available for this Digraph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::Graph.

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 63 of file Digraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Digraph::firstAt ( vertex v ) const [inline, virtual]

Get the first edge incident to a vertex.

Parameters:

v	is the the vertex of interest

Returns:: the first edge incident to v

Reimplemented from grafalgo::Graph.

Definition at line 84 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Digraph::firstIn ( vertex v ) const [inline]

Get the first edge incident to a vertex.

Parameters:

v	is the the vertex of interest

Returns:: the first edge incident to v

Definition at line 107 of file Digraph.h.

Here is the call graph for this function:

edge grafalgo::Digraph::firstOut ( vertex v ) const [inline]

Get the first edge leaving a specified vertex.

Parameters:

v	is the the vertex of interest

Returns:: the first outgoing edge incident to v

Definition at line 130 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Digraph::freeSpace ( ) [protected]

Free space used by graph.

Reimplemented from grafalgo::Graph.

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 43 of file Digraph.cpp.

Here is the caller graph for this function:

edge grafalgo::Digraph::head ( edge e ) const [inline]

Get the head (starting point) of a directed edge.

Parameters:

e	is an edge

Returns:: the head of the edge (if e=(u,v), v is the head)

Definition at line 78 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Digraph::joinWith	(	vertex	u,
		vertex	v,
		edge	e
	)		`[virtual]`

Join two vertices with a specific edge.

Parameters:

u	is the tail of the new edge
v	is the head of the new edge
e	is the number of an idle edge

Returns:: the edge number for the new edge, or 0 on failure

Reimplemented from grafalgo::Graph.

Definition at line 75 of file Digraph.cpp.

Here is the call graph for this function:

void grafalgo::Digraph::makeSpace	(	int	numv,
		int	maxe
	)		`[protected]`

Allocate and initialize dynamic storage for Digraph.

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.

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 28 of file Digraph.cpp.

Here is the caller graph for this function:

edge grafalgo::Digraph::nextAt	(	vertex	v,
		edge	e
	)		const `[inline, virtual]`

Get the next edge incident to a specific vertex.

Parameters:

v	is the edge whose adjacency list we're accessing
e	is the edge whose successor is requested

Returns:: the next edge incident to e (either in or out) or 0 if e is not incident to v or is the last edge on the list

Reimplemented from grafalgo::Graph.

Definition at line 95 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Digraph::nextIn	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the next incoming edge incident to a specific vertex.

Parameters:

v	is a vertex whose edges we're iterating through
e	is the edge whose successor is requested

Returns:: the next edge in the adjacency list for v or 0 if e is not incident to v or is the last edge on the list

Definition at line 118 of file Digraph.h.

Here is the call graph for this function:

edge grafalgo::Digraph::nextOut	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the next outgoing edge incident to a specific vertex.

Parameters:

v	is the edge whose adjacency list we're accessing
e	is the edge whose successor is requested

Returns:: the next edge in the adjacency list for v or 0 if e is not incident to v or is the last edge on the list

Definition at line 141 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Digraph::rdag	(	int	numv,
		int	nume
	)

Generate a random directed acyclic graph.

Parameters:

numv	is the number of vertices on which the digraph is generated; if this object has n()>numv, the random graph is defined over the first numv vertices, leaving the remaining vertices with no edges
nume	is the number of edges in the generated digraph

Definition at line 289 of file Digraph.cpp.

Here is the call graph for this function:

bool grafalgo::Digraph::readAdjList ( istream & in ) [protected, virtual]

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

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 194 of file Digraph.cpp.

Here is the call graph for this function:

bool grafalgo::Digraph::remove ( edge e )

Remove an edge from the Diraph.

Parameters:

e	is the edge to be removed.

Returns:: true on success, false on failure

Reimplemented from grafalgo::Graph.

Definition at line 101 of file Digraph.cpp.

Here is the call graph for this function:

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

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

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 50 of file Digraph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Digraph::rgraph	(	int	numv,
		int	nume
	)

Read a graph.

Parameters:

in	is an open input stream

Returns:: true on success, else false Generate a random digraph.

Parameters:

numv	is the number of vertices on which the digraph is generated; if this object has n()>numv, the random graph is defined over the first numv vertices, leaving the remaining vertices with no edges
nume	is the number of edges in the generated digraph

Reimplemented from grafalgo::Graph.

Definition at line 233 of file Digraph.cpp.

Here is the call graph for this function:

edge grafalgo::Digraph::tail ( edge e ) const [inline]

Get the tail (starting point) of a directed edge.

Parameters:

e	is an edge

Returns:: the tail of the edge (if e=(u,v), u is the tail, v the head)

Definition at line 72 of file Digraph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 152 of file Digraph.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/Digraph.h
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Digraph.cpp

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation