//-------------------------------------------------------------------
//	recog.cpp
//
//	This program implements our polynomial-time algorithm for 
//	recognizing the score-vectors for a C-tournament of fixed 
//	order  N , defined by an upper-triangular  N-by-N  matrix 
//	of randomly generated non-negative integers bounded by B.
//
//	The algorithm begins with an initial C-tournament defined 
//	by the matrix C itself, and proceeds iteratively to alter 
//	the direction of some arcs in the tournament, regarded as 
//	a directed loopless multigraph, so as to cause its vector 
//	of row-sums to move "closer" to the given score-vector if 
//	possible -- or to terminate with a subset K of rows which 
//	violates the linear inequality corresponding to K that we 
//	identified as nesessary to the existence of C-tournaments 
//	having the prescribed score-vector.  
//
//		compile using:  $ g++ recog.cpp -o recog
//		execute using:  $ ./recog
//
//	programmer: ALLAN CRUSE
//	date begun: 15 FEB 2014
//	compledted: 17 FEB 2014
//	revised on: 21 FEB 2014
//-------------------------------------------------------------------

#include <stdio.h>		// for printf()
#include <stdlib.h>		// for random()
#include <math.h>		// for sqrt()

typedef	int	Scalar;

const int	N = 9;		// order of directed multigraph 
const int	B = 2;		// upper-bound on outdegrees
const int	INFIN = 65535;	// for uninitialized entries 

Scalar	bounds[ N ][ N ];	// defines initial C-tournament	
Scalar	partition[ N ];		//  and potential score-vector

Scalar	total;			// sum of nodes' outdegrees
Scalar	adjmat[ N ][ N ];	// current adjacency-matrix
Scalar	outdegree[ N ];		// current node outdegrees 

int	subset_hi[ N ];		// current set of HI nodes		
int	subset_lo[ N ];		// current set of LO nodes
int	subset_ok[ N ];		// current set of OK nodes

int	number_ok;		// current count of OK nodes

int	unreached[ N ];		// set of unreached nodes
int	isreached[ N ];		// set of 'reached' nodes
int	back_path[ N ];		// backward path pointers

int	hi_node, lo_node;	// node-index variables

int	iteration;		// counts algorithm steps


