Class representing a weighted flow graph. More...

#include <Wflograph.h>

Inheritance diagram for grafalgo::Wflograph:

Collaboration diagram for grafalgo::Wflograph:

Public Member Functions
	Wflograph (int=3, int=2, int=1, int=2)
	Construct a Wflograph.
	Wflograph (const Wflograph &)
void	resize (int, int)
	Resize a Wflograph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Wflograph.
void	expand (int numv)
void	copyFrom (const Wflograph &)
	Copy into list from source.
virtual edge	join (vertex, vertex)
	Join two vertices with an edge.
floCost	cost (vertex, edge) const
	Return cost of an edge.
void	setCost (edge, floCost)
	Set the cost of an edge.
void	randCost (floCost, floCost)
	Generate random edge costs.
string &	edge2string (edge, string &) const
	Create readable representation of an edge.
string &	toDotString (string &) const
	Create graphviz representation of this flograph.
Protected Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Wflograph.
void	freeSpace ()
	Free space used by graph.
virtual void	shuffle (int , int )
	Shuffle the vertices and edges according to given permutations.
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.
Protected Attributes
floCost *	cst
	cst[e] is cost of e
Private Member Functions
Wflograph &	operator= (const Wflograph &)

Detailed Description

Class representing a weighted flow graph.

Used in min cost flow problems. Inherits many methods from the Flograph class and adds methods for dealing with edge costs.

Definition at line 25 of file Wflograph.h.

Constructor & Destructor Documentation

grafalgo::Wflograph::Wflograph	(	int	numv = `3`,
		int	maxe = `2`,
		int	s1 = `1`,
		int	t1 = `2`
	)

Construct a Wflograph.

Parameters:

numv	is the number of vertices in the graph
maxe	is the max number of edges in the graph
s1	is the source vertex
t1	is the sink vertex

Definition at line 22 of file Wflograph.cpp.

Here is the call graph for this function:

Member Function Documentation

string & grafalgo::Wflograph::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::Flograph.

Definition at line 130 of file Wflograph.cpp.

Here is the call graph for this function:

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

Copy into list from source.

Definition at line 73 of file Wflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

flow grafalgo::Wflograph::cost	(	vertex	v,
		edge	e
	)		const `[inline]`

Return cost of an edge.

Parameters:

v	is a vertex
e	is an edge that is incident to v

Returns:: the cost of e in the direction from v to mate(v)

Definition at line 64 of file Wflograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Create readable representation of an edge.

Parameters:

e	is an edge
s	is a string in which result is to be returned

Returns:: a reference to s

Reimplemented from grafalgo::Flograph.

Definition at line 185 of file Wflograph.cpp.

Here is the call graph for this function:

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

Expand the space available for this Wflograph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::Flograph.

Definition at line 66 of file Wflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free space used by graph.

Reimplemented from grafalgo::Flograph.

Definition at line 46 of file Wflograph.cpp.

Here is the caller graph for this function:

edge grafalgo::Wflograph::join	(	vertex	u,
		vertex	v
	)		`[virtual]`

Join two vertices with an edge.

Parameters:

u	is a vertex
v	is a vertex

Returns:: the number of the new edge

Reimplemented from grafalgo::Flograph.

Definition at line 204 of file Wflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Allocate and initialize dynamic storage for Wflograph.

Parameters:

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

Reimplemented from grafalgo::Flograph.

Definition at line 33 of file Wflograph.cpp.

Here is the caller graph for this function:

void grafalgo::Wflograph::randCost	(	floCost	lo,
		floCost	hi
	)

Generate random edge costs.

Parameters:

lo	is the low end of the range of costs
hi	is the high end of the range of costs costs are generated uniformly in [lo,hi]

Definition at line 230 of file Wflograph.cpp.

Here is the call graph for this function:

bool grafalgo::Wflograph::readAdjList ( istream & in ) [protected, 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::Flograph.

Definition at line 91 of file Wflograph.cpp.

Here is the call graph for this function:

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

Resize a Wflograph 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::Flograph.

Definition at line 53 of file Wflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Wflograph::setCost	(	edge	e,
		floCost	c
	)		`[inline]`

Set the cost of an edge.

Parameters:

e	is an edge
c	is a new cost to be assigned to e

Definition at line 73 of file Wflograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Wflograph::shuffle	(	int *	,
		int *
	)		`[protected, virtual]`

Shuffle the vertices and edges according to given permutations.

Shuffle the vertices and edges according to the given permutations.

Parameters:

vp	is a permutation on the integers 1..(# of vertices)
ep	is a permutation on the integers 1..(# of edges) This method remaps vertex u to vp[u] and edge e to ep[e]

More precisely, remap all vertices u to vp[u] and all edges e to ep[e].

Parameters:

vp	is a permutation on 1..(# of vertices)
ep	is a permutation on 1..(# of edges)

Reimplemented from grafalgo::Flograph.

Definition at line 242 of file Flograph.cpp.

Here is the call graph for this function:

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

Create graphviz representation of this flograph.

Parameters:

s	is a string in which result is to be returned

Returns:: a reference to s

Reimplemented from grafalgo::Flograph.

Definition at line 156 of file Wflograph.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/Wflograph.h
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Flograph.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Graph.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Mflograph.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Wflograph.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation