#include <Graph.h>

Public Types
typedef TPair< Uint, Uint >	TMappedPair
Public Member Functions
	TGraph (bool bDirected=true)
	TGraph (const IMatrix &rMatrix, bool bDirected=true)
virtual Retval	addEdge (Uint uiVertice1, Uint uiVertice2, Float fWeight=1.0)
virtual Retval	addVertice (Uint uiID, IZUnknown *pObject=NULL)
void	assignMatrix (const IMatrix &rMatrix)
void	clearEdges ()
void	clearVertices ()
Retval	getCompleteGraph (TGraph *&rpGraph) const
Retval	getMinimumCostTree (TGraph *&rpGraph) const
Retval	getMinimumCostTree (Uint uiStartVertice, TGraph *&rpGraph) const
Retval	getComplementGraph (TGraph *&rpGraph) const
Retval	getIsomorphicMatches (const TGraph &rGraphToMatch, TSet< TPair< Uint, Uint > > &rMatches) const
Retval	getAdjazentMatrix (IMatrix &rMatrix) const
Int	getEdgeCount () const
Int	getVerticeCount () const
const TEdge &	getEdge (Int iIndex) const
Retval	getVertice (Int iIndex, TVertice *&rpVertice) const
Retval	getVerticeByID (Uint uiID, TVertice *&rpVertice) const
Float	getWeightSum (Uint uiFromID, Uint uiToID) const
bool	equals (const TGraph &rGraph, bool bIsomorphism=false) const
bool	hasCylce () const
bool	hasEdge (Uint uiVertice1, Uint uiVertice2) const
bool	hasEdge (Uint uiVertice1, Uint uiVertice2, Float fWeight) const
bool	hasVertice (Uint uiID) const
bool	isConnected (Uint uiVertice1, Uint uiVertice2) const
bool	isDirected () const
bool	isEmpty () const
Retval	removeEdge (Uint uiVertice1, Uint uiVertice2)
Retval	removeEdge (Uint uiVertice1, Uint uiVertice2, Float fWeight)
TGraphIterator *	getIterator ()
const TGraphIterator *	getConstIterator () const
TGraphIterator *	getDepthFirstIterator ()
const TGraphIterator *	getConstDepthFirstIterator () const
TGraphIterator *	getBreathFirstIterator ()
const TGraphIterator *	getConstBreathFirstIterator () const
Protected Member Functions
virtual	~TGraph ()
Retval	addEdge (TEdge &rEdge)
Retval	addVertice (TVertice &rVertice)
bool	hasEdge (TEdge &rEdge, bool bIgnoreWeight) const
Retval	removeEdge (TEdge &rEdge, bool bIgnoreWeight)
void	cloneVerticesOfGraph (const TGraph &rGraph)

Detailed Description

Generic implementation of the graph theorie

Member Typedef Documentation

typedef TPair<Uint, Uint> zeus::TGraph::TMappedPair

Constructor & Destructor Documentation

TGraph::TGraph ( bool bDirected = true )

Creates a graph

Parameters:

bDirected : Flag for directed graph

TGraph::TGraph	(	const IMatrix &	rMatrix,
		bool	bDirected = `true`
	)

Creates a graph

Parameters:

rMatrix	: Matrix of laplacian or adjazent matrix
bDirected	: Flag for directed graph

TGraph::~TGraph ( ) [protected, virtual]

Destroys the graph

Member Function Documentation

Retval zeus::TGraph::addEdge	(	Uint	uiVertice1,
		Uint	uiVertice2,
		Float	fWeight = `1.0`
	)		`[inline, virtual]`

adds a new edge to the graph

Parameters:

uiVertice1	: vertice 1
uiVertice2	: vertice 2
fWeight	: Weight of the vertice

Return values:

RET_NOERROR	: Edge added
RET_REQUEST_FAILED	: Could not add the edge because the vertices are not known

Retval TGraph::addEdge ( TEdge & rEdge ) [protected]

adds a new edge to the graph

Parameters:

rEdge : Edge information to add

Return values:

RET_NOERROR	: Edge added
RET_REQUEST_FAILED	: Could not add the edge because the vertices are not known

Retval zeus::TGraph::addVertice	(	Uint	uiID,
		IZUnknown *	pObject = `NULL`
	)		`[inline, virtual]`

adds a new vertice to the graph

Parameters:

uiID	: ID of vertice
pObject	: object of vertice

Return values:

RET_NOERROR	: vertice added
RET_REQUEST_FAILED	: vertice already added

Retval TGraph::addVertice ( TVertice & rVertice ) [protected]

adds a vertice to the graph

Parameters:

rVertice : vertice

Return values:

RET_NOERROR	: Vertice added
RET_REQUEST_FAILED	: Vertice was already added

void TGraph::assignMatrix ( const IMatrix & rMatrix )

Assigns a matrix graph representation

void TGraph::clearEdges ( )

Removes all edges of the graph

void TGraph::clearVertices ( )

Removes all vertices of the graph

void TGraph::cloneVerticesOfGraph ( const TGraph & rGraph ) [protected]

clones all vertices and assigns them to this graph

bool TGraph::equals	(	const TGraph &	rGraph,
		bool	bIsomorphism = `false`
	)		const

Checks if two graphs are equal. If the bIsomorphism flag is not set, then the two graphs has to match exactly, meaning for all vertices G1::v1 = G2:v1, G1:v2 = G2:v2 ... G1::v_n = G2:v_n and for all edges G1::E(G1::v_x, G1::v_y, w) = G2::E(G2::v_x, G2::v_y, w). If the flag is set, then the isomorphism is checked. Note that this is a NP-complete problem, meaning there exists no polynominal algorithm at the moment and therefore the time complexity is exponential O(2^n). Its recommended to set the flag only for small graphs.

Parameters:

rGraph	: graph to check
bIsomorphism	: flag to check if the graphs are isomorph

Return values:

true	: graphs are equal or isomorph
false,:	graphs are not equal

Retval TGraph::getAdjazentMatrix ( IMatrix & rMatrix ) const

Returns the ajazent matrix representation of this graph

TGraphIterator * TGraph::getBreathFirstIterator ( )

returns the depth first iterator of the graph

Retval TGraph::getComplementGraph ( TGraph *& rpGraph ) const

This method returns the complement of this graph

Retval TGraph::getCompleteGraph ( TGraph *& rpGraph ) const

This method returns a completes graph containing all vertices of this graph. The returned graph is undirected. Each vertice has an edge to the other vertices.

Parameters:

rpGraph : returns the new graph

Return values:

RET_NOERROR	: Graph created
RET_REQUEST_FAILED	: Could not create a complete graph

const TGraphIterator * zeus::TGraph::getConstBreathFirstIterator ( ) const [inline]

Returns the const breath first iterator

const TGraphIterator * zeus::TGraph::getConstDepthFirstIterator ( ) const [inline]

Returns the const depth first iterator

const TGraphIterator* zeus::TGraph::getConstIterator ( ) const [inline]

TGraphIterator * TGraph::getDepthFirstIterator ( )

returns the depth first iterator of the graph

const TEdge & zeus::TGraph::getEdge ( Int iIndex ) const [inline]

Returns an indexed edge

Int zeus::TGraph::getEdgeCount ( ) const [inline]

Returns the number of edges

Retval TGraph::getIsomorphicMatches	(	const TGraph &	rGraphToMatch,
		TSet< TPair< Uint, Uint > > &	rMatches
	)		const

This method returns the isomorphic matches of each vertice from this graph with the graph given by parameter rGraphToMatch.

Parameters:

rGraphToMatch	: Graph to match
rMatches	: Return parameter of isomorphic matches

Return values:

RET_NOERROR	: Isomorphic graph found
RET_REQUEST_FAILED	: Could not match the graph rGraphToMatch

TGraphIterator* zeus::TGraph::getIterator ( ) [inline]

Retval zeus::TGraph::getMinimumCostTree ( TGraph *& rpGraph ) const [inline]

See also:: TGraph::getMinimumCostTree

Retval TGraph::getMinimumCostTree	(	Uint	uiStartVertice,
		TGraph *&	rpGraph
	)		const

This method returns the minimum-cost spanning tree of this graph. This is mostly used to find the cheapest way from a start node to the target node. The graph returned is a cyle free and directed graph (called tree). The method implements the algorithme of Prim (priority search)

Parameters:

uiStartVertice	: ID of start vertice
rpGraph	: Return parameter of the minimum-cost spanning tree

Return values:

RET_NOERROR	: minimum-cost spanning tree created
RET_REQUEST_FAILED	: could not create minimum-cost spanning tree

Retval TGraph::getVertice	(	Int	iIndex,
		TVertice *&	rpVertice
	)		const

Returns an indexed vertices

Parameters:

iIndex	: List index
rpVertice	: return parameter

Return values:

RET_NOERROR	: Vertice found and returned
RET_REQUEST_FAILED	: Vertice not found

Retval TGraph::getVerticeByID	(	Uint	uiID,
		TVertice *&	rpVertice
	)		const

Returns a vertices by ID

Parameters:

uiID	: vertice ID
rpVertice	: return parameter

Return values:

RET_NOERROR	: Vertice found and returned
RET_REQUEST_FAILED	: Vertice not found

Int zeus::TGraph::getVerticeCount ( ) const [inline]

Returns the number of vertices

Float TGraph::getWeightSum	(	Uint	uiFromID,
		Uint	uiToID
	)		const

Returns the sum of all weights from one vertice to the other vertice

Parameters:

uiFromID	: ID of the first vertice
uiToID	: ID of the second vertice

Returns:: Weight. if zero is returned no edge has been found

bool TGraph::hasCylce ( ) const

Checks if the graph has any cycles. If the cycle is undirected this method will return always true

Return values:

true	: There exists a cycle
false,:	No cycle found

bool TGraph::hasEdge	(	TEdge &	rEdge,
		bool	bIgnoreWeight
	)		const `[protected]`

Checks if there is an edge between two vertices.

bool zeus::TGraph::hasEdge	(	Uint	uiVertice1,
		Uint	uiVertice2
	)		const `[inline]`

checks if an edge between vertice 1 and vertice 2 is included by the graph. The weight is ignored.

bool zeus::TGraph::hasEdge	(	Uint	uiVertice1,
		Uint	uiVertice2,
		Float	fWeight
	)		const `[inline]`

checks if an edge between vertice 1 and vertice 2 is included by the graph.

bool zeus::TGraph::hasVertice ( Uint uiID ) const [inline]

checks if a vertice is included by the graph

bool TGraph::isConnected	(	Uint	uiVertice1,
		Uint	uiVertice2
	)		const

Checks if the two vertices are connected. For directed graphs the direction is concerned. There fore the vertice 2 is a "sub" vertice of vertice 1: vertice1 --> vertice2

Parameters:

uiVertice1	: ID of the first vertice
uiVertice2	: ID of the second vertice

Return values:

false	: vertices are not connected
true	: Vertices are connected

bool zeus::TGraph::isDirected ( ) const [inline]

Checks if the graph is directed

bool zeus::TGraph::isEmpty ( ) const [inline]

checks if the graph is empty (no vertices)

Retval TGraph::removeEdge	(	TEdge &	rEdge,
		bool	bIgnoreWeight
	)		`[protected]`

Removes an edge between two vertices.

Parameters:

rEdge	: edge to remove
bIgnoreWeight	: if flag is set, the search will ignore the weight

Return values:

RET_NOERROR	: edge removed
RET_REQUEST_FAILED	: Could not find an edge between the two vertices

Retval zeus::TGraph::removeEdge	(	Uint	uiVertice1,
		Uint	uiVertice2,
		Float	fWeight
	)		`[inline]`

Removes an edge between vertice 1 and vertice 2 with a specific weight.

Parameters:

uiVertice1	: vertice 1
uiVertice2	: vertice 2
fWeight	: weight

Return values:

RET_NOERROR	: edge removed
RET_REQUEST_FAILED	: Could not find an edge between the two vertices

Retval zeus::TGraph::removeEdge	(	Uint	uiVertice1,
		Uint	uiVertice2
	)		`[inline]`

Removes an edge between vertice 1 and vertice 2. The weight is ignored. If there are more than one edge matching, the first will be removed.

Parameters:

uiVertice1	: vertice 1
uiVertice2	: vertice 2

Return values:

RET_NOERROR	: edge removed
RET_REQUEST_FAILED	: Could not find an edge between the two vertices

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

zeus::TGraph Class Reference

Public Types

Public Member Functions

Protected Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation