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 (Index nmx=0, Index mmx=0, bool Drctd=true)
	Constructor of the class.

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

cCRow	MCFGetPi (void) const override
	Same meaning as MCFClass::MCFGetPi().

FONumber	MCFGetFO (void) const override
	Same meaning as MCFClass::MCFGetFO().

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

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

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

void	MCFGetX (Index ND, cIndex_Set DB, FRow F, Index_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const
	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.

FONumber	MCFGetFO (Index ND, cIndex_Set DB) const
	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.

bool	Reached (Index i) const
	Returns 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.

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

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.

Index	Orig (void) const
	returns the root of the SPT problem

Index	DestN (void) const
	returns the number of destination nodes in the SPT problem

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

Index	LenFS (Index i) const
	returns the size of the Forward Star of node i

Index	ReadFS (Index i, Index h) const
	returns the h-th arc in FS( i ) for h = 0, ... , LenFS( i ) - 1

virtual void	MCFGetX (FRow F, Index_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const=0
	write the optimal flow solution in a vector

virtual cFRow	MCFGetX (void) const
	return a read-only pointer to the flow solution

virtual void	MCFGetRC (CRow CR, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const=0
	write the reduced costs in a vector

virtual cCRow	MCFGetRC (void) const
	return a read-only pointer to an the reduced costs

virtual CNumber	MCFGetRC (Index i) const=0
	return the reduced cost of the i-th arc

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

virtual void	LoadDMX (istream &DMXs, bool IsQuad=false)
	read a MCF instance from a stream

virtual void	PreProcess (void)
	pre-process the instamce

virtual void	SetPar (int par, int val)
	set integer parameters of the algorithm

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

virtual void	GetPar (int par, int &val) const
	returns one of the integer parameters of the algorithm

virtual void	GetPar (int par, double &val) const
	returns one of the double parameters of the algorithm

virtual void	SetMCFTime (bool TimeIt=true)
	set the timer of the code

int	MCFGetStatus (void) const
	returns the solution status

virtual bool	HaveNewX (void)
	tells if a different flow solution is available

virtual bool	HaveNewPi (void)
	tells if a different dual solution is available

virtual FONumber	MCFGetDFO (void) const
	return the objective function value of the dual solution

virtual FNumber	MCFGetUnfCut (Index_Set Cut) const
	return an unfeasibility certificate

virtual Index	MCFGetUnbCycl (Index_Set Pred, Index_Set ArcPred) const
	return an unboundedness certificate

virtual MCFStatePtr	MCFGetState (void) const
	save the state of the MCF solver

virtual void	MCFPutState (MCFStatePtr S)
	restore the state of the solver

void	TimeMCF (double &t_us, double &t_ss) const
	time the code

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

void	CheckPSol (void) const
	checks the primal solution

void	CheckDSol (void) const
	checks the dual solution

Index	MCFnmax (void) const
	return the maximum number of nodes

Index	MCFmmax (void) const
	return the maximum number of arcs

Index	MCFn (void) const
	return the current number of nodes

Index	MCFm (void) const
	return the current number of arcs

virtual cIndex_Set	MCFSNdes (void) const
	return a read-only pointer to the vector of starting nodes

virtual cIndex_Set	MCFENdes (void) const
	return a read-only pointer to the vector of ending nodes

virtual cCRow	MCFCosts (void) const
	return a read-only pointer to the vector of arc costs

virtual void	MCFQCoef (CRow Qv, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >()) const
	write the quadratic coefficients of the arc costs into a vector

virtual CNumber	MCFQCoef (Index i) const
	return the quadratic coefficients of the cost of the i-th arc

virtual cCRow	MCFQCoef (void) const
	return a read-only pointer to the vector of arc quadratic costs

virtual cFRow	MCFUCaps (void) const
	return a read-only pointer to an the vector of arc capacities

virtual cFRow	MCFDfcts (void) const
	return a read-only pointer to the vector of node deficits

virtual void	WriteMCF (ostream &oStrm, int frmt=0) const
	write the current MCF problem to an ostream

virtual void	ChgQCoef (cCRow NQCoef=0, cIndex_Set nms=0, Index strt=0, Index stp=Inf< Index >())
	change the quadratic coefficients of the arc costs

virtual void	ChgQCoef (Index arc, CNumber NQCoef)
	change the quadratic coefficient of the cost of the i-th arc

virtual Index	AddArc (Index Start, Index End, FNumber aU, CNumber aC)=0
	adds a new arc

virtual	~MCFClass ()
	destructor of the class

Additional Inherited Members
Public Types inherited from MCFClass
enum	MCFParam { kMaxTime = 0 , kMaxIter , kEpsFlw , kEpsDfct , kEpsCst , kReopt , kLastParam }
	Public enum describing the possible parameters of the MCF solver, to be used with the methods SetPar() and GetPar(). More...

enum	MCFStatus { kUnSolved = -1 , kOK = 0 , kStopped , kUnfeasible , kUnbounded , kError }
	Public enum describing the possible status of the MCF solver. More...

enum	MCFAnswer { kNo = 0 , kYes }
	Public enum describing the possible reoptimization status of the MCF solver. More...

enum	MCFFlFrmt { kDimacs = 0 , kQDimacs , kMPS , kFWMPS }
	Public enum describing the possible file formats in WriteMCF(). More...

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, T eps) const
	true if flow x is equal to zero (possibly considering tolerances).

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

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

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

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

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

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

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.

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()

SPTree	(	Index	nmx = `0`,
		Index	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

◆ LoadNet()

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

overridevirtual

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, 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.

◆ MCFGetPi()

cCRow MCFGetPi ( void ) const

inlineoverridevirtual

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.

◆ MCFGetFO() [1/2]

FONumber MCFGetFO ( void ) const

inlineoverridevirtual

Same meaning as MCFClass::MCFGetFO().

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

Implements MCFClass.

◆ ShortestPathTree()

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.

◆ SetDest()

void SetDest ( Index 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, MCFClass::status, and USENAME0.

◆ MCFGetX() [1/3]

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

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.

◆ MCFGetFO() [2/2]

FONumber MCFGetFO	(	Index	ND,
		cIndex_Set	DB
	)		const

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.

◆ Predecessors()

cIndex_Set Predecessors ( void ) const

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.

◆ ArcPredecessors()

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 >().

◆ MCFGetX() [2/3]

virtual void MCFGetX	(	FRow	F,
		Index_Set	nms = `0`,
		Index	strt = `0`,
		Index	stp = `Inf< Index >()`
	)		const

virtual

write the optimal flow solution in a vector

Write the optimal flow solution in the vector F[]. If nms == 0, F[] will be in "dense" format, i.e., the flow relative to arc ‘i’ (i in 0 .. m - 1) is written in F[ i ]. If nms != 0, F[] will be in "sparse" format, i.e., the indices of the nonzero elements in the flow solution are written in nms (that is then Inf< Index >()-terminated) and the flow value of arc nms[ i ] is written in F[ i ]. Note that nms is not* guaranteed to be ordered. Also, note that, unlike MCFGetRC() and MCFGetPi() [see below], nms is an output of the method.

The parameters ‘strt’ and ‘stp’ allow to restrict the output of the method to all and only the arcs ‘i’ with strt <= i < min( MCFm() , stp ).

Implements MCFClass.

◆ MCFGetX() [3/3]

virtual cFRow MCFGetX ( void ) const

inlinevirtual

return a read-only pointer to the flow solution

Return a read-only pointer to an internal data structure containing the flow solution in "dense" format. Since this may not always be available, depending on the implementation, this method can (uniformly) return 0. This is done by the base class already, so a derived class that does not have the information ready does not need to implement the method.

Reimplemented from MCFClass.

◆ MCFGetRC() [1/3]

virtual void MCFGetRC	(	CRow	CR,
		cIndex_Set	nms = `0`,
		Index	strt = `0`,
		Index	stp = `Inf< Index >()`
	)		const

virtual

write the reduced costs in a vector

Write the reduced costs corresponding to the current dual solution in RC[]. If nms == 0, the reduced cost of arc ‘i’ (i in 0 .. m - 1) is written in RC[ i ]; if nms != 0, it must point to a vector of indices in 0 .. m - 1 (ordered in increasing sense and Inf< Index >()-terminated), and the reduced cost of arc nms[ i ] is written in RC[ i ]. Note that, unlike MCFGetX() above, nms is an input of the method.

The parameters ‘strt’ and ‘stp’ allow to restrict the output of the method to all and only the arcs ‘i’ with strt <= i < min( MCFm() , stp ). ‘strt’ and ‘stp’ work in "&&" with nms; that is, if nms != 0 then only the values corresponding to arcs which are both in nms[] and whose index is in the correct range are returned.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() [see above] which returns true.

Implements MCFClass.

◆ MCFGetRC() [2/3]

virtual cCRow MCFGetRC ( void ) const

inlinevirtual

return a read-only pointer to an the reduced costs

Return a read-only pointer to an internal data structure containing the reduced costs. Since this may not always be available, depending on the implementation, this method can (uniformly) return 0. This is done by the base class already, so a derived class that does not have the information ready does not need to implement the method.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() which returns true.

Reimplemented from MCFClass.

◆ MCFGetRC() [3/3]

virtual CNumber MCFGetRC ( Index i ) const

virtual

return the reduced cost of the i-th arc

Return the reduced cost of the i-th arc. This information should be cheapily available in most implementations.

Note: the output of MCFGetRC() will change after any call to HaveNewPi() which returns true.

Implements MCFClass.

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SPTree()

Member Function Documentation

◆ LoadNet()

◆ MCFGetPi()

◆ MCFGetFO() [1/2]

◆ ShortestPathTree()

◆ SetDest()

◆ MCFGetX() [1/3]

◆ MCFGetFO() [2/2]

◆ Predecessors()

◆ ArcPredecessors()

◆ MCFGetX() [2/3]

◆ MCFGetX() [3/3]

◆ MCFGetRC() [1/3]

◆ MCFGetRC() [2/3]

◆ MCFGetRC() [3/3]