The SPTree class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements Shortest Path Tree algorithms for solving "uncapacitated" (Linear) Min Cost Flow problems with one source node. More...

#include <SPTree.h>

Inheritance diagram for SPTree:

Public Member Functions
	SPTree (cIndex nmx=0, cIndex mmx=0, bool Drctd=true)
	Constructor of the class. More...

void	LoadNet (cIndex nmx=0, cIndex mmx=0, cIndex pn=0, cIndex pm=0, cFRow pU=0, cCRow pC=0, cFRow pDfct=0, cIndex_Set pSn=0, cIndex_Set pEn=0)
	Inputs a new network, as in MCFClass::LoadNet(). More...

cCRow	MCFGetPi (void)
	Same meaning as MCFClass::MCFGetPi(). More...

SPTree::FONumber	MCFGetFO (void)
	Same meaning as MCFClass::MCFGetFO(). More...

void	ShortestPathTree (void)
	Solver of the Shortest Path Tree Problem from the current Origin. More...

void	SetOrigin (cIndex NewOrg)
	Changes the Origin from which Shortest Paths are computed. More...

void	SetDest (cIndex NewDst)
	Changes the Destination node of Shotest Paths. More...

void	MCFGetX (Index ND, cIndex_Set DB, FRow F, Index_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())
	Like SPTree::MCFGetX( FRow , Index_Set , cIndex , Index ), except that the primal solution that is returned is relative only to the subset of destinations whose names are contained in the first ND entries of the vector DB. More...

SPTree::FONumber	MCFGetFO (Index ND, cIndex_Set DB)
	Like SPTree::MCFGetFO( void ), except that the cost that is returned is that of the primal solution relative only to the subset of destinations whose names are contained in the first ND entries of the vector DB. More...

bool	Reached (cIndex i)
	Return true if a shortest path from Origin to i have already been computed; this can be used when LABEL_SETTING == 1 to determine if a shortest from Origin to i have been obtained as a by-product of the calculation of the shortest path between Origin and some other Dest. More...

cIndex_Set	Predecessors (void)
	Return a cIndex* vector p[] such that p[ i ] is the predecessor of node i in the shortest path tree. More...

cIndex_Set	ArcPredecessors (void)
	Return a cIndex* vector a[] such that a[ i ] is the index of the arc ( p[ i ] , i ), being p[] the vector returned by the above method, and with the same structure. More...

Index	Orig (void)
	Return the root of the SPT problem. More...

Index	DestN (void)
	Return the number of destination nodes in the SPT problem. More...

cIndex_Set	Dests (void)
	Return the DestN()-vector containig the names of destination nodes in the SPT problem; the names are in increasing order and INF-terminated. More...

Index	LenFS (cIndex i)
	Return the size of the Forward Star of node i. More...

Index	ReadFS (cIndex i, cIndex h)
	Return the h-th arc in FS( i ) for h = 0, ... More...

Public Member Functions inherited from MCFClass
	MCFClass (cIndex nmx=0, cIndex mmx=0)
	Constructor of the class. More...

virtual void	LoadDMX (istream &DMXs, bool IsQuad=false)
	Read a MCF instance in DIMACS standard format from the istream. More...

virtual void	PreProcess (void)
	Extract a smaller/easier equivalent MCF problem. More...

virtual void	SetPar (int par, int val)
	Set integer parameters of the algorithm. More...

virtual void	SetPar (int par, double val)
	Set float parameters of the algorithm. More...

virtual void	GetPar (int par, int &val)
	This method returns one of the integer parameter of the algorithm. More...

virtual void	GetPar (int par, double &val)
	This method returns one of the integer parameter of the algorithm. More...

virtual void	SetMCFTime (bool TimeIt=true)
	Allocate an OPTtimers object [see OPTtypes.h] to be used for timing the methods of the class. More...

int	MCFGetStatus (void)
	Returns an int describing the current status of the MCF solver. More...

virtual cFRow	MCFGetX (void)
	Return a read-only pointer to an internal data structure containing the flow solution in "dense" format. More...

virtual bool	HaveNewX (void)
	Return true if a different (approximately) optimal primal solution is available. More...

virtual bool	HaveNewPi (void)
	Return true if a different (approximately) optimal dual solution is available. More...

virtual cCRow	MCFGetRC (void)
	Return a read-only pointer to an internal data structure containing the reduced costs. More...

virtual FONumber	MCFGetDFO (void)
	Return the objective function value of the dual solution currently returned by MCFGetPi() / MCFGetRC(). More...

virtual FNumber	MCFGetUnfCut (Index_Set Cut)
	Return an unfeasibility certificate. More...

virtual Index	MCFGetUnbCycl (Index_Set Pred, Index_Set ArcPred)
	Return an unboundedness certificate. More...

virtual MCFStatePtr	MCFGetState (void)
	Save the state of the MCF solver. More...

virtual void	MCFPutState (MCFStatePtr S)
	Restore the solver to the state in which it was when the state `S' was created with MCFGetState() [see above]. More...

void	TimeMCF (double &t_us, double &t_ss)
	Time the code. More...

double	TimeMCF (void)
	Like TimeMCF(double,double) [see above], but returns the total time. More...

void	CheckPSol (void)
	Check that the primal solution returned by the solver is primal feasible. More...

void	CheckDSol (void)
	Check that the dual solution returned by the solver is dual feasible. More...

Index	MCFnmax (void)
	Return the maximum number of nodes for this instance of MCFClass. More...

Index	MCFmmax (void)
	Return the maximum number of arcs for this instance of MCFClass. More...

Index	MCFn (void)
	Return the number of nodes in the current graph. More...

Index	MCFm (void)
	Return the number of arcs in the current graph. More...

virtual cIndex_Set	MCFSNdes (void)
	Return a read-only pointer to an internal vector containing the starting (tail) nodes for each arc. More...

virtual cIndex_Set	MCFENdes (void)
	Return a read-only pointer to an internal vector containing the ending (head) nodes for each arc. More...

virtual cCRow	MCFCosts (void)
	Return a read-only pointer to an internal vector containing the arc costs. More...

virtual void	MCFQCoef (CRow Qv, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())

virtual CNumber	MCFQCoef (cIndex i)

virtual cCRow	MCFQCoef (void)
	Return a read-only pointer to an internal vector containing the arc costs. More...

virtual cFRow	MCFUCaps (void)
	Return a read-only pointer to an internal vector containing the arc capacities. More...

virtual cFRow	MCFDfcts (void)
	Return a read-only pointer to an internal vector containing the node deficits. More...

virtual void	WriteMCF (ostream &oStrm, int frmt=0)
	Write the current MCF problem to an ostream. More...

virtual void	ChgQCoef (cCRow NQCoef=0, cIndex_Set nms=0, cIndex strt=0, Index stp=Inf< Index >())

virtual void	ChgQCoef (Index arc, cCNumber NQCoef)

virtual	~MCFClass ()
	Destructor of the class. More...

Additional Inherited Members
Public Types inherited from MCFClass
typedef unsigned int	Index
	index of a node or arc ( >= 0 )

typedef Index *	Index_Set
	set (array) of indices

typedef const Index	cIndex
	a read-only index

typedef cIndex *	cIndex_Set
	read-only index array

typedef double	FNumber
	type of arc flow

typedef FNumber *	FRow
	vector of flows

typedef const FNumber	cFNumber
	a read-only flow

typedef cFNumber *	cFRow
	read-only flow array

typedef double	CNumber
	type of arc flow cost

typedef CNumber *	CRow
	vector of costs

typedef const CNumber	cCNumber
	a read-only cost

typedef cCNumber *	cCRow
	read-only cost array

typedef double	FONumber
	type of the objective function: has to hold sums of products of FNumber(s) by CNumber(s)

typedef const FONumber	cFONumber
	a read-only o.f. value

typedef MCFState *	MCFStatePtr
	pointer to a MCFState

Protected Member Functions inherited from MCFClass
template<class T >
bool	ETZ (T x, const T eps)
	true if flow x is equal to zero (possibly considering tolerances). More...

template<class T >
bool	GTZ (T x, const T eps)
	true if flow x is greater than zero (possibly considering tolerances). More...

template<class T >
bool	GEZ (T x, const T eps)
	true if flow x is greater than or equal to zero (possibly considering tolerances). More...

template<class T >
bool	LTZ (T x, const T eps)
	true if flow x is less than zero (possibly considering tolerances). More...

template<class T >
bool	LEZ (T x, const T eps)
	true if flow x is less than or equal to zero (possibly considering tolerances). More...

template<class T >
bool	GT (T x, T y, const T eps)
	true if flow x is greater than flow y (possibly considering tolerances).

template<class T >
bool	LT (T x, T y, const T eps)
	true if flow x is less than flow y (possibly considering tolerances). More...

Protected Attributes inherited from MCFClass
Index	n
	total number of nodes

Index	nmax
	maximum number of nodes

Index	m
	total number of arcs

Index	mmax
	maximum number of arcs

int	status
	return status, see the comments to MCFGetStatus() above. More...

bool	Senstv
	true <=> the latest optimal solution should be exploited

OPTtimers *	MCFt
	timer for performances evaluation

FNumber	EpsFlw
	precision for comparing arc flows / capacities

FNumber	EpsDfct
	precision for comparing node deficits

CNumber	EpsCst
	precision for comparing arc costs

double	MaxTime
	max time (in seconds) in which MCF Solver can find an optimal solution (0 = no limits)

int	MaxIter
	max number of iterations in which MCF Solver can find an optimal solution (0 = no limits)

Detailed Description

The SPTree class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements Shortest Path Tree algorithms for solving "uncapacitated" (Linear) Min Cost Flow problems with one source node.

Warning: The SPT algorithm will enter in an infinite loop if a directed cycle of negative cost exists in the graph: there is no check about this in the code.

Constructor & Destructor Documentation

SPTree	(	cIndex	nmx = `0`,
		cIndex	mmx = `0`,
		bool	Drctd = `true`
	)

Constructor of the class.

For the meaning of nmx and mmx see MCFClass::MCFClass().

The parameter `Drctd' tells if the given graph has really to be understood as directed (default), i.e., if the i-th arc is Sn[ i ] –> En[ i ], or undirected, i.e., the i-th arc is Sn[ i ] <–> En[ i ]. Undirected graphs are internally implemented by doubling each arc, but this is completely hidden by the interface.

Member Function Documentation

void LoadNet	(	cIndex	nmx = `0`,
		cIndex	mmx = `0`,
		cIndex	pn = `0`,
		cIndex	pm = `0`,
		cFRow	pU = `0`,
		cCRow	pC = `0`,
		cFRow	pDfct = `0`,
		cIndex_Set	pSn = `0`,
		cIndex_Set	pEn = `0`
	)

virtual

Inputs a new network, as in MCFClass::LoadNet().

Arcs with pC[ i ] == Inf<CNumber>() do not "exist". If DYNMC_MCF_SPT > 0, these arcs are "closed".

If DYNMC_MCF_SPT == 0 but SAME_GRPH_SPT > 0, these arcs are dealt with explicitly, and can be put back into the formulation by simply changing their cost. Note that, however, this is less efficient than eliminating them explicitly from the problem.

If DYNMC_MCF_SPT == 0 and SAME_GRPH_SPT == 0, these arcs are just removed from the formulation. However, they have some sort of a "special status" (after all, if the user wants to remove them completely he/she can just change the data), in that they are still counted into the number of arcs of the graph and they will always have 0 flow and Inf<CNumber>() reduced cost as "closed" or "deleted" arcs.

Implements MCFClass.

cCRow MCFGetPi ( void )

virtual

Same meaning as MCFClass::MCFGetPi().

Note: Some of the potentials may be + Inf<CNumber>(): this means that

the node is not a destination and it cannot be reached from the Origin (however, this does not mean that the problem is unfeasible);
if LABEL_SETTING == 1, the node is not a destination and it has not been reached during the algorithm.

Reimplemented from MCFClass.

SPTree::FONumber MCFGetFO ( void )

virtual

Same meaning as MCFClass::MCFGetFO().

Note: if not all the specified destinations can be reached from the Origin, returns Inf<FONumber>().

Implements MCFClass.

void ShortestPathTree ( void )

Solver of the Shortest Path Tree Problem from the current Origin.

(specified in the constructor or by SetOrigin(), see below)

If LABEL_SETTING == 0, or if no Destination is speficied (Dst == Inf<Index>() in SetDest() [see below]), the whole Shortest Path Tree (at least, the SPT of the component of the graph connected with Origin) is computed, otherwise the code stops as soon as the shortest path between Origin and Dest is computed.

Note that methods such as MCFGetX(), MCFGetRC() and MCFGetFO() may need some complicate calculations in order to put the solution of the Shortest Path in the correct format; since these calculations change some of the internal data structures, it is not permitted to call again ShortestPathTree() after that any of these methods have been called.

void SetOrigin ( cIndex NewOrg )

inline

Changes the Origin from which Shortest Paths are computed.

References MCFClass::kUnSolved, and USENAME0.

void SetDest ( cIndex NewDst )

inline

Changes the Destination node of Shotest Paths.

If LABEL_SETTING == 0, it has no influence since label correcting methods cannot stop before the whole SPT has been computed. Conversely, label setting algorithms can solve Origin-Dest Shortest Path Problems; therefore, it is possible to obtain shortest paths between Origin and a subset of the nodes, by calling ShortestPathTree() with one of the destinations, and controlling upon completion that all the desidered nodes have been visited (see Reached() below). If this is not the case, ShortestPathTree() can be invoked again with one of the unreached nodes, until they are all visited.

If no Dest is given, or if Dest is set to Inf<Index>(), the whole Shortest Path Tree (at least, the SPT of the component of the graph connected with Origin) is computed.

References MCFClass::kUnSolved, and USENAME0.

void MCFGetX	(	Index	ND,
		cIndex_Set	DB,
		FRow	F,
		Index_Set	nms = `0`,
		cIndex	strt = `0`,
		Index	stp = `Inf< Index >()`
	)

Like SPTree::MCFGetX( FRow , Index_Set , cIndex , Index ), except that the primal solution that is returned is relative only to the subset of destinations whose names are contained in the first ND entries of the vector DB.

Note: node names in ND must be in 1 ... n irrespective of USENAME0.

SPTree::FONumber MCFGetFO	(	Index	ND,
		cIndex_Set	DB
	)

Like SPTree::MCFGetFO( void ), except that the cost that is returned is that of the primal solution relative only to the subset of destinations whose names are contained in the first ND entries of the vector DB.

Note: node names in ND must be in 1 ... n irrespective of USENAME0.

bool Reached ( cIndex i )

inline

Return true if a shortest path from Origin to i have already been computed; this can be used when LABEL_SETTING == 1 to determine if a shortest from Origin to i have been obtained as a by-product of the calculation of the shortest path between Origin and some other Dest.

MCFClass::cIndex_Set Predecessors ( void )

inline

Return a cIndex* vector p[] such that p[ i ] is the predecessor of node i in the shortest path tree.

If a node i has no predecessor, i.e., i == Origin, i does not belong to the connected component of the origin or the computation have been stopped before reaching i, then p[ i ] == 0.

Note: if the name "0" is used for nodes, (USENAME0 == 1) then node names are internally "translated" of +1 to avoid it being used - the the names reported in this vector will follow the same rule.

For this reason, the first entry of p (*p) is not significative.

cIndex_Set ArcPredecessors ( void )

Return a cIndex* vector a[] such that a[ i ] is the index of the arc ( p[ i ] , i ), being p[] the vector returned by the above method, and with the same structure.

If p[ i ] == 0, then a[ i ] is not significative: for the Origin (that has p[ Origin ] == 0), however, it is guaranteed that a[ Origin ] == Inf<Index>().

MCFClass::Index Orig ( void )

inline

Return the root of the SPT problem.

MCFClass::Index DestN ( void )

inline

Return the number of destination nodes in the SPT problem.

MCFClass::cIndex_Set Dests ( void )

inline

Return the DestN()-vector containig the names of destination nodes in the SPT problem; the names are in increasing order and INF-terminated.

MCFClass::Index LenFS ( cIndex i )

inline

Return the size of the Forward Star of node i.

MCFClass::Index ReadFS	(	cIndex	i,
		cIndex	h
	)

inline

Return the h-th arc in FS( i ) for h = 0, ...

, LenFS( i ) - 1.

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation