Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

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

Functions

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

Function Documentation

◆ SCIPpqueueCreate()

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

creates priority queue

Parameters
pqueuepointer to a priority queue
initsizeinitial number of available element slots
sizefacmemory 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 initData(), initProblem(), nodepairqueueCreate(), SCIPbendersActivate(), SCIPconflictCreate(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurTMRun(), and subtreeSumGapStoreNode().

◆ SCIPpqueueFree()

SCIP_EXPORT void SCIPpqueueFree ( SCIP_PQUEUE **  pqueue)

frees priority queue, but not the data elements themselves

Parameters
pqueuepointer to a priority queue

Definition at line 1263 of file misc.c.

References BMSfreeMemory, BMSfreeMemoryArray, and NULL.

Referenced by freeProblem(), nodepairqueueFree(), SCIPbendersDeactivate(), SCIPconflictFree(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurTMRun(), and subtreeSumGapDelSubtrees().

◆ SCIPpqueueClear()

SCIP_EXPORT void SCIPpqueueClear ( SCIP_PQUEUE pqueue)

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

Parameters
pqueuepriority queue

Definition at line 1274 of file misc.c.

References SCIP_PQueue::len, and NULL.

Referenced by conflictClear().

◆ SCIPpqueueInsert()

◆ SCIPpqueueDelPos()

SCIP_EXPORT void SCIPpqueueDelPos ( SCIP_PQUEUE pqueue,
int  pos 
)

delete element at specified position, maintaining the heap property

Parameters
pqueuepriority queue
posposition 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()

SCIP_EXPORT void* SCIPpqueueRemove ( SCIP_PQUEUE pqueue)

◆ SCIPpqueueFirst()

SCIP_EXPORT void* SCIPpqueueFirst ( SCIP_PQUEUE pqueue)

returns the best element of the queue without removing it

Parameters
pqueuepriority queue

Definition at line 1454 of file misc.c.

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

Referenced by conflictFirstCand(), nodepairqueueIsEmpty(), SCIPStpDualAscent(), SCIPStpHeurLocalExtendPcMw(), subtreeSumGapComputeFromScratchEfficiently(), and subtreeSumGapRemoveNode().

◆ SCIPpqueueNElems()

◆ SCIPpqueueElems()

SCIP_EXPORT void** SCIPpqueueElems ( SCIP_PQUEUE pqueue)

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

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

SCIP_EXPORT int SCIPpqueueFind ( SCIP_PQUEUE pqueue,
void *  elem 
)

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

Parameters
pqueuepriority queue
elemelement to be inserted

Definition at line 1490 of file misc.c.

References SCIPpqueueNElems(), and SCIP_PQueue::slots.

Referenced by propagateVbounds().