/* This is the serial push/relabel max-flow algorithm
 * This version does depth first search instead of implementing a queue
 */
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define RAND_SEED 99
#define NUM_NODES 400
#define MAX_D     NUM_NODES*2
#define S         0               // nodeId of source
#define T         NUM_NODES-1     // nodeId of target
#define MAX_CAP   10
#define NUM_RUNS  3

class nodeList;

class nodeClass {
  
public:
  int nodeId,d,e,working;
  nodeList *adjNodeList;

  nodeClass (int nodeId, int d, int e, nodeList *adjNodeList) {
    this->nodeId = nodeId;
    this->d = d;
    this->e = e;
    this->adjNodeList = adjNodeList;
    this->working = 0;
  }

};

class nodeList {

public:
  nodeClass *node;
  nodeList *next;

  nodeList (nodeClass *node, nodeList *next) {
    this->node = node;
    this->next = next;
  }

  void addNode (nodeClass *newNode) {
    next = new nodeList(newNode, next);
  }
};

class nodeListClass {
  
public:
  nodeList *head, *tail;

  nodeListClass() {
    head = NULL;
    tail = NULL;
  }

  int empty() {
    if (head == NULL) return 1; else return 0;
  }

  nodeClass* getHead() {
    if (head == NULL) return NULL;

    nodeClass *headNode;
    nodeList *newHead;

    headNode = head->node;
    newHead = head->next;
    delete head;
    head = newHead;
    if (head == NULL) {
      tail = NULL;
    }

    return headNode;
  }

  void addToTail (nodeClass *node) {
    if (head == NULL) {
      // this is a new list, nothing in it yet
      head = new nodeList(node, NULL);
      tail = head;
    } else {
      tail->next = new nodeList(node, NULL);
      tail = tail->next;
    }
  }
};


class activeListClass {

public:
  nodeListClass *list;
  int inList[NUM_NODES];

  activeListClass() {
    list = new nodeListClass();
    for (int a=0; a<NUM_NODES; a++) {
      inList[a] = 0;
    }
  }

  int empty() {
    return list->empty();
  }

  nodeClass* getHead() {
    nodeClass *node;
    
    node = list->getHead();
    if (node != NULL) {
      inList[node->nodeId] = 0;
    }
    return node;
  }

  void addToTail (nodeClass *node) {
    if ((node->nodeId != S) && 
	(node->nodeId !=T) &&
	(inList[node->nodeId] == 0)) {
      inList[node->nodeId] = 1;
      list->addToTail(node);
    }
  }

  void print() {
    nodeList *curNodeList;
    
    curNodeList = list->head;

    printf ("Active List: ");
    while (curNodeList != NULL) {
      printf ("%d ", curNodeList->node->nodeId);
      curNodeList = curNodeList->next;
    }
    printf ("\n");
  }
};


// Global variables
int **r; // residual network capacities
nodeClass *nodes[NUM_NODES];
activeListClass *activeNodeList;

int min (int a, int b) {
  if (a<=b) return a; else return b;
}

/* Used for debuggin only
 */
void printNodes() {

  nodeClass *n;

  printf ("Nodes:\n");

  for (int a=0; a<NUM_NODES; a++) {
    n = nodes[a];
    printf("Node: %d d=%d e=%d\n", n->nodeId, n->d, n->e);
  }
}

void printR() {

  printf ("R:\n");
  for (int a=0; a<NUM_NODES; a++) {
    for (int b=0; b<NUM_NODES; b++) {
      printf ("%d ", r[a][b]);
    }
    printf ("\n");
  }

}

void printArcs() {

  nodeClass *node;
  nodeList *curAdjNodeList;
  
  printf ("Arcs:\n");
  for (int a=0; a<NUM_NODES; a++) {
    node = nodes[a];
    printf ("Node: %d ", a);
    curAdjNodeList = node->adjNodeList;
    while (curAdjNodeList != NULL) {
      printf ("%d ", curAdjNodeList->node->nodeId);
      curAdjNodeList = curAdjNodeList->next;
    }
    printf ("\n");
  }
}




void generateNodes() {

  int a;
  nodeClass *node;

  for (a=0; a<NUM_NODES; a++) {
    node = new nodeClass(a, 0, 0, NULL);
    nodes[a] = node;
  }
}

/* This adds the necessary arcs to both fromNode and toNode.
 * It also adds the capacity to r
 * It assumes that an edge from fromNode to toNode (or other way around) has
 * never been added before!!
 * cap > 0
 */
void addArc(nodeClass *fromNode, nodeClass *toNode, int cap) {
  r[fromNode->nodeId][toNode->nodeId] = cap;
  if (fromNode->adjNodeList == NULL) {
    fromNode->adjNodeList = new nodeList (toNode, NULL);
  } else {
    fromNode->adjNodeList->addNode (toNode);
  }
  if (toNode->adjNodeList == NULL) {
    toNode->adjNodeList = new nodeList (fromNode, NULL);
  } else {
    toNode->adjNodeList->addNode (fromNode);
  }
}


/* Special case to push/relabel S
 */
void pushRelabelS() {

  nodeClass *node;
  nodeList *curAdjNodeList;
  nodeClass *curAdjNode;
  int pushAmnt, *resArcCap, *revResArcCap;
  
  node = nodes[S];
  curAdjNodeList = node->adjNodeList;

  while (curAdjNodeList != NULL) {
    curAdjNode   = curAdjNodeList->node;
    resArcCap    = &r[node->nodeId][curAdjNode->nodeId];
    revResArcCap = &r[curAdjNode->nodeId][node->nodeId];
    if (*resArcCap > 0) {
      pushAmnt     = *resArcCap;
      node->e -= pushAmnt;
      curAdjNode->e += pushAmnt;
      *resArcCap -= pushAmnt;
      *revResArcCap += pushAmnt;
      // need to schedule curAdjNode so that it will get processed as active
      activeNodeList->addToTail(curAdjNode);
    }
    curAdjNodeList = curAdjNodeList->next;
  }

  node->d = NUM_NODES;
}



void pushRelabel (nodeClass *node) {
  // node must be an active node (e>0) - not necessary anymore

  nodeList *curAdjNodeList;
  nodeClass *curAdjNode;
  int pushAmnt, *resArcCap, *revResArcCap;

  if ((!node->working) && (node->nodeId != S) && (node->nodeId != T)) {
    node->working = 1;
    curAdjNodeList = node->adjNodeList;

    // checking all the adjacent nodes
    while (curAdjNodeList != NULL) {
      curAdjNode   = curAdjNodeList->node;
      resArcCap    = &r[node->nodeId][curAdjNode->nodeId];
      revResArcCap = &r[curAdjNode->nodeId][node->nodeId];
      if ((curAdjNode->d == node->d - 1) && 
	  (*resArcCap > 0) && 
	  (node->e > 0)) {
	// this arc is admissible - we can push flow
	pushAmnt     = min(node->e, *resArcCap);
	node->e -= pushAmnt;
	curAdjNode->e += pushAmnt;
	*resArcCap -= pushAmnt;
	*revResArcCap += pushAmnt;
	// need to schedule curAdjNode so that it will get processed as active
	//activeNodeList->addToTail(curAdjNode);
	pushRelabel(curAdjNode);
      }
      curAdjNodeList = curAdjNodeList->next;
    }

    if (node->e > 0) {
    
      // otherwise this node is still active, need to relabel and reschedule
  
      int curD;
      int minAdjD = MAX_D;
      curAdjNodeList = node->adjNodeList;

      // checking all the adjacents nodes
      while (curAdjNodeList != NULL) {
	if (r[node->nodeId][curAdjNodeList->node->nodeId]) {
	  curD = curAdjNodeList->node->d;
	  if (curD < minAdjD) minAdjD = curD;
	}
	curAdjNodeList = curAdjNodeList->next;
      }

      node->d = minAdjD + 1;

      activeNodeList->addToTail(node);
      //pushRelabel(node);
    }
    node->working = 0;
  } else {
    activeNodeList->addToTail(node);
  }

}


void initR() {

  r = (int**)malloc(sizeof(int*)*NUM_NODES);
  for (int a=0; a<NUM_NODES; a++) {
    r[a] = (int*)malloc(sizeof(int)*NUM_NODES);
    for (int b=0; b<NUM_NODES; b++) {
      r[a][b] = 0;
    }
  }
}


void initNodes() {

  nodeList *adjNodeList;

  for (int a=0; a<NUM_NODES; a++) {
    nodes[a]->e = 0;
    nodes[a]->d = 0;
    nodes[a]->working = 0;
    while (nodes[a]->adjNodeList != NULL) {
      adjNodeList = nodes[a]->adjNodeList;
      nodes[a]->adjNodeList = nodes[a]->adjNodeList->next;
      delete adjNodeList;
    }
  }
}

void initDistances() {
  
  nodeListClass *nodesToTouch;
  nodeList *curAdjNodeList;
  nodeClass *node, *adjNode;
  int nextD;
  int touched[NUM_NODES];

  for (int a=0; a<NUM_NODES; a++) {
    touched[a] =0;
  }

  nodesToTouch = new nodeListClass();

  nodes[T]->d = 0;
  touched[T] = 1;
  nodesToTouch->addToTail(nodes[T]);

  // this basically does breadth first search backwards from T
  while (!nodesToTouch->empty()) {
    node = nodesToTouch->getHead();
    nextD = node->d+1;
    curAdjNodeList = node->adjNodeList;
    while (curAdjNodeList != NULL) {
      adjNode = curAdjNodeList->node;
      if (!touched[adjNode->nodeId] && r[adjNode->nodeId][node->nodeId]) {
	touched[adjNode->nodeId] = 1;
	adjNode->d = nextD;
	nodesToTouch->addToTail(adjNode);
      }
      curAdjNodeList = curAdjNodeList->next;
    }
  }
}

/* This connects a small test graph used for testing
 */
void connectTestGraph() {
  addArc(nodes[0],nodes[1],3);
  addArc(nodes[0],nodes[3],2);
  addArc(nodes[0],nodes[2],3);
  addArc(nodes[1],nodes[4],4);
  addArc(nodes[2],nodes[3],1);
  addArc(nodes[2],nodes[5],2);
  addArc(nodes[3],nodes[1],1);
  addArc(nodes[3],nodes[5],4);
  addArc(nodes[4],nodes[3],1);
  addArc(nodes[4],nodes[5],1);
  addArc(nodes[1],nodes[2],0);
}

/* This connects a fully connected graph with random caps
 */
void connectRandomGraph() {

  int a,b;

  //srand(time(NULL));
  srand(RAND_SEED); //so that we can compare runs

  for (a=0; a<NUM_NODES; a++) {
    for (b=a+1; b<NUM_NODES; b++) {
      addArc(nodes[a],nodes[b],rand()%MAX_CAP+1);
    }
  }
}


void findMaxFlow() {

  nodeClass *node;
  pushRelabelS();
  
  node = activeNodeList->getHead();
  while (node != NULL) {
   
    pushRelabel(node);
    node = activeNodeList->getHead();
  }
}


void main() {

  clock_t startTime, endTime, totTime;
  
  generateNodes();
  activeNodeList = new activeListClass();
  totTime = 0;

  for (int run=0; run<NUM_RUNS; run++) {
  
    initNodes();
    initR();
  
    //connectTestGraph();
    connectRandomGraph();

    initDistances();

    //printR();
  
    printf ("Starting run %d\n", run);
    startTime = clock();
    findMaxFlow();
    endTime = clock();
    //printf ("Done Max-Flow\n");

    totTime += endTime-startTime;

  }

  printf ("max flow:     %d\n", nodes[NUM_NODES-1]->e);
  printf ("# of nodes:   %d\n", NUM_NODES);
  printf ("# of runs:    %d\n", NUM_RUNS);
  printf ("tot time (s): %f\n", ((float)totTime)/CLOCKS_PER_SEC);
  printf ("avg time (s): %f\n", ((float)totTime)/CLOCKS_PER_SEC/NUM_RUNS);

}