int main( int argc, char **argv )
{
	int	i, j, k, s, v; 
	
	// initialize the random 'seed'
	srandom( argc );

	// initialize the upper-triangular 'bounds' matrix (i.e., C)
	for (i = 0; i < N; i++) for (j = 0; j < N; j++) 
		{
		if ( i < j ) 
			bounds[ i ][ j ] = 1 + ( random() % B );	
		else	bounds[ i ][ j ] = 0;
		}

	// compute the total number of the directed arcs 
	total = 0;
	for (i = 0; i < N; i++) for (j = 0; j < N; j++)
		total += bounds[ i ][ j ];
	
	// generate a random partition of this total
	for (j = 0; j < N; j++) partition[ j ] = 0;
	for (i = 0; i < total; i++)
		{
		// uniform distribution when argc < 5
		// or skewed distributgion otherwise
		if (argc < 4 ) j = random() % N;
		else	j = sqrt( random() % (N*N) );
 		partition[ j ] += 1;
		}
	
	// initialize the C-tournament's adjacency-matric 
	for (i = 0; i < N; i++) for (j = 0; j < N; j++)
		adjmat[ i ][ j ] = bounds[ i ][ j ];

	// begin the iterative algorithm	
	iteration = 0;
again:	
	// compute current C-tournament's outdegrees
	for (i = 0; i < N; i++)
		{
		outdegree[ i ] = 0;
		for (j = 0; j < N; j++) outdegree[ i ] += adjmat[ i ][ j ];
		}

	// compute number of 'OK' nodes
	number_ok = 0;
	for (i = 0; i < N; i++) 
		if ( outdegree[ i ] == partition[ i ] ) ++number_ok;

	// display the partition, the current C-tournament and its outdegrees		
	printf( "\n\n" );
	printf( "            " );
	printf( "total = %d        ", total );
	printf( "iteration #%d     ", iteration );
	printf( "number_ok = %d \n", number_ok ); 
	printf( "\n" );
	for (i = 0; i < N; i++)
		{
		printf( "   %2d     ", partition[ i ] );
		for (j = 0; j < N; j++) printf( " %2d ", adjmat[ i ][ j ] );
		printf( "    = %2d ", outdegree[ i ] );
		if ( outdegree[ i ] < partition[ i ] ) printf( "(LO)" );
		if ( outdegree[ i ] > partition[ i ] ) printf( "(HI)" );
		if ( outdegree[ i ] == partition[ i ] ) printf( "(OK)" );
		printf( "\n" );
		}
	printf( "\n" );

	// exit if all the nodes are 'OK'
	if ( number_ok == N ) 
		{ 
		printf( "   DONE -- We have found a C-tournament " );
		printf( "that has the prescrbed score-vector. \n\n" );
		exit(1);
		}

	// compute the HI, LO, and OK subsets
	for (i = 0; i < N; i++) 
		{ 
		subset_lo[ i ] = ( outdegree[ i ] < partition[ i ] ) ? 1 : 0;
		subset_hi[ i ] = ( outdegree[ i ] > partition[ i ] ) ? 1 : 0;
		subset_ok[ i ] = ( outdegree[ i ] == partition[ i ] ) ? 1 : 0;
		}
	printf( "\n" );
	printf( "            HI nodes: " );
	for (i = 0; i < N; i++) if ( subset_hi[ i ] ) printf( " %d ", i+1 );
	printf( "            LO nodes: " );
	for (i = 0; i < N; i++) if ( subset_lo[ i ] ) printf( " %d ", i+1 );
	printf( "\n\n" );

	//---------------------------------------------------
	// allow user to pause our verbose algorithm display
	//--------------------------------------------------- 
	if ( argc > 1 ) 
		if ( *argv[1] != 'x' ) getchar();
	
	// initialize the 'unreached[]' and 'isreached[]' subsets
	for (i = 0; i < N; i++) { unreached[ i ] = 1; isreached[ i ] = 0; }
	
	// select a HI node, to be used as a directed path source	
	hi_node = -INFIN;
	for (i = 0; i < N; i++)
		if ( subset_hi[ i ] ) { hi_node = i; /*break;*/ }
	if ( hi_node < 0 ) { printf( "\nTROUBLE -- no HI node found \n\n" ); exit(1); } 
	
	s = hi_node;
	unreached[ s ] = 0;
	isreached[ s ] = 1;
	back_path[ s ] = s;

	for (i = 0; i < N; i++)
		{
		if ( isreached[ i ] ) 
			for (j = 0; j < N; j++)
				if (( unreached[ j ] )&&( adjmat[ i ][ j ] > 0 ))
					{
					unreached[ j ] = 0;
					isreached[ j ] = 1;
					back_path[ j ] = i;
					}
		}
	printf( "\n     From node %d we can reach nodes: ", s+1 );
	for (j = 0; j < N; j++) if ( isreached[ j ] ) printf( " %d ", j+1 );
	printf( "\n\n" );

	
	// select a LO node among the 'reached' nodes, if possible
	lo_node = -INFIN;
	for (j = 0; j < N; j++) 
		if ( isreached[ j ] && subset_lo[ j ] ) 	
			{
			lo_node = j;
			break;
			}
	if ( lo_node < 0 ) 
		{ 
		printf( "\n     HALT -- no reachable LO node was found! \n" ); 
		printf( "\n     --------------------------------------- \n" );

		printf( "\n   Subset of those nodes reachable from HI-node %d is  K = {", hi_node+1 );
		for (i = 0; i < N; i++) if ( isreached[ i ] ) printf( " %2d ", i+1 );  
		printf( " } \n" );

		int	subtotal = 0;
		int	rowtotal = 0;
		printf( "\n   Submatrix of the upper-triangular matrix  C  having indices in subset K : \n" );
		printf( "\n" );
		for (i = 0; i < N; i++) 
			{
			if ( !isreached[ i ] ) continue;
			printf( "     " );
			printf( "[node %d] \t", i+1 );
			for (j = 0; j < N; j++) 
				{
				if ( !isreached[ j ] ) continue;
				printf( " %2d ", bounds[ i ][ j ] );
				subtotal += bounds[ i ][ j ];
				}
			printf( "          S[%d] = %d ", i+1, partition[ i ] );
			rowtotal += partition[ i ];
			printf( "\n" );
			}
		printf( "\n" );
		printf( "   Number of arcs in this subgraph = %d, ", subtotal );
		printf( "exceeding the sum of the sequence-entries = %d ", rowtotal );
		printf( "for nodes in subset  K , \n");
		printf( "   violating an essential constraint for the existence of " );
		printf( "a C-tournament having the prescribed score-vector S. " ); 
		printf( "\n\n" );
		exit(1); 
		} 

	// Exhibit a backward path from lo_node to hi_node
	printf( "\n     Backpath: %d ", lo_node+1 );
	v = lo_node;
	while ( v != hi_node )
		{
		v = back_path[ v ];
		printf( " %d ", v+1 );
		}
	printf( "\n" );

	// Adjust the multigraph adjacencies
	printf( "\n   Adjusting multigraph adjacencies along this backward path \n" );
	v = lo_node;
	while ( v != hi_node ) 
		{
		++adjmat[ v ][ back_path[ v ] ];
		--adjmat[ back_path[ v ] ][ v ];
		v = back_path[ v ];
		}
	printf( "\n" );

	++iteration;
	goto again;
}