/* Author: Joshua Madden, with assistance from Kevin Hare.
Written during the PIms Mathematical Modelling Workshop, SFU, May 1998.
This code may be distributed without let or hindrance, provided that 
this comment is included.  No warranty is made for the correctness or
reliability of this code (although it works as far as I am aware), nor
for its suitability for any particular purpose other than calculating
approximations to obscure properties of graphs.  I also do not guarantee
that this code, if placed on your computer, will not foment revolution
among your word processing files and cause them to overthrow your operating
system, tease your cat, make fun of what you look like in the morning, 
let the air out of your tires, or drop 16-ton (English or metric) weights
on your head just to hear the crash.  Use it at your own risk. */

/* Input file format: 
<number of nodes in graph>
<weight of each node>
<(weighted) adjacency matrix> 

Each element of the file should be separated by whitespace from other file
elements; other than that, there are no formatting restrictions other than
order.  The adjacency matrix can be weighted, but this program does nothing
with those weights other than check to see whether they are zero or nonzero; 
it is only concerned with the weights on the nodes. */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct st_node
{
    int duration, start, end, degree, conflicts;
} node;

int read_graph(FILE *infile, int *N, int ***A, node **nodes);
int greedy1(int n, node *nodes, int **A);
int select_node_1(int n, node *nodes);
int select_node_2(int n, node *nodes);

/*******************************************************************
 * main()
 *******************************************************************/
int main(int argc, char **argv)
{
    int n, **A;
    node *nodes;
    FILE *infile;
    int i, j, success;
    
    /* n is the number of vertices in the graph, A is the (weighted)
       adjacency matrix, nodes holds duration, degree, and "location"
       (explained later) information for each node */
    
    if (argc != 2)
    {
	printf("Usage: traffic <infile>\n");
	return 1;
    }
    
    infile = fopen(argv[1], "r");
    if (!infile)
    {
	printf("File %s does not exist: exiting\n", argv[1]);
	return 2;
    }
    
    success = read_graph(infile, &n, &A, &nodes);
    if (!success)
    {
	printf("Failed to properly read graph from file %s: exiting\n", 
	       argv[1]);
	fclose(infile);
	return 3;
    }
    
    /* display graph data: number of vertices, node data (duration, degree), 
       adjacency matrix */

    /*    
    printf("Number of vertices: %d\n", n);
    for (i=0; i<n; i++)
	printf("node %d: duration %d, degree %d\n", i, nodes[i].duration, 
	       nodes[i].degree);
    printf("Adjacency matrix:\n");
    for (i=0; i<n; i++)
    {
	for (j=0; j<n; j++)
	    printf("%d  ", A[i][j]);
	printf("\n");
    }
    */
  
    /* run heuristic algorithm on graph */
    success = greedy1(n, nodes, A);
    if (!success)
    {
	printf("greedy1 returned failure\n");
	fclose(infile);
	return 4;
    }
    else
    {
	for (i=0; i<n; i++)
	    printf("node %d: start %d, duration %d, end %d\n", i, 
		   nodes[i].start, nodes[i].duration, nodes[i].end);
	printf("total cycle duration: %d\n", success);
    }
    
    fclose(infile);
    return 0;
}  

/*******************************************************************
 * read_graph()
 *******************************************************************/
int read_graph(FILE *infile, int *N, int ***A, node **nodes)
{
    int i, j, n, scanret;
    int **a;
    node *narray;
    
    scanret = fscanf(infile, "%d", N);
    if ((scanret == EOF) || ((*N) < 1)) 
	return 0;
    n = *N;
    
    *A = (int **) calloc(n, sizeof(int *));
    if (!(*A))
	return 0;
    a = *A;
    for (i=0; i<n; i++)
    {
      a[i] = (int *) calloc(n, sizeof(int));
      if (!a[i])
	  return 0;
    }
    
    *nodes = (node *) calloc(n, sizeof(node));
    if (!nodes)
	return 0;
    narray = *nodes;
    
    /* read in node durations, set starting times to INT_MAX, 
       conflicts to 0 */
    for (i=0; i<n; i++)
    {
	scanret = fscanf(infile, "%d", &(narray[i].duration));
	if (scanret == EOF)
	    return 0;
	narray[i].start = INT_MAX;
	narray[i].conflicts = 0;
	narray[i].end = INT_MAX;
    }
    
    /* read in adjacency matrix */
    for (i=0; i<n; i++)
	for (j=0; j<n; j++)
	{
	    scanret = fscanf(infile, "%d", &(a[i][j]));
	    if (scanret == EOF)
		return 0;
	}
    
    /* calculate degree of each node: find # of nonzero entries in each row */
    for (i=0; i<n; i++)
	for (j=0; j<n; j++)
	    narray[i].degree += (a[i][j] != 0);
    
    return n;
}

/*******************************************************************
 * greedy1()
 *
 * Calculates, using the greedy algorithm described below, an
 * ordering (hopefully efficient) of the nodes as portions of a cycle.
 * The nodes[] array, when the function returns, holds (among other
 * things) the starting and ending positions for each node-arc.
 * The function returns the total length of the cycle, or 0 on error.
 *******************************************************************/
int greedy1(int n, node *nodes, int **A)
{
    int i, j, k, m, conf_start, end, curr, inserted, conflicts;
    int *ends;
    
  /* 
     The basic idea of this heuristic is to pick the "most problematic"
     vertex to add to the partial solution at all times.  This is
     defined as follows:
     0) pick vertex with a) largest duration and b) highest degree (to 
     start off on)

     The heuristic for selecting subsequent nodes is specified in the 
     select_node_X() function called, and is documented there.

     Once you've picked your vertex (node), it then has to be placed
     in the "circle".  We want to do this in such a way as to (greedily) 
     minimize the circle's circumference.  Thus, we place the start
     of the node's segment (whose length is the duration of the node) as 
     close to zero as possible (where "zero" is defined as being the
     starting point of the first segment placed).  (We use "circle" in 
     parentheses here because we are not, as yet, actually placing 
     the segments on a circle, but on a line segment of minimal length.
     This equates to calculating an approximate solution to the *weighted*
     chromatic number (as opposed to the weighted star-chromatic number).

     To do this, we have to avoid conflicts with segments that are already
     placed.  (Once a segment has been placed, it is not moved.)  We try to 
     fit the current segment after each placed conflicting segment, in 
     increasing order of ending location.  (This can be done if the length
     of the current segment is <= the distance between the end of the 
     current conflicting segment and the beginning of the next conflicting
     segment.)  If it can't be done, we move on to the next conflicting
     segment and try again.  Note that for maximum efficiency, this requires
     that we create a sorted list of conflicting segments, ordered by 
     ending location; this information is stored in the ends[] array.
  */

    ends = (int *)calloc(n, sizeof(int));
    if (!ends)
	return 0;
  
    /* find initial node (one with the greatest duration of highest degree) */
    curr = 0;
    for (i=1; i<n; i++)
	if (nodes[curr].duration <= nodes[i].duration)
	{
	    if (nodes[curr].duration == nodes[i].duration)
	    {
		if (nodes[curr].degree < nodes[i].degree)
		    curr = i;
	    }
	    else
		curr = i;
	}

    /*
    printf("first node: %d\n", curr);
    */

    /* specify the start of the initial node to be 0 */
    nodes[curr].start = 0;
    nodes[curr].end = nodes[curr].start + nodes[curr].duration;
    inserted = 1;
    
    /* update conflicts for all nodes connected to this node */
    for (i=0; i<n; i++)
	if (A[curr][i])
	{
	    nodes[curr].conflicts++;
	    nodes[i].conflicts++;
	}
    
    while (inserted < n)
    {
	/* select an unplaced node */
	curr = select_node_1(n, nodes);

	/* identify the nodes that conflict with the current node whose
	   start has already been specified, and order their indices (in 
	   nondecreasing order of starting time) in starts */
	
	/* clear ends array */
	memset(ends, INT_MAX, n);
	
	/* conflicts stores the number of valid entries in starts */ 
	conflicts = 0; 
	
	/* record indices of conflicting nodes in ends, and find the minimum
	   starting position for any conflicting node */
	conf_start = INT_MAX;
	for (i=0; i<n; i++)
	    if ((A[curr][i]) && (nodes[i].start != INT_MAX))
	    {
		if (nodes[i].start < conf_start)
		    conf_start = nodes[i].start;
		ends[conflicts++] = i;
	    }

	/* early termination: if no conflicts, place it at 0 */
	if (!conflicts)
	{
	    nodes[curr].start = 0;
	    nodes[curr].end = nodes[curr].start + nodes[curr].duration;
	    inserted++;
	    printf("nodes[%d].start = %d\n", curr, nodes[curr].start);
	    /* update conflicts for all nodes connected to this node */
	    for (k=0; k<n; k++)
		if (A[curr][k])
		{
		    nodes[curr].conflicts++;
		    nodes[k].conflicts++;
		}
	    continue;
	}	    

	/* sort ends array */
	if (conflicts >= 2)
	{
	    for (i=1; i<conflicts; i++)
	    {
		j = i-1;
		/* push i as far to the left as possible; j will be i's new
		   position */
		while ((nodes[ends[i]].end < nodes[ends[j]].end) && 
		       (j >= 0))
		    j--;
                j++;
		
		m = ends[i];
		for (k=i; k>j; k--)
		    ends[k] = ends[k-1];
		ends[j] = m;
	    }
	}

	/*
	printf("sorted ends array:  ");
	for (j=0; j<conflicts; j++)
	    printf("%d, %d\t", ends[j], nodes[ends[j]].end);
	printf("\n");
	*/

	/* special case: check to see whether we can put this at the
	   beginning of the "circle", i.e., position 0 */
	if (nodes[curr].duration <= conf_start)
	{
	    nodes[curr].start = 0;
	    nodes[curr].end = nodes[curr].start + nodes[curr].duration;
	}
	else
	{
	    /* specify the position of curr in the circle, subject to the
	       conflicting nodes already placed; place it greedily as 
	       far to the left as possible.*/
	    nodes[curr].start = nodes[ends[0]].end;
	    nodes[curr].end = nodes[curr].start + nodes[curr].duration;
	    for (i=1; i<conflicts; i++)
	    {
		if ((nodes[curr].start < nodes[ends[i]].end) &&
		    (nodes[curr].end > nodes[ends[i]].start))
		{
		    nodes[curr].start = nodes[ends[i]].end;
		    nodes[curr].end = nodes[curr].start + nodes[curr].duration;
		}
	    }
	}

	inserted++;
	/* update conflicts for all nodes connected to this node */
	for (k=0; k<n; k++)
	    if (A[curr][k])
	    {
		nodes[curr].conflicts++;
		nodes[k].conflicts++;
	    }
    }

    /* find maximum of ending points; this is the total length of the cycle */
    end = nodes[0].end;
    for (i=1; i<n; i++)
	if (nodes[i].end > end)
	    end = nodes[i].end;

  free(ends);
  return end;
}

/*******************************************************************
 * select_node_1()
 *
 *    priority for node selection:
 *      a) largest number of conflicts with already chosen nodes
 *      b) largest duration
 *      c) largest degree
 *******************************************************************/
int select_node_1(int n, node *nodes)
{
    int i, curr;

    curr = 0;
    while (nodes[curr].start != INT_MAX)
	curr++;
    
    for (i=curr; i<n; i++)
    {
	/* if this node has not yet been placed */
	if (nodes[i].start == INT_MAX)
	{
	    if (nodes[curr].conflicts <= nodes[i].conflicts)
	    {
		if (nodes[curr].conflicts == nodes[i].conflicts)
		{
		    if (nodes[curr].duration <= nodes[i].duration)
		    { 
			if (nodes[curr].duration == nodes[i].duration)
			{
			    if (nodes[curr].degree < nodes[i].degree)
				curr = i;
			}
			else
			    curr = i;
		    }
		}
		else
		    curr = i;
	    }
	}
    }

    /*
    printf("selected <%d>: duration %d, start %d, conflicts %d, "
	   "degree %d\n", curr, nodes[curr].duration, nodes[curr].start, 
	   nodes[curr].conflicts, nodes[curr].degree);
    */

    return curr;
}

/*******************************************************************
 * select_node_2()
 *
 *    priority for node selection:
 *      a) largest duration
 *      b) largest number of conflicts with already chosen nodes
 *      c) largest degree
 *******************************************************************/
int select_node_2(int n, node *nodes)
{
    int i, curr;

    curr = 0;
    while (nodes[curr].start != INT_MAX)
	curr++;
    
    for (i=curr; i<n; i++)
    {
	/* if this node has not yet been placed */
	if (nodes[i].start == INT_MAX)
	{
	    if (nodes[curr].duration <= nodes[i].duration)
	    {
		if (nodes[curr].duration == nodes[i].duration)
		{
		    if (nodes[curr].conflicts <= nodes[i].conflicts)
		    { 
			if (nodes[curr].conflicts == nodes[i].conflicts)
			{
			    if (nodes[curr].degree < nodes[i].degree)
				curr = i;
			}
			else
			    curr = i;
		    }
		}
		else
		    curr = i;
	    }
	}
    }

    /*
    printf("selected <%d>: duration %d, start %d, conflicts %d, "
	   "degree %d\n", curr, nodes[curr].duration, nodes[curr].start, 
	   nodes[curr].conflicts, nodes[curr].degree);
    */

    return curr;
}