Skip to main content

Minimum weight cycle in an undirected weighted graph in c

C program for Minimum weight cycle in an undirected weighted graph. Here more information.

// Include header file
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/*
    C program for 
    Minimum weight cycle in an undirected graph
*/
typedef struct AjlistNode {
	// Define useful field of AjlistNode
	// Vertices node key
	int id;
	int weight;
	struct AjlistNode * next;
}AjlistNode;
AjlistNode * getAjlistNode(int id, int weight) {
	// Create dynamic memory of AjlistNode
	AjlistNode * ref = (AjlistNode * ) malloc(sizeof(AjlistNode));
	if (ref == NULL) {
		// Failed to create memory 
		return NULL;
	}
	// Set value of node key
	ref->id = id;
	ref->weight = weight;
	ref->next = NULL;
	return ref;
}
typedef struct Vertices {
	// Define useful field of Vertices
	int data;
	struct AjlistNode * next;
	struct AjlistNode * last;
}Vertices;

typedef struct Graph {
	// Define useful field of Graph
	// Number of Vertices
	int size;
	int result;
	Vertices * node;
}Graph;

// Set initial node value
void setData(Graph * ref) {
	if ((ref->size <= 0)) {
		printf("\nEmpty Graph");
	} else {
		for (int index = 0; index < ref->size; index++) {
			// Set initial node value
			ref->node[index].data = index;
			ref->node[index].next = NULL;
			ref->node[index].last = NULL;
		}
	}
}
Graph * getGraph(int size) {
	// Create dynamic memory of Graph
	Graph * ref = (Graph * ) malloc(sizeof(Graph));
	if (ref == NULL) {
		// Failed to create memory 
		return NULL;
	}
	// Set value
	ref->size = size;
	ref->result = 0;
	ref->node = (struct Vertices * )
	malloc(sizeof(struct Vertices) * size);
	setData(ref);
	return ref;
}
void connection(Graph * ref, int start, int last, int weight) {
	// Safe connection
	AjlistNode * edge = getAjlistNode(last, weight);
	if ((ref->node[start].next == NULL)) {
		ref->node[start].next = edge;
	} else {
		// Add edge at the end
		ref->node[start].last->next = edge;
	}
	// Get last edge 
	ref->node[start].last = edge;
}
//  Handling the request of adding new edge
void addEdge(Graph * ref, int start, int last, int weight) {
	if ((start >= 0 && start < ref->size && 
         last >= 0 && last < ref->size)) {
		// Connect edge with weight
		connection(ref, start, last, weight);
		connection(ref, last, start, weight);
	} else {
		// When invalid nodes
		printf("\nNode missing (%d,%d)", start, last);
	}
}
void printGraph(Graph * ref) {
	if ((ref->size > 0)) {
		// Print graph ajlist
		for (int index = 0; index < ref->size; index++) {
			printf("\nAdjacency list of vertex %d :",index);
			AjlistNode * edge = ref->node[index].next;
			while (edge != NULL) {
				// Display graph node value and weight	
				printf(" %d[%d] ", ref->node[edge->id].data,edge->weight);
				// Visit to next edge
				edge = edge->next;
			}
		}
	}
}
void minimumCycle(Graph * ref, 
                  int start, 
                  int last, 
                  int visit[], 
  					int sum, int length) {
	if ((start >= ref->size || last >= ref->size || 
         start < 0 || last < 0 || ref->size <= 0)) {
		return;
	}
	if ((visit[start] == 1)) {
		// Here length are indicate loop length
		if ((length > 2 && start == last && sum < ref->result)) {
			// Here length is indicate number of nodes
			// Because graph is undirected so we consider all cycle 
			// Which contains more than 2 node
			// ---------------------
			// When find a new min weight cycle
			ref->result = sum;
		}
		return;
	}
	// Here modified  the value of visited node
	visit[start] = 1;
	// This is used to iterate nodes edges
	AjlistNode * edge = ref->node[start].next;
	while (edge != NULL) {
		//  Find solution using recursion
		minimumCycle(ref,edge->id, last, visit, 
                          sum + (edge->weight), length + 1);
		// Visit to next edge
		edge = edge->next;
	}
	// Reset the value of visited node status
	visit[start] = 0;
}
void minWeightCycle(Graph * ref) {
	if ((ref->size <= 0)) {
		// Empty graph
		return;
	}
	// Auxiliary space which is used to store 
	// information about visited node
	int visit[ref->size];
	// Set initial visited node status 
	for (int i = 0; i < ref->size; i++) {
		visit[i] = 0;
	}
	ref->result = INT_MAX;
	for (int i = 0; i < ref->size; i++) {
		// Check cycle of node i to i
		// Here initial cycle weight is zero
		minimumCycle(ref, i, i, visit, 0, 0);
	}
	// Display result
	printf("\nMin weight cycle : %d", ref->result);
}
int main() {
	// 6 implies the number of nodes in graph
	Graph * g = getGraph(6);
	// Connect node with an edge
	// First and second parameter indicate node
	// Last parameter is indicate weight
	addEdge(g, 0, 1, 3);
	addEdge(g, 0, 3, -3);
	addEdge(g, 0, 4, 7);
	addEdge(g, 0, 5, 1);
	addEdge(g, 1, 2, 11);
	addEdge(g, 1, 4, 8);
	addEdge(g, 2, 3, 1);
	addEdge(g, 2, 5, 4);
	addEdge(g, 3, 4, 2);
	addEdge(g, 4, 5, 8);
	addEdge(g, 5, 1, 0);
	// Print graph element
	printGraph(g);
	// Test
	minWeightCycle(g);
}

Output

Adjacency list of vertex 0 : 1[3]  3[-3]  4[7]  5[1]
Adjacency list of vertex 1 : 0[3]  2[11]  4[8]  5[0]
Adjacency list of vertex 2 : 1[11]  3[1]  5[4]
Adjacency list of vertex 3 : 0[-3]  2[1]  4[2]
Adjacency list of vertex 4 : 0[7]  1[8]  3[2]  5[8]
Adjacency list of vertex 5 : 0[1]  2[4]  4[8]  1[0]
Min weight cycle : 3




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment