// Prim's Algorithm in C using a table with the best S vertex for
// every T vertex.  Adjacency lists are used for storing the
// undirected graph.
// See CSE 2320 Notes 15

#include <stdio.h>
#include <stdlib.h>
// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

// Basic Definitions

#define oo (1000000000)

// Declarations

int numVertices,numEdges;
struct edge {
  int tail,head,weight;
  int next;  // subscript of next edge with same tail 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first edge for a tail

float CPUtime()
{
struct rusage rusage;

getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
       + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void read_input_file()
{
// Reads a file with a weighted, undirected graph and
// stores as unordered adjacency lists.
int tail,head,weight,i,j,workingEdges;

// read number of nodes and edges
scanf("%d %d",&numVertices,&numEdges);

// Tables are allocated with space for inverses.
firstEdge=(int*) malloc(numVertices*sizeof(int));
edgeTab=(edgeType*) malloc(2*numEdges*sizeof(edgeType));
if (!firstEdge || !edgeTab)
{
  printf("edgeTab malloc failed %d\n",__LINE__);
  exit(0);
}

// Initially, all adjacency lists are empty
for (i=0;i<numVertices;i++)
  firstEdge[i]=(-1);

// read edges, each with a weight
workingEdges=0;
for (i=0; i<numEdges; i++)
{
  scanf("%d %d %d",&tail,&head,&weight);
  // Test for illegal edge.
  if (tail<0 || tail>numVertices-1 || head<0
  || head>numVertices-1 || weight<=0)
  {
    printf("Invalid input %d %d %d at %d\n",tail,head,weight,__LINE__);
    exit(0);
  }
  // Save input edge and insert in adjacency list
  edgeTab[workingEdges].tail=tail;
  edgeTab[workingEdges].head=head;
  edgeTab[workingEdges].weight=weight;
  edgeTab[workingEdges].next=firstEdge[tail];
  firstEdge[tail]=workingEdges;
  workingEdges++;
  // Save inverse of input edge and insert in adjacency list
  edgeTab[workingEdges].tail=head;
  edgeTab[workingEdges].head=tail;
  edgeTab[workingEdges].weight=weight;
  edgeTab[workingEdges].next=firstEdge[head];
  firstEdge[head]=workingEdges;
  workingEdges++;
}
}

void prim()
{
typedef enum {s,t} stType;

int i,j,MSTedgeCount=0,MSTweight=0,smallestWeight,smallestVertexNumber;
stType *flag;
int *Tweight,*bestSneighbor;

flag=(stType*) malloc(numVertices*sizeof(stType));
Tweight=(int*) malloc(numVertices*sizeof(int));
bestSneighbor=(int*) malloc(numVertices*sizeof(int));
if (!flag || !Tweight || !bestSneighbor)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
// Vertex 0 starts in S.  Other vertices start in T.
flag[0]=s;
for (i=1;i<numVertices;i++)
  flag[i]=t;

// Initialize T-table with edges from vertex 0.
for (i=0;i<numVertices;i++)
  Tweight[i]=oo;
for (i=firstEdge[0];
     i!=(-1);
     i=edgeTab[i].next)
{
  Tweight[edgeTab[i].head]=edgeTab[i].weight;
  bestSneighbor[edgeTab[i].head]=0;
}

// Each iteration finds another MST edge
for (MSTedgeCount=0;MSTedgeCount<numVertices-1;MSTedgeCount++)
{
  // Scan for minimum weight edge.
  smallestWeight=oo;
  for (j=0;j<numVertices;j++)
    if (flag[j]==t && Tweight[j]<smallestWeight)
    {
      smallestWeight=Tweight[j];
      smallestVertexNumber=j;
    }
  if (smallestWeight==oo) // no edges remain that bridge S & T
    break;

  MSTweight+=smallestWeight;
  printf("Include edge from %d to %d of weight %d\n",
    bestSneighbor[smallestVertexNumber],smallestVertexNumber,
    smallestWeight);
  flag[smallestVertexNumber]=s;
  // Scan adjacency list looking for improvements
  for (j=firstEdge[smallestVertexNumber];
       j!=(-1);
       j=edgeTab[j].next)
    if (flag[edgeTab[j].head]==t && edgeTab[j].weight<Tweight[edgeTab[j].head])
    {
      Tweight[edgeTab[j].head]=edgeTab[j].weight;
      bestSneighbor[edgeTab[j].head]=smallestVertexNumber;
    }
}
if (MSTedgeCount<numVertices-1)
  printf("Stopped after collecting %d edges of weight %d\n",
    MSTedgeCount,MSTweight);
else
  printf("Found MST with weight %d\n",MSTweight);
free(flag);
free(Tweight);
free(bestSneighbor);
}

int main ()
{
int i,j;
float startCPU,stopCPU;

read_input_file();
startCPU=CPUtime();
prim();
stopCPU=CPUtime();
printf("Table-based Prim's time %f\n",stopCPU-startCPU);
free(edgeTab);
free(firstEdge);
}