Class representing a flow graph with minimum flow constraints. More...

#include <Mflograph.h>

Inheritance diagram for grafalgo::Mflograph:

Collaboration diagram for grafalgo::Mflograph:

Public Member Functions
	Mflograph (int=3, int=2, int=1, int=2)
	Construct a Mflograph.
void	resize (int, int)
	Resize a Mflograph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Mflograph.
void	expand (int numv)
void	copyFrom (const Mflograph &)
	Copy into list from source.
flow	res (vertex, edge) const
	Get the residual capacity of an edge.
virtual edge	join (vertex, vertex)
	Join two vertices with an edge.
flow	minFlo (edge) const
	Return cost of an edge.
void	setMinFlo (edge, flow)
	Set the min flow constraint of an edge.
void	randMinFlo (flow, flow)
	Generate random min capacities.
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 Mflograph.
void	freeSpace ()
	Free space used by graph.
virtual void	shuffle (int , int )
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
flow *	mflo
	mflo[e] is min flow for e
Private Member Functions
Mflograph &	operator= (const Mflograph &)

Detailed Description

Class representing a flow graph with minimum flow constraints.

Inherits many methods from the Flograph class and adds methods for dealing with min flow constraints.

Definition at line 22 of file Mflograph.h.

Constructor & Destructor Documentation

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

Construct a Mflograph.

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

Here is the call graph for this function:

Member Function Documentation

string & grafalgo::Mflograph::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 Mflograph.cpp.

Here is the call graph for this function:

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

Copy into list from source.

Definition at line 73 of file Mflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Mflograph::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 157 of file Mflograph.cpp.

Here is the call graph for this function:

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

Expand the space available for this Mflograph.

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free space used by graph.

Reimplemented from grafalgo::Flograph.

Definition at line 46 of file Mflograph.cpp.

Here is the caller graph for this function:

edge grafalgo::Mflograph::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 Mflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Allocate and initialize dynamic storage for Mflograph.

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

Here is the caller graph for this function:

flow grafalgo::Mflograph::minFlo ( 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 61 of file Mflograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Mflograph::randMinFlo	(	flow	lo,
		flow	hi
	)

Generate random min capacities.

Parameters:

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

Definition at line 230 of file Mflograph.cpp.

Here is the call graph for this function:

bool grafalgo::Mflograph::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 Mflograph.cpp.

Here is the call graph for this function:

flow grafalgo::Mflograph::res	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the residual capacity of an edge.

Parameters:

v	is a vertex in the flograph
e	is an edge that is incident to v

Returns:: the unused capacity of e, going from v to mate(v)

Reimplemented from grafalgo::Flograph.

Definition at line 82 of file Mflograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Resize a Mflograph 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 Mflograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Mflograph::setMinFlo	(	edge	e,
		flow	c
	)		`[inline]`

Set the min flow constraint of an edge.

Parameters:

e	is an edge
c	is a new min flow contraint to be assigned to e; if the specified c is smaller than the max edge capacity, the min flow contraint is set equal to the max capacity

Definition at line 72 of file Mflograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Mflograph::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 175 of file Mflograph.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/Mflograph.h
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Mflograph.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation