Class that represents a flograph. More...

#include <Flograph.h>

Inheritance diagram for grafalgo::Flograph:

Collaboration diagram for grafalgo::Flograph:

Classes
struct	FloInfo
Public Member Functions
	Flograph (int=3, int=2, int=1, int=2)
	Constructor for Flograph objects.
	Flograph (const Flograph &)
void	resize (int, int)
	Resize a Flograph object.
void	resize (int numv)
void	expand (int, int)
	Expand the space available for this Flograph.
void	expand (int numv)
void	copyFrom (const Flograph &)
	Copy into list from source.
vertex	src () const
	Get the source for a flograph.
vertex	snk () const
	Get the sink for a flograph.
void	setSrc (vertex)
	Set the source and sink vertices.
void	setSnk (vertex)
	Set the source and sink vertices.
flow	cap (vertex, edge) const
	Get the capacity of an edge.
flow	f (vertex, edge) const
	Get the flow on an edge.
flow	res (vertex, edge) const
	Get the residual capacity of an edge.
void	addFlow (vertex, edge, flow)
	Add to the flow on an edge.
void	setFlow (edge, flow)
	Change the flow on an edge.
void	clearFlow ()
	Remove flow from all edges.
void	setCapacity (edge, flow)
	Change the capacity of an edge.
virtual edge	join (vertex, vertex)
	Join two vertices with an edge.
string &	edge2string (edge, string &) const
	Create readable representation of an edge.
string &	toDotString (string &) const
	Create graphviz representation of this flograph.
void	randCapacity (flow, flow)
	Generate random edge capacities.
void	rgraph (int, int, int)
	Generate random flow graph.
Protected Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Flograph.
void	freeSpace ()
	Free space used by graph.
virtual void	shuffle (int , int )
string &	adjList2string (edge, string &) const
	Create a string representation of an adjacency list.
bool	readAdjList (istream &)
	Read adjacency list from an input stream, add it to the graph.
Flograph &	operator= (const Flograph &)
Protected Attributes
vertex	s
vertex	t
	source and sink vertices
FloInfo *	floInfo
	floInfo[e] contains the flow information for edge e

Detailed Description

Class that represents a flograph.

Inherits methods from the Digraph class and adds information and methods for dealing with flows and edge capcities

Definition at line 24 of file Flograph.h.

Constructor & Destructor Documentation

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

Constructor for Flograph objects.

Parameters:

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

Definition at line 21 of file Flograph.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::Flograph::addFlow	(	vertex	v,
		edge	e,
		flow	ff
	)

Add to the flow on an edge.

Parameters:

v	is a vertex
e	is an edge with v as one of its endpoints
ff	is a flow to be added to e, from v to the other endpoint

Returns:: the amount of flow on the edge leaving v, after ff has been added

Definition at line 147 of file Flograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Flograph::adjList2string	(	edge	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::Digraph.

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

Definition at line 187 of file Flograph.cpp.

Here is the call graph for this function:

flow grafalgo::Flograph::cap	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the capacity of an edge.

Parameters:

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

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

Definition at line 91 of file Flograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Copy into list from source.

Definition at line 74 of file Flograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 168 of file Flograph.cpp.

Here is the call graph for this function:

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

Expand the space available for this Flograph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::Digraph.

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

Definition at line 67 of file Flograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

flow grafalgo::Flograph::f	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the flow on an edge.

Parameters:

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

Returns:: the flow on e, going from v to mate(v)

Definition at line 101 of file Flograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free space used by graph.

Reimplemented from grafalgo::Digraph.

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

Definition at line 47 of file Flograph.cpp.

Here is the caller graph for this function:

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

Join two vertices with an edge.

Parameters:

u	is a vertex number
v	is a vertex number

Returns:: number of new edge from u to v

Reimplemented from grafalgo::Graph.

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

Definition at line 129 of file Flograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Allocate and initialize dynamic storage for Flograph.

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.

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

Definition at line 34 of file Flograph.cpp.

Here is the caller graph for this function:

void grafalgo::Flograph::randCapacity	(	flow	ec1,
		flow	ec2
	)

Generate random edge capacities.

Parameters:

ec1	is the max capacity of the source/sink edges
ec2	is the max capacity of the remaining edges edge capacities are selected uniformly with a minimum of 1

Definition at line 292 of file Flograph.cpp.

Here is the call graph for this function:

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

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

Definition at line 91 of file Flograph.cpp.

Here is the call graph for this function:

flow grafalgo::Flograph::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 in grafalgo::Mflograph.

Definition at line 111 of file Flograph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

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

Definition at line 54 of file Flograph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Flograph::rgraph	(	int	numv,
		int	nume,
		int	mss
	)

Generate random flow graph.

Parameters:

numv	is the number of vertices in the generated graph
nume	is the number of edges in the generated graph
mss	is the out-degree of the source and the in-degree of the sink

The generated graph has a "core" subgraph with numv-2 nodes and nume-2*mss edges and the specified span. It is generated using Digraph::rgraph. The source and sink are then added to the core. If mss>(numv-2)/4, it is first reduced to (numv-2)/4.

Reimplemented from grafalgo::Graph.

Definition at line 264 of file Flograph.cpp.

Here is the call graph for this function: