# Karger Min Cut Implementation C language

I have been taking this class about algorithms, this week we had an assignment which was to calculate the min cut of a given un-directed graph.

I have written some code(most of it i found online).

Can please guide me through some hints on how to implement this,because I have no idea how to do this

Here is my code

#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h>  struct edge {     int vertexIndex;     struct edge *edgePtr; }edge;  struct vertex {     int vertexKey;     struct edge *edgePtr; }vertex;  struct vertex graph[200]; int vertexCount=0;  void InsertVertex(int vertexKey) {     graph[vertexCount].vertexKey=vertexKey;     graph[vertexCount].edgePtr=NULL;     vertexCount++; }  void insertEdge(int vertex1, int vertex2) {     struct edge *e,*e1,*e2;     e=graph[vertex1].edgePtr;     while(e&& e->edgePtr)     {         e=e->edgePtr;     }     e1=(struct edge *)malloc(sizeof(*e1));     e1->vertexIndex=vertex2;     e1->edgePtr=NULL;     if(e)     e->edgePtr=e1;     else     graph[vertex1].edgePtr=e1;      e=graph[vertex2].edgePtr;     while(e&& e->edgePtr)     {         e=e->edgePtr;     }     e2=(struct edge *)malloc(sizeof(*e2));     e2->vertexIndex=vertex1;     e2->edgePtr=NULL;     if(e)     e->edgePtr=e2;     else     graph[vertex2].edgePtr=e2; }  void printGraph() {     int i;     struct edge *e;     for(i=0;i<vertexCount;i++)     {         printf("(%d)",graph[i].vertexKey);         e=graph[i].edgePtr;         while(e)         {             printf("->%d",e->vertexIndex);             e=e->edgePtr;         }         printf("\n");     } }  /*       procedure contract(G=(V,E)):    while |V|>2        choose e\in E uniformly at random           G >> G/e         return the only cut in G          1)  Initialize contracted graph CG as copy of original graph         2)  While there are more than 2 vertices.             a) Pick a random edge (u, v) in the contracted graph.             b) Merge (or contract) u and v into a single vertex (update the contracted graph).             c) Remove self-loops         3) Return cut represented by two vertices. */ main() {     FILE *fr;     char line[350];     char *p;       fr = fopen("kargerMinCut.txt","r");     while(fgets(line, 350, fr) != NULL)    {      p = strtok(line, "\t");      InsertVertex(i = atoi(p));      while ((p = strtok(NULL, "\t")) != NULL)     insertEdge(i,atoi(p));    }     fclose(fr);     /*min Cut algorithm*/     return 0; } 


Replay

Category: c# Time: 2016-07-31 Views: 11
Tags: