/*-----------------------------------------------------------------------------
Filename   : fleury.c
Name       : Tristan Miller
SID#       : 123456789
Description: Solves the Koenigsberg bridge problem
             (Note that this program assumes the graph is connected; the
             assignment did not allow you to make this assumption.)
-----------------------------------------------------------------------------*/

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

#include "graph.h"

#define NUM_DISTRICTS 4

int getBridges(struct district d[], struct bridgelist **bridges);
bool dfs(int start, int end, const struct bridge *b, struct district d[]);
bool isCutEdge(const struct bridge *b, struct district d[]);
struct bridgelist *fleury(int start, struct district d[]);
int pathLength(const struct bridgelist *bl);
void free_bridgelist(struct bridgelist *bl, int del_bridges);

/*-----------------------------------------------------------------------------
                                      main()
-----------------------------------------------------------------------------*/
int main(void) {

  int i, numBridges;
  struct district d[NUM_DISTRICTS];
  struct bridgelist *eulerCircuit, *bl_iter, *masterlist;

  /* Initialize d here */
  for (i = 0; i < NUM_DISTRICTS; i++)
    d[i].bridges = NULL;

  numBridges = getBridges(d, &masterlist);

  printf("Calculating Euler circuit...\n");

  eulerCircuit = fleury(0, d);
  if (pathLength(eulerCircuit) == numBridges && numBridges > 1) {
    printf("Starting from District 0, take the following bridges:\n");
    for (bl_iter = eulerCircuit; bl_iter; bl_iter = bl_iter->next)
      printf("%s ", bl_iter->b->name);
    printf("\n");
  }
  else {
    printf("There is no Euler circuit.\n");
  }

  /* Destroy the linked list eulerCircuit */
  free_bridgelist(eulerCircuit, FALSE);


  /* Destroy the adjacency matrix */
  for (i = 0; i < NUM_DISTRICTS; i++)
    free_bridgelist(d[i].bridges, FALSE);

  /* Destroy the master list of bridges and the bridges themselves */
  free_bridgelist(masterlist, TRUE);

  return EXIT_SUCCESS;
}

/*----------------------------------------------------------------------------
Function: free_bridgelist()
Input   : a bridgelist (bl);
          a flag indicating whether the bridges pointed to by the bridgelist
          should be freed as well (del_bridges)
----------------------------------------------------------------------------*/
void free_bridgelist(struct bridgelist *bl, int del_bridges) {
  struct bridgelist *temp;
  for (; bl; bl = temp) {
    temp = bl->next;
    if (del_bridges)
      free(bl->b);
    free(bl);
  }
}

/*----------------------------------------------------------------------------
Function: pathLength()
Input   : a bridgelist
Output  : number of elements in the list
----------------------------------------------------------------------------*/
int pathLength(const struct bridgelist *bl) {
  int count;
  for (count = 0; bl; count++)
    bl = bl->next;
  return count;
}

/*----------------------------------------------------------------------------
Function: fleury()
Input   : starting vertex (district number) and graph
Output  : a bridgelist containing an Euler circuit (if possible)
----------------------------------------------------------------------------*/
struct bridgelist *fleury(int start, struct district d[]) {
  struct bridgelist *bl;
  struct bridge *b;

  /* Select a bridge which hasn't already been crossed and isn't a cut edge */
  for (bl = d[start].bridges; bl; bl = bl->next) {
    b = bl->b;
    if (!b->crossed && (bl->next == NULL || !isCutEdge(b, d)))
      break;
  }

  /* No more bridges left to cross */
  if (!bl)
    return NULL;

  /* Cross this bridge */
  b->crossed = TRUE;
  if (start == b->district[0])
    start = b->district[1];
  else
    start = b->district[0];

  bl = malloc(sizeof(*bl));
  if (!bl) {
    fprintf(stderr, "Error: out of memory\n");
    exit(EXIT_FAILURE);
  }
  bl->b = b;
  bl->next = fleury(start, d);

  return bl;
}

/*----------------------------------------------------------------------------
Function: isCutEdge()
Input   : an edge (bridge) and a graph containing the edge
Output  : true iff the given edge is a cut edge
----------------------------------------------------------------------------*/
bool isCutEdge(const struct bridge *b, struct district d[]) {
  int i;

  for (i = 0; i < NUM_DISTRICTS; i++)
    d[i].visited = FALSE;

  return !dfs(b->district[0], b->district[1], b, d);
}

/*----------------------------------------------------------------------------
Function: dfs()
Input   : start, end - starting and ending districts
          b          - a bridge which cannot be crossed
          d          - the graph
Output  : true iff there exists a path of uncrossed bridges from start to
          end, and bridge b is not on the path
Assumes : all districts in the graph are initially unvisited
----------------------------------------------------------------------------*/
bool dfs(int start, int end, const struct bridge *b, struct district d[]) {
  struct bridgelist *bl = d[start].bridges;

  /* We reached the goal */
  if (start == end)
    return TRUE;

  /* Have we visited this district already? */
  if (d[start].visited)
    return FALSE;

  /* Visit this district and all its adjacent districts */
  d[start].visited = TRUE;
  while (bl) {
    if (bl->b != b && b->crossed == FALSE) {
      if (bl->b->district[0] == start)
	start = bl->b->district[1];
      else
	start = bl->b->district[0];
      if (dfs(start, end, b, d))
	return TRUE;
    }
    bl = bl->next;
  }
  
  return FALSE;
}

/*----------------------------------------------------------------------------
Function: getBridges()
Input   : a graph (d)
          pointer to pointer to bridge list (bridges)
Output  : number of bridges (edges) added to the graph
          bridges will point to a master list of all bridges (edges) in the
          graph
----------------------------------------------------------------------------*/
int getBridges(struct district d[], struct bridgelist **bridges) {
  struct bridge *b;
  struct bridgelist *bl, *masterlist = NULL, *masterptr = NULL;
  int endpoint[2], i, numBridges = 0;
  char name[LABELSIZE];

  printf("Enter bridges in the following format:\n"
	 "bridge_name district1 district2\n"
	 "Enter \"done\" for the bridge name to stop.\n");

  while(1) {

    scanf("%s %d %d", name, &endpoint[0], &endpoint[1]);

    if (!strcmp(name, "done"))
      break;

    if (--endpoint[0] >= NUM_DISTRICTS ||
	--endpoint[1] >= NUM_DISTRICTS ||
	endpoint[0] < 0 ||
	endpoint[1] < 0) {
      printf("Error: invalid land index\n");
      continue;
    }

    if (endpoint[0] == endpoint[1]) {
      printf("Error: a bridge cannot connect a piece of land to itself\n");
      continue;
    }

    /* Allocate space for the bridge and initialize it */
    b = malloc(sizeof(*b));
    if (!b) {
      fprintf(stderr, "Error: out of memory\n");
      exit(EXIT_FAILURE);
    }
    b->district[0] = endpoint[0];
    b->district[1] = endpoint[1];
    b->crossed = FALSE;
    strcpy(b->name, name);

    /* Make sure the bridgelist for both districts points to this bridge */
    for (i = 0; i < 2; i++) {
      bl = malloc(sizeof(*bl));
      if (!bl) {
	fprintf(stderr, "Error: out of memory\n");
	exit(EXIT_FAILURE);
      }
      
      bl->b = b;
      bl->next = d[endpoint[i]].bridges;
      d[endpoint[i]].bridges = bl;
    }

    /* If we keep a linked list of bridges, they will be easier to free() later */
    masterptr = malloc(sizeof(*masterptr));
    if (!masterptr) {
	fprintf(stderr, "Error: out of memory\n");
	exit(EXIT_FAILURE);
    }
    masterptr->b = b;
    masterptr->next = masterlist;
    masterlist = masterptr;

    /* Increment bridge counter */
    numBridges++;
  }

  *bridges = masterlist;
  return numBridges;
}