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
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