Priority Queue

Detailed Description

priority queue with O(1) access to the minimum element

Functions
SCIP_RETCODE	SCIPpqueueCreate (SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
void	SCIPpqueueFree (SCIP_PQUEUE **pqueue)
void	SCIPpqueueClear (SCIP_PQUEUE *pqueue)
SCIP_RETCODE	SCIPpqueueInsert (SCIP_PQUEUE *pqueue, void *elem)
void	SCIPpqueueDelPos (SCIP_PQUEUE *pqueue, int pos)
void *	SCIPpqueueRemove (SCIP_PQUEUE *pqueue)
void *	SCIPpqueueFirst (SCIP_PQUEUE *pqueue)
int	SCIPpqueueNElems (SCIP_PQUEUE *pqueue)
void **	SCIPpqueueElems (SCIP_PQUEUE *pqueue)
int	SCIPpqueueFind (SCIP_PQUEUE *pqueue, void *elem)

Function Documentation

SCIPpqueueCreate()

SCIP_RETCODE SCIPpqueueCreate	(	SCIP_PQUEUE **	pqueue,
		int	initsize,
		SCIP_Real	sizefac,
		SCIP_DECL_SORTPTRCOMP((*ptrcomp))	,
		SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos))
	)

creates priority queue

Parameters

pqueue	pointer to a priority queue
initsize	initial number of available element slots
sizefac	memory growing factor applied, if more element slots are needed

Definition at line 1236 of file misc.c.

References BMSallocMemory, MAX, NULL, pqueueResize(), SCIP_ALLOC, SCIP_CALL, and SCIP_OKAY.

Referenced by daExec(), dualascent_execPcMw(), initData(), initProblem(), nodepairqueueCreate(), SCIPbendersActivate(), SCIPconflictCreate(), SCIPStpHeurLocalExtendPcMw(), subtreeSumGapStoreNode(), and tmVnoiInit().

SCIPpqueueFree()

void SCIPpqueueFree

(

SCIP_PQUEUE **

pqueue

)

frees priority queue, but not the data elements themselves

Parameters

pqueue

pointer to a priority queue

Definition at line 1263 of file misc.c.

References BMSfreeMemory, BMSfreeMemoryArray, and NULL.

Referenced by daExec(), dualascent_execPcMw(), freeProblem(), nodepairqueueFree(), SCIPbendersDeactivate(), SCIPconflictFree(), SCIPStpHeurLocalExtendPcMw(), subtreeSumGapDelSubtrees(), and tmVnoiFree().

SCIPpqueueClear()

void SCIPpqueueClear

(

SCIP_PQUEUE *

pqueue

)

clears the priority queue, but doesn't free the data elements themselves

Parameters

pqueue

priority queue

Definition at line 1274 of file misc.c.

References SCIP_PQueue::len, and NULL.

Referenced by conflictClear().

SCIPpqueueInsert()

SCIP_RETCODE SCIPpqueueInsert	(	SCIP_PQUEUE *	pqueue,
		void *	elem
	)

inserts element into priority queue

Parameters

pqueue	priority queue
elem	element to be inserted

Definition at line 1335 of file misc.c.

References SCIP_PQueue::len, NULL, PQ_PARENT, pqueueElemChgPos(), pqueueResize(), SCIP_CALL, SCIP_OKAY, and SCIP_PQueue::slots.

Referenced by addToCandidates(), computeSteinerTreeVnoi(), conflictQueueBound(), createAndSplitProblem(), daExec(), daInit(), dualascent_execPcMw(), nodepairqueueCreate(), propagateVbounds(), SCIPbendersActivate(), solveProblem(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().

SCIPpqueueDelPos()

void SCIPpqueueDelPos	(	SCIP_PQUEUE *	pqueue,
		int	pos
	)

delete element at specified position, maintaining the heap property

Parameters

pqueue	priority queue
pos	position of element that should be deleted

Definition at line 1374 of file misc.c.

References SCIP_PQueue::len, NULL, PQ_LEFTCHILD, PQ_PARENT, PQ_RIGHTCHILD, pqueueElemChgPos(), SCIPpqueueNElems(), and SCIP_PQueue::slots.

Referenced by SCIPpqueueRemove(), and subtreeSumGapRemoveNode().

SCIPpqueueRemove()

void* SCIPpqueueRemove

(

SCIP_PQUEUE *

pqueue

)

removes and returns best element from the priority queue

Parameters

pqueue

priority queue

Definition at line 1434 of file misc.c.

References SCIP_PQueue::len, NULL, SCIPpqueueDelPos(), and SCIP_PQueue::slots.

Referenced by addToCandidates(), computeSteinerTreeVnoi(), conflictFirstCand(), conflictRemoveCand(), createSolveSubproblemIndexList(), daExec(), dualascent_execPcMw(), nodepairqueueRemove(), propagateVbounds(), SCIPStpHeurLocalExtendPcMw(), and solveProblem().

SCIPpqueueFirst()

void* SCIPpqueueFirst

(

SCIP_PQUEUE *

pqueue

)

returns the best element of the queue without removing it

Parameters

pqueue

priority queue

Definition at line 1454 of file misc.c.

References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.

Referenced by addToCandidates(), conflictFirstCand(), daExec(), nodepairqueueIsEmpty(), subtreeSumGapComputeFromScratchEfficiently(), and subtreeSumGapRemoveNode().

SCIPpqueueNElems()

int SCIPpqueueNElems

(

SCIP_PQUEUE *

pqueue

)

returns the number of elements in the queue

Parameters

pqueue

priority queue

Definition at line 1468 of file misc.c.

References SCIP_PQueue::len, and NULL.

Referenced by computeSteinerTreeVnoi(), conflictAddConflictset(), conflictAnalyze(), conflictCreateReconvergenceConss(), conflictFirstCand(), conflictRemoveCand(), conflictResolveBound(), createSolveSubproblemIndexList(), daExec(), dualascent_execPcMw(), pqueueElemChgPos(), propagateVbounds(), SCIPconflictAnalyze(), SCIPisPropagatedVbounds(), SCIPpqueueDelPos(), SCIPpqueueFind(), SCIPStpHeurLocalExtendPcMw(), solveProblem(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), subtreeSumGapStoreNode(), and updateSubproblemStatQueue().

SCIPpqueueElems()

void** SCIPpqueueElems

(

SCIP_PQUEUE *

pqueue

)

returns the elements of the queue; changing the returned array may destroy the queue's ordering!

Parameters

pqueue

priority queue

Definition at line 1479 of file misc.c.

References SCIP_PQueue::len, NULL, and SCIP_PQueue::slots.

Referenced by conflictAddConflictset(), conflictResolveBound(), subtreeSumGapDelSubtrees(), subtreeSumGapRemoveNode(), and subtreeSumGapStoreNode().

SCIPpqueueFind()

int SCIPpqueueFind	(	SCIP_PQUEUE *	pqueue,
		void *	elem
	)

return the position of elem in the priority queue, or -1 if element is not found

Parameters

pqueue	priority queue
elem	element to be inserted

Definition at line 1490 of file misc.c.

References SCIPpqueueNElems(), and SCIP_PQueue::slots.

Referenced by propagateVbounds().