#include "geo.h"
#define DEBUG
extern FILE *fpo ;

void bellman(void)
{

int i , j , D , distance ;
WCPTR ptr ;

xBellArray = (BELLBOXPTR) malloc((1 + numXnodes) * sizeof(BELLBOX));
yBellArray = (BELLBOXPTR) malloc((1 + numYnodes) * sizeof(BELLBOX));

xBellArray[1].from     = 0 ;
xBellArray[1].distance = 0 ;
for( i = 2 ; i <= numXnodes ; i++ ) {
    xBellArray[i].distance = VBIG ;
}

for( i = 1 ; i <= numXnodes ; i++ ) {
    D = xBellArray[i].distance ;
    for( ptr = xNodeArray[i]; ptr != (WCPTR) NULL ; ptr = ptr->next ){
	j = ptr->node ;
	distance = - (ptr->length) ;
	if( xBellArray[j].distance > D + distance ) {
	    xBellArray[j].distance = D + distance ;
	    xBellArray[j].from = i ;
	}
    }
}

yBellArray[1].from     = 0 ;
yBellArray[1].distance = 0 ;
for( i = 2 ; i <= numYnodes ; i++ ) {
    yBellArray[i].distance = VBIG ;
}

for( i = 1 ; i <= numYnodes ; i++ ) {
    D = yBellArray[i].distance ;
    for( ptr = yNodeArray[i]; ptr != (WCPTR) NULL ; ptr = ptr->next ){
	j = ptr->node ;
	distance = - (ptr->length) ;
	if( yBellArray[j].distance > D + distance ) {
	    yBellArray[j].distance = D + distance ;
	    yBellArray[j].from = i ;
	}
    }
}
#ifdef DEBUG
fprintf(fpo,"Longest Hori. Path in Circuit Graph has span: <%d>\n",
			    - xBellArray[numXnodes].distance ) ;
fprintf(fpo,"Longest Vert. Path in Circuit Graph has span: <%d>\n",
			    - yBellArray[numYnodes].distance ) ;
#endif

return ;
}