/******************************  order.c  ************************************

   Purpose:	Implement the ordering stage of the MPHF algorithm.

   Provenance:	Written and tested by Q. Chen and E. Fox, March 1991.
   		Edited and tested by S. Wartik, April 1991.

   Notes:	None.
**/

#include <stdio.h>

#include "types.h"
#include "support.h"
#include "vheap.h"

#ifdef __STDC__

extern void	delete_from_rList( vertexType *vertex, verticesType *vertices );
extern void	append_to_VS( vertexType *vertex, verticesType *vertices );
extern void	initialize_rList( verticesType *vertices );

#else

extern void	delete_from_rList();
extern void	append_to_VS();
extern void	initialize_rList();

#endif

/*************************************************************************

	ordering( arcs, vertices )

  Return:	void

  Purpose:	Generate an ordering of the vertices.

  Notes:	The ordering of the vertices is a linked list, the head
  		of which is in vertices->vsList.  The "next element"
		pointer for each node is in the "succ" field of each
		vertex component.  Note that the "succ" field has two
		purposes in this step.  One is that just mentioned.  The
		other is to be part of the rList used in this step.
**/

void ordering( arcs, vertices )
    arcsType		*arcs;     /* in out: the arcs data structure.     */
    verticesType	*vertices; /* in out: the vertices data structure. */
{
    int		degree,
		side;                /* Indicates side of graph.	*/

    vertexType	*vertex;
    arcType	*arc;

    vertices->vsHead = vertices->vsTail = NP;	/* Initialize the VS list. */

    initialize_rList( vertices );
    allocate_vheap( arcs->no_arcs, vertices->no_vertices );

    while ( vertices->rlistHead != -1 ) {	/* Process each component graph. */
	initialize_vheap();
	vertex = &vertices->vertexArray[vertices->rlistHead];
	do {
	    vertex->g = 0;                          /* Mark node "visited".  */
	    delete_from_rList( vertex, vertices );
	    append_to_VS( vertex, vertices );
	    if ( vertex->first_edge != 0 ) {
		/* Add adjacent nodes that are not visited and  */
		/* not in virtual heap to the virtual heap.	*/

		side = vertex - vertices->vertexArray >= vertices->no_vertices/2;

		arc = vertex->first_edge;
		while ( arc != 0 ) {
		    int	    adj_node;	/* Node adjacent to vertex. */

		    adj_node = arc->h12[(side+1)%2];
		    degree = vertices->vertexArray[adj_node].g;

		    if ( degree > 0 ) {            /* One such node is found. */
			add_to_vheap( &vertices->vertexArray[adj_node], degree );
			vertices->vertexArray[adj_node].g *= -1;
		    }
		    arc = arc->next_edge[side];
		}
	    }
	} while ( max_degree_vertex( &vertex ) == NORM );
    }
    free_vheap();
}


/*************************************************************************

	delete_from_rList( vertex, vertices )

  Return:	void

  Purpose:	Delete a vertex pointing at by vertex from the rList stored
		in the vertices data structure.
**/

void delete_from_rList( vertex, vertices )
   vertexType	*vertex;    	/* in: vertex to delete.  	 */
   verticesType *vertices;     	/* out: vertices data structure. */
{
    if ( vertex->prec != NP )
	vertices->vertexArray[vertex->prec].succ = vertex->succ;
    else
	vertices->rlistHead = vertex->succ;

    if ( vertex->succ != NP )
	vertices->vertexArray[vertex->succ].prec = vertex->prec;
}


/*************************************************************************

	append_to_VS( vertex, vertices )

  Return:	void

  Purpose:	Append the vertex to the vertex ordering VS.
**/

void append_to_VS( vertex, vertices )
    vertexType	 *vertex;   	/* in: the vertex to be added.       */
    verticesType *vertices;    	/* out: the vertices data structure. */
{
    int newTail = vertex - vertices->vertexArray;

    vertex->succ = vertex->prec = NP;
    if ( vertices->vsHead == NP )
	vertices->vsHead = newTail;
    else
	vertices->vertexArray[vertices->vsTail].succ = newTail;
    vertices->vsTail = newTail;
}


/*************************************************************************

	initialize_rList( vertices )

  Return:	void

  Purpose:	Set up an rList from the vertices.  An rList is a
		doubly-linked list of vertices in decending order of
		degree.

  Notes:	pred and succ are used to store the list.		
**/

void initialize_rList( vertices )
    verticesType *vertices;	/* in out: vertices to be ordered.	*/
{
    int		i, j, previous;
    intSetType	heads,	/* Two sets of pointers. Element i of "heads" points at	*/
		tails;	/* the head of a list about degree i, 0<=i<=maxDegree.	*/
    			/* The elements of "tails" are the corresponding tails.	*/

    heads.count = vertices->maxDegree + 1;
    heads.intSetRep = (int*)owncalloc( heads.count, sizeof(int) );
    for ( i = 0; i < heads.count; i++ )
	heads.intSetRep[i] = NP;

    tails.count = vertices->maxDegree + 1;
    tails.intSetRep = (int*) owncalloc( tails.count, sizeof(int) );
    for ( i = 0; i < tails.count; i++ )
	tails.intSetRep[i] = NP;

		      /* Construct lists for vertices being of */
		      /* degree 0, 1, ... maxDegree.           */
    for ( i = 0; i < vertices->no_vertices; i++ ) {
	previous = heads.intSetRep[vertices->vertexArray[i].g];
	vertices->vertexArray[i].succ =  previous;
	if ( previous != NP )
	    vertices->vertexArray[previous].prec = i;
	else
	    tails.intSetRep[vertices->vertexArray[i].g] = i;
	heads.intSetRep[vertices->vertexArray[i].g] = i;
	vertices->vertexArray[i].prec = NP;
    }

	/* Construct the rList by linking lists for vertices being of  */
	/* degree 0, 1, ... maxDegree. 				       */
    for ( i = heads.count - 1; i > 1; i-- )
	if ( tails.intSetRep[i] != NP ) {
	    for ( j = i - 1; j >= 1; j-- )
		if ( heads.intSetRep[j] != NP )
		    break;
		if ( j >= 1 ) {
		    vertices->vertexArray[tails.intSetRep[i]].succ =
			    heads.intSetRep[j];
		    vertices->vertexArray[heads.intSetRep[j]].prec =
			    tails.intSetRep[i];
		}
	}
    vertices->rlistHead = heads.intSetRep[vertices-> maxDegree];

    free( (char *)heads.intSetRep );
    free( (char *)tails.intSetRep );
}