LDSP

Contents

• Introduction
• Interface
• API reference
• Revision history

Introduction

The component maintains information about all pairs shortest paths in a weighted directed graph subject to a sequence of edge weight updates. The current implementation of component LDSP is based on the Potentially Uniform Paths Algorithm [C.Demetrescu and G.F.Italiano, "A New Approach to Dynamic All Pairs Shortest Paths", in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC'03), San Diego, California, June 2003. Also Technical Report ALCOM-FT TR-02-92].

Interface

Constants

LDSP_ID LDSP_INFTY LDSP_NIL LDSP_BAD_PARAMETERS

Types

LDSP LDSP_TSetup

Functions

LDSP* LDSP_New (LGraph* inGraph, LEdgeInfo* inEdgeWeights); LDSP* LDSP_NewEmpty (ui2 inNumVertices); void LDSP_Delete (LDSP** AThis); ui2 LDSP_GetNumVertices (LDSP* This); ui4 LDSP_GetEdgeWeight (LDSP* This, ui2 inU, ui2 inV); void LDSP_UpdateEdge (LDSP* This, ui2 inU, ui2 inV, ui4 inW); ui4 LDSP_GetDist (LDSP* This, ui2 inX, ui2 inY); ui2 LDSP_GetLWit (LDSP* This, ui2 inX, ui2 inY); ui2 LDSP_GetRWit (LDSP* This, ui2 inX, ui2 inY); LDSP_TSetup LDSP_GetConfig (LDSP* This); void LDSP_SetConfig (LDSP* This, LDSP_TSetup inSetup); ui4 LDSP_GetUsedMem (LDSP* This); LDSP_TStat LDSP_GetStatistics (LDSP* This); void LDSP_Dump (LDSP* This);

API Reference

Function	Arguments	Description	Returns	Throws
New	LGraph* inGraph	Create object initialized with a graph specified by inGraph, with edge weights given in inEdgeWeights. The input graph can have at most 65536 vertices, which are maintained in the object according to the indices given by LGraph_GetNodeIndex. Caller is responsible of dellocating the created object using LDSP_Delete.	LDSP* address of the newly created object	-
	LEdgeInfo* inEdgeWeights
NewEmpty	ui2 inNumVertices	Create object containing a graph with inNumVertices vertices and no edges. inNumVertices must be in the range [0..65535]. Caller is responsible of dellocating the created object using LDSP_Delete.	LDSP* address of the newly created object	-
Delete	LDSP** ThisA	Release object pointed to by *ThisA. Pointer *ThisA is set to NULL.	void	-
GetNumVertices	LDSP* This	Return the number of vertices in the graph maintained by This as initially specified by New.	ui2 number of vertices in the graph	-
GetEdgeWeight	LDSP* This	Return the weight of edge (inU,inV) in the graph maintained by This. Vertices inU and inV should be in the range [0..GetNumVertices-1].	ui4 weight of edge (inU,inV) in the graph	LDSP_BAD_PARAMETERS if inU and inV are not in the range [0..GetNumVertices-1].
	ui2 inU
	ui2 inV
UpdateEdge	LDSP* This	Updates the weight of edge (inU,inV) in the graph maintained by This to the new non-negative value value inW, which has to be in the range [0,LDSP_INFTY]. Vertex indices inU and inV must be in the range [0..GetNumVertices-1]. Notice: setting inW to LDSP_INFTY corresponds to removing an edge in the underlying graph.	void	LDSP_BAD_PARAMETERS if inU and inV are not in the range [0..GetNumVertices-1] or inW is negative.
	ui2 inU
	ui2 inV
	ui4 inW
GetDist	LDSP* This	Return the distance between vertex inX and vertex inY in the graph maintained by This.	ui4 distance between vertex inX and vertex inY in the graph	LDSP_BAD_PARAMETERS if inX and inY are not in the range [0..GetNumVertices-1].
	ui2 inX
	ui2 inY
GetLWit	LDSP* This	Return vertex successor of inX in the shortest path between inX and inY. If inY is unreachable from inX, then LDSP_NIL is returned.	ui2 leftmost shortest path witness for pair (inX, inY), or LDSP_NIL if no such shortest path exists	LDSP_BAD_PARAMETERS if inX and inY are not in the range [0..GetNumVertices-1].
	ui2 inX
	ui2 inY
GetRWit	LDSP* This	Return vertex predecessor of inY in the shortest path between inX and inY. If inY is unreachable from inX, then LDSP_NIL is returned.	ui2 rightmost shortest path witness for pair (inX, inY), or LDSP_NIL if no such shortest path exists	LDSP_BAD_PARAMETERS if inX and inY are not in the range [0..GetNumVertices-1].
	ui2 inX
	ui2 inY
GetConfig	LDSP* This	Return a struct with the internal current object configuration (see SetConfig for the details of struct LDSP_TSetup).	LDSP_TSetup current object configuration	-
SetConfig	LDSP* This	Change the internal object configuration to the new parameters specified by inSetup as follows: f8 mThreshold smoothing threshold in [0,1]. If the graph is subject to evenly mixed sequences of increase/decrease edge eight updates, 0 is a good choice. If there are long subsequences of decrease operations, use 0.7 (default) f8 mCorrection smoothing threshold correction (usually mThreshold-0.1 or 0 if mThreshold is 0). ui4 mStep # operations between original update and first dummy update of an edge (default = 100) ui4 mRatio smoothing exponential rate (default = 10)	void	-
	LDSP_TSetup inSetup
GetUsedMem	LDSP* This	Return the total number of bytes used to maintain the data structure.	ui4 bytes used to maintain object This	-
GetStatistics	LDSP* This	Return a struct with the following statistics (all ui4 values) about the object: mPUP # potentially uniform paths mUP # uniform paths mHSP # historical shortest paths (mSP+mZombie) mSP # shortest paths mZombie # zombies mFree # free path slots in the data structure mAffected # node pairs with distance changed by the last update mNewPUP # potentially uniform paths created during the last update mDelPUP # potentially uniform paths deleted during the last update mDummyUpdates total # of performed dummy updates mSkipped total # dummy updates skipped using adaptive smoothing strategy	LDSP_TStat object statistics
Dump	LDSP* This	Print information about LDSP object This. (Debug Mode)	void	-

Revision history

• Oct 30, 2002: created.
• Nov 5, 2002: changed.
• May 20, 2003: news.

Last updated: Jul 1, 2003