Detailed Description

Computes the shortest-cost path between all pairs of vertices in a graph. Takes O(n^3) time.

#include <GGraph.h>

Public Member Functions
	GFloydWarshall (size_t nodes)
	nodes specifies the number of nodes in the graph. More...

	~GFloydWarshall ()

void	addDirectedEdge (size_t from, size_t to, double cost)
	Adds a directed edge to the graph. (You must call this to add all the edges before calling compute.) More...

void	compute ()
	Computes the shortest-cost path between every pair of points (You must add all the edges before you call compute.) More...

double	cost (size_t from, size_t to)
	Returns the smallest cost to get from node "from" to node "to". (You must call compute before calling this) More...

GMatrix *	costMatrix ()
	Returns a pointer to the cost matrix. More...

bool	isConnected ()
	Scans the entire cost matrix, and returns false if any node is unreachable from any other node. (Assumes compute has already been called.) More...

size_t	next (size_t from, size_t goal)
	Returns the next node on the shortest path from node "from" to get to node "goal" (You must call compute before calling this) More...

size_t	nodeCount ()
	Returns the number of nodes in the graph. More...

GMatrix *	releaseCostMatrix ()
	Returns the cost matrix. You are responsible to delete it. (This class should not be used after this method is called.) More...

Static Public Member Functions
static void	test ()
	Performs unit tests for this class. Throws an exception if there is a failure. More...

Constructor & Destructor Documentation

GClasses::GFloydWarshall::GFloydWarshall ( size_t nodes )

nodes specifies the number of nodes in the graph.

GClasses::GFloydWarshall::~GFloydWarshall ( )

void GClasses::GFloydWarshall::addDirectedEdge	(	size_t	from,
		size_t	to,
		double	cost
	)

Adds a directed edge to the graph. (You must call this to add all the edges before calling compute.)

void GClasses::GFloydWarshall::compute ( )

Computes the shortest-cost path between every pair of points (You must add all the edges before you call compute.)

double GClasses::GFloydWarshall::cost	(	size_t	from,
		size_t	to
	)

Returns the smallest cost to get from node "from" to node "to". (You must call compute before calling this)

GMatrix* GClasses::GFloydWarshall::costMatrix ( )

inline

Returns a pointer to the cost matrix.

bool GClasses::GFloydWarshall::isConnected ( )

Scans the entire cost matrix, and returns false if any node is unreachable from any other node. (Assumes compute has already been called.)

size_t GClasses::GFloydWarshall::next	(	size_t	from,
		size_t	goal
	)

Returns the next node on the shortest path from node "from" to get to node "goal" (You must call compute before calling this)

size_t GClasses::GFloydWarshall::nodeCount ( )

inline

Returns the number of nodes in the graph.

GMatrix* GClasses::GFloydWarshall::releaseCostMatrix ( )

Returns the cost matrix. You are responsible to delete it. (This class should not be used after this method is called.)

static void GClasses::GFloydWarshall::test ( )

static

Performs unit tests for this class. Throws an exception if there is a failure.

size_t GClasses::GFloydWarshall::m_nodes

protected

GMatrix* GClasses::GFloydWarshall::m_pCosts

protected

size_t* GClasses::GFloydWarshall::m_pPaths

protected