DAA3

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "limits.h"

typedef struct graph {
  int u, v, wt;
}graph;

int validate(int n) {
  while (1) {
    if (scanf("%d", &n)) return n;
    printf("Please enter a valid integer\n");
  }
}

void rec(int *parent, int cur) {
  if (parent[cur] == cur) {printf("%d ", cur+1); return;}
  rec(parent, parent[cur]);
  printf("%d ", cur+1);
}

int main() {
  graph *ins = NULL;
  int ch, nodes, edges, tmp, u, v;
  int wt, fl = 0, sourceVertex, neg;
  int *dist = NULL, *parent = NULL, j;
  while (1) {
    printf("Enter 1)Input 2)Output 0)Exit\n");
    ch = validate(ch);
    switch(ch) {
      case 1:
        printf("Enter the number of nodes and edges\n");
        if (ins != NULL) free(ins);
        nodes = validate(nodes);
        while (nodes < 2) {
          printf("Please enter atleast 2 nodes\n");
          nodes = validate(nodes);
        }
        edges = validate(edges);
        while (edges < nodes-1 || edges > nodes*(nodes-1)) {
          printf("Please enter positive number of edges\n");
          edges = validate(edges);
        }
        printf("For next %d lines enter source, destination and weight of edge\n", edges);
        ins = (graph*)malloc(sizeof(graph)*edges);
        for (int i = 0; i < edges; ) {
          u = validate(u), v = validate(v), wt = validate(wt);
          if (u < 1 || v < 1 || u > nodes || v > nodes) {
            printf("Node value out of range, please enter again\n");
          }
          else {
            j = 0;
            --u, --v;
            for (; j < i; ++j) {
              if (ins[j].u == u && ins[j].v == v) {
                printf("Edge already exist with weight %d, Do you want to modify weight enter 1 else 0\n", ins[j].wt);
                tmp = validate(tmp);
                if (tmp == 1) {
                  ins[j].wt = wt;
                }
              }
            }
            if (j==i) {
              ins[i].u = u, ins[i].v = v, ins[i].wt = wt;
              ++i;
            }
          }
        }
      break;

      case 2:
        // for (int i = 0; i < edges; ++i)
        //   printf("%d %d %d\n", ins[i].u, ins[i].v, ins[i].wt);
        printf("Enter source vertex \n");
        sourceVertex = validate(sourceVertex);
        while (sourceVertex < 0 || sourceVertex > nodes) {
          printf("Please enter a valid source vertex\n");
          sourceVertex = validate(sourceVertex);
        }
        --sourceVertex;
        dist = (int*)malloc(sizeof(int)*(nodes));
        parent = (int*)malloc(sizeof(int)*(nodes));
        for (int i = 0; i < nodes; i++) {
          dist[i] = INT_MAX, parent[i] = -1;
        }
        dist[sourceVertex] = 0;
        parent[sourceVertex] = sourceVertex;
        for (int i = 1; i < nodes; i++) {
          neg = -1;
            for (int j = 0; j < edges; j++) {
                int u = ins[j].u;
                int v = ins[j].v;
                int wt = ins[j].wt;
                if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
                  dist[v] = dist[u] + wt;
                  neg = v;
                  parent[v] = u;
                }
            }
            if (neg == -1) break;
        }
        if (neg != -1) {
          neg = -1;
          for (int j = 0; j < edges; ++j) {
            int u = ins[j].u;
            int v = ins[j].v;
            int wt = ins[j].wt;
            if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
              neg = v;
              break;
            }
          }
        }
        // for (int i = 0; i < nodes; ++i)
        //   printf("%d %d\n", i, parent[i]);
        printf("\n");
        if (neg != -1) {
          printf("Negative Weight cycle exists\n");
        }
        else {
          for (int i = 0; i < nodes; ++i) {
            if (i == sourceVertex) {
            }
            else if (parent[i] == -1) {
              printf("for %d Path does not exists\n", i+1);
            }
            else {
              printf("Dist of %d is %d and Path is-> ", i+1, dist[i]);
              tmp = i;
              rec(parent, i);
              printf("\n");
            }
          }
        }
        free(dist);
        free(parent);
      break;

      case 0:
      if (ins != NULL) free(ins);
      exit(0);
      break;
    }
  }
  return 0;
}