/**************************** vheap.c ********************************** Purpose: Implement a "virtual heap": a combination of stacks and a heap. Provenance: Written and tested by Q. Chen and E. Fox, March 1991. Edited and tested by S. Wartik, April 1991. Revised and tested by S. Wartik, July 1991. Notes: The point of the combination is that a stack is a more efficient data structure. Vertices of low degree (specifically, those <= NO_STACKS) are stored in stacks, since they are more common. Vertices of high degree are stored in the heap. **/ #include #include /* The following aims to define INT_MAX as the maximum value of * type "int" for the hardware on which the program is being compiled. */ #ifdef __STDC__ #include #else /* According to a comment in the file "values.h" on a Sun-4 (which * unfortunately isn't widely available), the following works on any * binary representation where the high-order bit contains the sign. */ # ifndef INT_MAX # if gcos # define BITSPERBYTE 9 # else # define BITSPERBYTE 8 # endif # define BITS(type) (BITSPERBYTE * (int)sizeof(type)) # define HIBITI (1 << BITS(int) - 1) # define INT_MAX (~HIBITI) # endif #endif #include "types.h" #include "support.h" #include "vheap.h" #define NO_STACKS 6 /* The number of stacks in use. */ #define DEF_SIZE 10 /* The default size of a heap or a stack. */ typedef struct { /* Stack data structure. */ int stackTop, /* Stack top. */ stackSize; /* Allocated stack area size. */ vertexType **stackRep; /* Stack area. */ } stackType; typedef struct { /* Heap cell data structure. */ int degree; /* Key field, containing vertex's degree. */ vertexType *vertex; /* Info field, holding vertex's address. */ } heapCell; typedef struct { /* Heap data structure. */ int heapTop, /* Heap top. */ heapSize; /* Allocated heap area size. */ heapCell *heapRep; /* Heap area. */ } heapType; stackType stacks[NO_STACKS]; /* The stacks of the virtual heap. */ heapType heap; /* The heap portion. */ #ifdef __STDC__ extern void push( stackType *stack, vertexType *vertex ); extern int pop( stackType *stack, vertexType **vertex ); extern void enter_heap( int degree, vertexType *vertex ); extern int remove_from_heap( vertexType **vertex ); #else extern void push(); extern int pop(); extern void enter_heap(); extern int remove_from_heap(); #endif /*********************************************************************** add_to_vheap( vertex, degree ) Return: void Purpose: Add a vertex of a specified degree to the virtual heap. **/ void add_to_vheap( vertex, degree ) vertexType *vertex; /* in: a vertex to be added. */ int degree; /* in: the vertex's degree. */ { if ( degree > NO_STACKS ) enter_heap( degree, vertex ); else push( &stacks[degree-1], vertex ); } /************************************************************************* max_degree_vertex( vertex ) Return: int -- NORM if a vertex could be found, ABNORM if the virtual heap (stacks and heap) is empty. Purpose: Find the unvisited vertex with maximal degree from the virtual heap. Place it in "vertex". Plan: First check the heap; remove_from_heap() automatically removes a vertex of maximal degree. If the heap is empty, try the stacks, one at a time. **/ int max_degree_vertex( vertex ) vertexType **vertex; /* out: the vertex found. */ { int i; if ( remove_from_heap( vertex ) == NORM ) /* heap empty? */ return(NORM); for( i = NO_STACKS - 1; i >= 0; i-- ) /* stacks empty? */ if ( pop( &stacks[i], vertex ) == NORM ) return (NORM); return(ABNORM); /* No node at all. The component has been processed. */ } /************************************************************************* push(stack, vertex ) Return: void Purpose: Push a vertex pointer onto a stack. **/ static void push(stack, vertex) stackType *stack; /* in out: the stack. */ vertexType *vertex; /* in: the vertex. */ { stack->stackTop++; /* Expand stack if it doesn't have enough space. */ if ( stack->stackTop >= stack->stackSize ) { fprintf(stderr, "Warning: stack overflow. Re-allocating.\n"); stack->stackSize *= 2; stack->stackRep = (vertexType**)ownrealloc( (char *)stack->stackRep, sizeof(vertexType*) * stack->stackSize ); } stack->stackRep[stack->stackTop] = vertex; } /************************************************************************* pop( stack, vertex ) Return: int -- Index of a vertex. Purpose: Pop up a vertex pointer from the stack. Return -1 if the stack was empty, 0 if it wasn't. **/ static int pop( stack, vertex ) stackType *stack; vertexType **vertex; { if ( stack->stackTop == -1 ) return(-1); /* stack empty */ *vertex = stack->stackRep[stack->stackTop--]; return(0); /* stack not empty */ } /************************************************************************* enter_heap( degree, vertex ) Return: void Purpose: Insert a vertex pointer and its degree into the heap. **/ static void enter_heap( degree, vertex ) int degree; /* in: the degree of the node. */ vertexType *vertex; /* in: the vertex pointer. */ { int k = heap.heapTop++ ; if ( k >= heap.heapSize ) { heap.heapSize = 2 * heap.heapSize; heap.heapRep = (heapCell*)ownrealloc( (char *)heap.heapRep, sizeof(heapCell) * heap.heapSize ); } heap.heapRep[k].degree = degree; heap.heapRep[k].vertex = vertex; while ( heap.heapRep[k/2].degree <= degree ) { heap.heapRep[k].degree = heap.heapRep[k/2].degree; heap.heapRep[k].vertex = heap.heapRep[k/2].vertex; k /= 2; } heap.heapRep[k].degree = degree; heap.heapRep[k].vertex = vertex; } /************************************************************************* remove_from_heap( vertex ) Return: int -- -1 if the heap is empty when the routine is called, 0 if it isn't. Purpose: Remove a vertex of maximal degree from the heap, and return it. **/ static int remove_from_heap( vertex ) vertexType **vertex; /* out: the vertex selected. */ { int k, j; /* Iterators through the heap. */ heapCell tempCell; /* Heap element currently being examined. */ if ( heap.heapTop == 1 ) return(-1); *vertex = heap.heapRep[1].vertex; heap.heapTop--; tempCell.degree = heap.heapRep[1].degree= heap.heapRep[heap.heapTop].degree; tempCell.vertex = heap.heapRep[1].vertex = heap.heapRep[heap.heapTop].vertex; k = 1; /* Go down the heap. */ while ( k <= heap.heapTop / 2 ) { j = 2 * k; if ( (j < heap.heapTop ) && (heap.heapRep[j].degree< heap.heapRep[j+1].degree) ) j++; if ( tempCell.degree > heap.heapRep[j].degree ) break; heap.heapRep[k].degree = heap.heapRep[j].degree; heap.heapRep[k].vertex = heap.heapRep[j].vertex; k = j; } /* end of while */ heap.heapRep[k].degree = tempCell.degree; heap.heapRep[k].vertex = tempCell.vertex; return(0); } /************************************************************************* initialize_vheap() Return: void Purpose: Set the heap and stacks to their empty states. **/ void initialize_vheap() { int i; heap.heapRep[0].degree = INT_MAX; heap.heapTop = 1; for ( i = 1; i < heap.heapSize; i++ ) { heap.heapRep[i].degree = 0; heap.heapRep[i].vertex = 0; } for ( i = 0; i < NO_STACKS; stacks[i++].stackTop = -1 ); } /************************************************************************* free_vheap() Return: void Purpose: Deallocate space for stacks and heap. **/ void free_vheap() { int i; for ( i = 0; i < NO_STACKS; free((char *)stacks[i++].stackRep) ); free( (char *)heap.heapRep ); } /************************************************************************* allocate_vheap( no_arcs, no_vertices ) Return: void Purpose: Estimate and allocate space for the heap and the stacks. **/ void allocate_vheap( no_arcs, no_vertices ) int no_arcs, /* in: number of arcs. */ no_vertices; /* in: number of vertices. */ { int i, /* iteration variable. */ sum = 0; /* partial sum of degree. */ double lambda, /* lambda = |E| / ( |V| / 2 ) */ Pr0, /* Pr0 = Pr(X = 0) */ Pri; /* Pri = Pr(X = i) */ lambda = (double)(2*no_arcs) / (double)no_vertices; Pr0 = Pri = exp(-lambda); /* Compute Pr(x = 0). */ for ( i = 1; i <= NO_STACKS; i++ ) { /* Compute the expected number */ Pri *= lambda/(double)(i); /* of nodes of degree 1, 2, ..., */ /* NO_STACKS. */ stacks[i-1].stackSize = (int) 2 * no_vertices * Pri; sum += stacks[i-1].stackSize ; } for ( i = 0; i < NO_STACKS; i++ ) { /* Allocate stack space. */ if ( stacks[i].stackSize <= 0 ) stacks[i].stackSize = DEF_SIZE; stacks[i].stackRep = (vertexType**) owncalloc( stacks[i].stackSize, sizeof(vertexType*) ); } heap.heapSize = no_vertices - sum - (int) 2 * no_vertices * Pr0; if ( heap.heapSize <= 0 ) heap.heapSize = DEF_SIZE; heap.heapRep = /* Allocate heap space. */ (heapCell*) owncalloc( heap.heapSize, sizeof(heapCell) ); }