
//	Title:		NodeArcCon.cpp
//	Purpose:	Experiments with node-arc connectivity matrices and recording node tours.
//	Author:		Bud Fox
//	Source:		"A Book on C" (2nd ed.), by Kelley and Pohl, was used for misc. fns.
//	Date:		10-May-2009

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <time.h>

#include "NodeArcCon.h"
using namespace std;


int main(int argc, char **argv)
{
	cout << "\n main()\n";

	NodeArcConnectivity();
	
	cout << endl;
	return 0;
}

int NodeArcConnectivity(void)
{
	int i;
	int n_nodes;			// number of initial nodes in node_vec, i.e., source nodes only, NOT ALL NODES.
	int ncols;				// number of cols of node-arc matrix (number of nodes)
	int nrows;				// number of rows of node-arc matrix (number of nodes)
	int *node_vec = NULL;	// node vector that contains only the source node(s)
	int *tour_vec = NULL;	// vec that holds node-to-node tours, of size total number of nodes = ncols.
	int **A = NULL;			// nod-arc matrix

	cout << "\n NodeArcConnectivity()\n"; 

	// Get the number of rows and cols for the partic. example type.
	SetProblemDimensions(nrows, ncols);

	// MEMORY ALLOC
	node_vec = new int[ncols];	// allocate enough space for all nodes, but only emplace source nodes.
	tour_vec = new int[ncols];	// allocate enough space for all nodes, since max tour length contains all nodes
	A = new int *[nrows];
	for(i=0; i<nrows; i++)
	{
		A[i] = new int[ncols];	// allocate an array of doubles, return & to matrix[i]
	}

	// Setup data structures
	SetupConnectivityMatrix(A, nrows, ncols);
	PrintMatrix(A, nrows, ncols);

	DetermineInitialNodeVector(A, nrows, ncols, node_vec, n_nodes);
	PrintVector(node_vec, ncols);

	SetupInitialTourVector(tour_vec, ncols);
	PrintVector(tour_vec, ncols);

	// Construct node-arc tours
	BuildTour(A, nrows, ncols, node_vec, n_nodes, tour_vec);

	// MEMORY DELETE
	delete [] node_vec;
	delete [] tour_vec;
	if(A != NULL)
	{
		for(i=0; i<nrows; i++)
		{
			delete [] A[i]; 
		}
		delete [] A; 
	}

	return 0;
}

int SetProblemDimensions(int &nrows, int &ncols)
{
	int example = EXAMPLE;

	switch(example)
	{
	case 0:				// Example 0: feedback case with multiple paths
		nrows = 5;
		ncols = nrows;
		break;
	case 1:				// Example 1: feed forward case with multiple paths
		nrows = 6;
		ncols = nrows;
		break;
	case 2:				// Example 2: feedback case with multiple source nodes
		nrows = 7;
		ncols = nrows;
		break;
	case 3:				// Example 3: feedback case with multiple feedback loops
		nrows = 10;
		ncols = nrows;
		break;
	case 4:				// Example 4: feed forward case with only two blocks
		nrows = 2;
		ncols = nrows;
		break;
	case 5:				// Example 5: simple feedback loop without intervening block
		nrows = 4;
		ncols = nrows;
		break;
	case 6:				// Example 6: simple feedback loop with and without intervening block
		nrows = 5;
		ncols = nrows;
		break;
	default:
		printf("\n SetProblemDimensions(), select a feasible example number.\n");
		break;
	}
	
	return 0;
}

int SetupConnectivityMatrix(int **matrix, int nrows, int ncols)
{
	int i;
	int j;
	int example = EXAMPLE;	// example type

	cout << "\n SetupConnectivityMatrix()\n";

	// Nullify matrix
	for(i=0; i<nrows; i++)
	{
		for(j=0; j<ncols; j++)
		{
			matrix[i][j] = 0;
		}
	}

	// Assign one's (1) indicating node in row i, connected to node in col j.
	// The node numbers are represented by the row and column numbers.
	// A node is attached to itself, but for simplicity the diag elements are zero not one.

	switch(example)
	{
	case 0:	// Example 0: feedback case with multiple paths
		matrix[0][4] = 1;
		matrix[2][4] = 1;
		matrix[3][1] = 1;
		matrix[3][2] = 1;
		matrix[4][3] = 1;
		break;
	case 1:	// Example 1: feed forward case with multiple paths
		matrix[0][5] = 1;
		matrix[1][3] = 1;
		matrix[2][5] = 1;
		matrix[4][0] = 1;
		matrix[4][2] = 1;
		matrix[4][5] = 1;
		matrix[5][1] = 1;
		break;
	case 2:	// Example 2: feedback case with multiple source nodes
		matrix[0][6] = 1;
		matrix[1][3] = 1;
		matrix[3][0] = 1;
		matrix[4][6] = 1;
		matrix[5][3] = 1;
		matrix[6][2] = 1;
		matrix[6][3] = 1;
		break;
	case 3:	// Example 3: feedback case with multiple feedback loops
		matrix[1][7] = 1;
		matrix[2][0] = 1;
		matrix[2][8] = 1;
		matrix[3][6] = 1;
		matrix[3][9] = 1;
		matrix[4][7] = 1;
		matrix[5][1] = 1;
		matrix[5][2] = 1;
		matrix[6][2] = 1;
		matrix[7][5] = 1;
		matrix[8][3] = 1;
		break;
	case 4:	// Example 4: feed forward case with only two blocks
		matrix[0][1] = 1;
		break;
	case 5: // Example 5: simple feedback loop without intervening block
		matrix[0][2] = 1;
		matrix[0][3] = 1;
		matrix[1][3] = 1;
		matrix[3][0] = 1;
		break;
	case 6: // Example 6: simple feedback loop with and without intervening block
		matrix[0][2] = 1;
		matrix[0][3] = 1;
		matrix[0][4] = 1;
		matrix[1][3] = 1;
		matrix[3][0] = 1;
		matrix[4][3] = 1;
		break;
	default:
		printf("\n SetupConnectivityMatrix(), select a feasible example number.\n");
		break;
	}
	
	return 0;
}

int DetermineInitialNodeVector(int **A, int nrows, int ncols, int *node_vec, int &n_nodes)
{
	int i;
	int j;
	int offset = 0;		// node_vec offset 
	int col_sum = 0;	// sum of col elements

	printf("\n DetermineInitialNodeVector()\n");

	// A node on row i, is connected to a node on col j. 
	// So if there is a col of zeros, then that col number represents a source node,
	// since no node is connected to it in the forward-direction sense.

	// Assign initial negative values 
	for(i=0; i<ncols; i++)
	{
		node_vec[i] = -1;
	}

	// Iterate across the cols and down the rows
	for(j=0; j<ncols; j++)
	{
		col_sum = 0;
		for(i=0; i<nrows; i++)
		{
			col_sum = col_sum + A[i][j];	// col sum

		}
		if(col_sum == 0)					
		{
			node_vec[offset] = j;	// place source node in node_vec
			offset++;
		}
	}

	// Assign the number of source nodes in the node_vec
	n_nodes = offset;

	// Return a flag indicating whether a row of zeros was found
	if(offset == 0)
	{
		return -1;	// error since no col of zeros, and hence no initial source node
	}
	else
	{
		return 0;	// a col of zeros was found, hence there exists a source node
	}
}

int SetupInitialTourVector(int *tour_vec, int ncols)
{
	int i;

	printf("\n SetupInitialTourVector()\n");

	// Assign unique initial negative values to the node entries of the tour vec indicating no tour
	for(i=0; i<ncols; i++)
	{
		tour_vec[i] = -(i+1);
	}

	return 0;
}

int BuildTour(int **A, int nrows, int ncols, int *node_vec, int n_nodes, int *in_tour_vec)
{
	int i;
	int j;
	int posn;					// posn of nodes in tour vector
	int n_branch_nodes;			// number of branch nodes present on a partic. row
	int node;					// node number = row number = col number
	int tour_end = 0;			// flag identifying whether current tour has been found
	int *branch_node_vec = NULL;// vec of branch nodes to which current node can progress
	int *tour_vec = NULL;		// vec of nodes comprising the tour
	time_t seconds;				// time var used to aid user when pressing return bw. iterations of for-node loop
	char t_string[20];			// time string

	cout <<"\n -- BuildTour()\n";

	// -- MEMORY ALLOC
	tour_vec = new int[ncols];

	// Copy the incoming tour vec into the local tour vec
	for(j=0; j<ncols; j++)
	{	
		tour_vec[j] = in_tour_vec[j];
	}
	
	printf("\n tour_vec:\n");
	PrintVector(tour_vec, ncols);

	printf("\n node_vec:\n");
	PrintVector(node_vec, ncols);


	// -- ITERATE OVER ONLY THE NODES IN THE NODE VECTOR FROM WHICH CONNECTIONS TO OTHER NODES ARE PREMISSABLE
	for(node=0; node<n_nodes; node++)
	{
		// Get the offset position in the tour vector into which the next node should be placed
		posn = FindCurrentTourPosition(in_tour_vec, ncols);
		printf("\n For node = %d < %d, posn = %d\n", node, n_nodes, posn);

		// Get starting node, i.e. a node in the node vector (of source nodes or branch nodes)
		i = node_vec[node];
		tour_vec[posn] = i;
		tour_end = 0;

		printf("\n Prior to while(), tour_end = %d, i = node_vec[%d] = %d, tour_vec:\n", tour_end, node, i);
		PrintVector(tour_vec, ncols);

		// Check for repeated entries here, after the new node addition to the tour_vec: if there is a repeat, end tour.
		if(CheckRepeatedEntries(tour_vec, ncols) > 0)
		{
			tour_end = 1;
			printf("\n repeated entries, tour_end = %d\n", tour_end);

			SaveTourVector(tour_vec, ncols);	// save tour_vec since tour has had an entry added but a loop exists
		}

		// -- WHILE TOUR NOT COMPLETE
		while(tour_end == 0)
		{
			// Get the offset position in the EVOLVING TOUR VECTOR into which the next node should be placed
			posn = FindCurrentTourPosition(tour_vec, ncols);
			printf("\n Inside while, before if, posn = %d, ncols = %d\n", posn, ncols);

			if(posn >= ncols)	// if the posn is after the end of the array, then the tour vector is filled.
			{
				tour_end = 1;
				SaveTourVector(tour_vec, ncols);	// save tour_vec since tour has ended due to no further connections
				break;			// break from while loop
			}

			// Find the number of connections i.e. branch nodes to the current node
			n_branch_nodes = NumberOfOnes(A, i, ncols);

			// If there are no 1's in the cols then there are no connecting nodes
			if(n_branch_nodes == 0)	
			{
				printf("\n n_branch_nodes = %d\n", n_branch_nodes);
				
				tour_vec[posn] = -1;				// -1 indicates no fwd connection exists from the current node
				tour_end = 1;						// end tour
				SaveTourVector(tour_vec, ncols);	// save tour_vec since tour has ended due to no further connections
			}
			// If there is one 1, in the cols, there there is one connecting node
			else if(n_branch_nodes == 1)	
			{
				printf("\n n_branch_nodes = %d\n", n_branch_nodes);

				for(j=0; j<ncols; j++)			// iterate over cols
				{
					if(A[i][j] == 1)			// if a col contains a 1, then, node on row i, is connected to node in col j.
					{
						tour_vec[posn] = j;		// new node traversed is that in col j, connected to that in row i
						i = j;					// update row i with col j to continue to the next connection
						break;			// break from for loop
					}	
				}
			
				printf("\n tour_vec:\n");
				PrintVector(tour_vec, ncols);
			}
			// If there is > one 1, in the cols, then there is > 1 connecting node
			else if(n_branch_nodes > 1)
			{
				// MEMORY ALLOC
				branch_node_vec = new int[ncols];

				// Find all nodes that are connected/branched to the current node
				FindBranchNodes(A, i, ncols, branch_node_vec, n_branch_nodes);
				
				printf("\n n_branch_nodes = %d, branch_node_vec:\n", n_branch_nodes);
				PrintVector(branch_node_vec, ncols);	
		
				// RECURSIVELY CALL THE BuildTour() FUNCTION WITH THE NEW NODE VECTOR AND TOUR VECTOR
				BuildTour(A, nrows, ncols, branch_node_vec, n_branch_nodes, tour_vec);
				
				printf("\n After recursive BuildTour() call\n");
	
				tour_end = 1;
	
				// MEMORY DELETE
				delete [] branch_node_vec;	
			}

			// Check for repeated entries here, after the if-else-based node addition to the tour_vec.
			if(CheckRepeatedEntries(tour_vec, ncols) > 0)
			{
				tour_end = 1;
				printf("\n repeated entries, tour_end = %d\n", tour_end);

				SaveTourVector(tour_vec, ncols);	// save tour_vec since tour has had an entry added but a loop exists
			}

			// Reset the tour_vec to be that of the incoming tour vector
			if(tour_end == 1)
			{
				ResetTourVector(tour_vec, in_tour_vec, ncols);
			}
		}// end while

		// Get the time of the end of this loop
		seconds = time(NULL);										// get seconds ellapsed since 1-1-1970
		strftime(t_string, 20, "%H:%M:%S", localtime(&seconds));	// get the local time as a string
		printf("\n ---------- End of for node = %d \t\t\t   time: %s\n", node, t_string);
		//printf("\n time: %s\n", t_string);
		//printf("\n Press return to continue ... \t\t\t\t time: %s\n", t_string);
		printf("\n Press return to continue ... \n");
		getchar();

	}// end for


	// MEMORY DELETE
	delete [] tour_vec;

	return 0;
}

int FindCurrentTourPosition(int *tour_vec, int ncols)
{
	int i;

	//printf("\n FindCurrentTourPosition()\n");

	// Iterate through the vector to find the first negative, non-node-filled, entry.
	for(i=0; i<ncols; i++)
	{
		if(tour_vec[i] < 0)
		{
			return i;
		}
	}

	// If no -ve value found then return the size of the array "ncols"
	return ncols;
}

int FindBranchNodes(int **A, int i, int ncols, int *branch_node_vec, int &n_branch_nodes)
{
	int j;			// col index
	int cnt = 0;	// branch_node_vec[] offset index

	//printf("\n FindBranchNodes()\n");

	// Negate the branch_node_vec
	for(j=0; j<ncols; j++)
	{
		branch_node_vec[j] = -1;
	}

	// Iterate over the cols of A for the current row (i), recording those with one's (1), indicating node connections.
	for(j=0; j<ncols; j++)
	{
		if(A[i][j] == 1)
		{
			branch_node_vec[cnt] = j;
			cnt++;
		}
	}
	n_branch_nodes = cnt;		// update the number of connecting/branch nodes

	return 0;
}

int NumberOfOnes(int **A, int row, int ncols)
{
	int j;
	int n_ones = 0;

	//printf("\n NumberOfOnes()\n");

	// Count the number of ones on the partic. row.
	for(j=0; j<ncols; j++)
	{
		if(A[row][j] == 1)
		{
			n_ones++;
		}
	}

	//printf("\n n_ones = %d\n", n_ones);

	return n_ones;
}

int CheckRepeatedEntries(int *tour, int ncols)
{	
	int i;
	int j;
	int n_repeats = 0;

	//printf("\n CheckRepeatedEntries()\n");

	// Check tour vector for repeated entries (implying a loop)
	for(i=0; i<(ncols-1); i++)
	{
		for(j=(i+1); j<ncols; j++)
		{
			if(tour[j] == tour[i])
			{
				n_repeats++;
			}
		}
	}

	//printf("\n n_repeats = %d\n", n_repeats);

	return n_repeats;
}

void ResetTourVector(int *tour_vec, int *in_tour_vec, int ncols)
{
	int j;

	// Reassign in_tour_vec to tour_vec
	for(j=0; j<ncols; j++)
	{
		tour_vec[j] = in_tour_vec[j];
	}
}

void SaveTourVector(int *tour_vec, int ncols)
{		
	int n_repeats = 0;			// number of repeated entries
	static int n_loops = 0;		// number of tours with feedback loops
	static int n_tours = 0;		// number of tours
	
	printf("\n -> SaveTourVector(),");

	// WARNING! This fn should save all tours, but doesn't here since nothing is done with them.
	// This could be performed in the following ways:
	// 1) Run NodeArcConnectivity() to determine the exact n_tours, then allocate enough memory, the rerun to obtain the tours.
	// 2) Run NodeArcConnectivity() and simply add each tour to a growing static int 2-D array that is large enough.

	// Record the number of unique tours
	n_tours++;
	printf(" n_tours = %d,", n_tours);
	
	//printf("\n CheckRepeatedEntries()\n");

	// Check tour vector for repeated entries (implying a node-to-node loop)
	n_repeats = CheckRepeatedEntries(tour_vec, ncols);

	// Notify method of tour termination
	if(n_repeats == 0)
	{
		printf(" tour_vec that would be saved (output block):\n");
	}
	else if(n_repeats > 0)
	{
		n_loops++;	// record the number of tours with feedback loops
		printf(" tour_vec that would be saved (loop)\n");
		
	}

	PrintVector(tour_vec, ncols);

	return;
}

// -- PRINTING FNS		

int PrintMatrix(int **M, int nrows, int ncols)
{
	int	i;
	int	j;

	cout << "\n PrintMatrix()\n";

	// If the matrix is NULL then return.
	if(M == NULL)
	{
		return 1;
	}

	// Print Matrix
	cout << endl;
	for(i=0; i<nrows; i++)
	{
		for(j=0; j<ncols; j++)
		{
			printf(" %d", M[i][j]);
		}
		cout << endl;
	}
	cout << endl;

	return 0;
}

int PrintVector(int *v, int ncols)
{
	int	i;
	
	//cout << "\n PrintVector()\n";

	// If the vector is NULL then return.
	if(v == NULL)
	{
		return 1;
	}

	// Print Vector
	printf("\n");
	for(i=0; i<ncols; i++)
	{
		printf(" %d", v[i]);
	}
	printf("\n\n");

	return 0;
}

//eof