Find minimum weight cycle on every node of a graph

Given an undirected graph which have include N nodes and there relative edges (form of Adjacency list) . Our goal is to detect each node minimum cycle there node length more than two in this graph. And there is also possible graph nodes are not contain any cycle.

Here given code implementation process.

``````//C Program
//Find minimum weight cycle on every node of a graph
//Where cycle length is more than 2
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> //for INT_MAX

struct AjlistNode
{
int id;//Vertices id
int weight;
struct AjlistNode*next;
};

struct Graph
{
int data; //node key value
struct AjlistNode*next;
};

//number of nodes
int size;

//set node key value
void set_data(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;

for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
printf("Vertic Node is Empty");
}
}
void connect_edge(struct Graph*node, int V ,int E,int weight)
{

struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);
if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->id=E;
newEdge->weight=weight;

struct AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");

}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph*node, int V ,int E,int weight)
{
//Add edge form V to E
//V and E is Node location
if(V<size && E <size)
{

connect_edge(node,V,E,weight);
if(V==E)
{
return;
}
connect_edge(node,E,V,weight);
}else
{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
void print_graph(struct Graph*node)

{
if(node!=NULL)

{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data

printf("  %d",node[temp->id].data);
temp=temp->next;
}
}
}else
{
printf("Empty Graph");
}
}

void minimum_cycle(int start,int end,int *visit,
struct Graph*node,int *result,int length,int sum)
{

if(start >size || end >size || start<0 || end<0 && node==NULL)
{
//invalid input
return ;
}

if(visit[start]==1)
{

if(start == end && length > 2 && sum < *result)
{
*result = sum;
}

return;
}

visit[start]=1;

struct AjlistNode *temp=node[start].next;

while(temp!=NULL)
{
minimum_cycle(temp->id,end,visit,node,result,length+1,sum+(temp->weight));

temp=temp->next;
}

visit[start]=0;
}
void reset_info(int *arr)
{
for (int i = 0; i < size; ++i)
{
arr[i]=0;
}
}
void node_cycle_weight(struct Graph*node)
{

int visit[size];

int result = INT_MAX;

for (int i = 0; i < size; ++i)
{
result = INT_MAX;

reset_info(visit);

minimum_cycle(i,i,visit,node,&result,0,0);

if(result==INT_MAX)
{
//Assuming that exist cycle weight less than INT_MAX
printf("\n Node [%d]  Min weight cycle : None",i);
}
else
{
printf("\n Node [%d]  Min weight cycle : %d",i,result);
}

}

}
int main()

{

size=7;

struct Graph*node=NULL;

node=(struct Graph*)malloc(sizeof(struct Graph)*size);

if(node==NULL)
{
printf("\n Memory overflow");
}else
{
//First set node keys
set_data(node);

//Connected two node with Edges
print_graph(node);
node_cycle_weight(node);
}
return 0;
}```
```

Output

`````` Adjacency list of vertex 0  :  1  3  4  5
Adjacency list of vertex 1  :  0  2  4
Adjacency list of vertex 2  :  1  3  5
Adjacency list of vertex 3  :  0  2  4
Adjacency list of vertex 4  :  0  1  3  5
Adjacency list of vertex 5  :  0  2  4  6
Adjacency list of vertex 6  :  5
Node [0]  Min weight cycle : 4
Node [1]  Min weight cycle : 10
Node [2]  Min weight cycle : 4
Node [3]  Min weight cycle : 4
Node [4]  Min weight cycle : 6
Node [5]  Min weight cycle : 4
Node [6]  Min weight cycle : None``````
``````// C++ Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
#include<iostream>
#include <limits.h> //for INT_MAX
using namespace std;
class AjlistNode {
public:

//Vertices node key
int id;
int weight;
AjlistNode *next;
AjlistNode(int id, int weight) {
//Set value of node key
this->id = id;
this->weight = weight;
this->next = NULL;
}
};
class Vertices {
public:
int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data) {
this->data = data;
this->next = NULL;
}
};
class MyGraph {
public:

//Number of Vertices
int size;
Vertices *node;
int result;
MyGraph(int size) {
//set value
this->size = size;
this->result = 0;
this->node = new Vertices[size];
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
for (int index = 0; index < this->size; index++) {
this->node[index] = index;
}
}
}
//Connect two nodes
void connect(int start, int last, int weight) {
AjlistNode *new_edge = new AjlistNode(last, weight);
if (this->node[start].next == NULL) {
this->node[start].next = new_edge;
} else {
AjlistNode *temp = this->node[start].next;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_edge;
}
}
void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < this->size &&
last >= 0 &&
last < this->size &&
this->node != NULL) {
this->connect(start, last, weight);
if (start == last) {
return;
}
this->connect(last, start, weight);
} else {
cout << "\nHere Something Wrong";
}
}
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
for (int index = 0; index < this->size; index++) {
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << " " << this->node[temp->id].data;
temp = temp->next;
}
}
}
}
void minimum_cycle(int start, int last, bool visit[], int length, int sum) {
if (start > this->size ||
last > this->size ||
start < 0 ||
last < 0 &&
this->node == NULL) {
return;
}
if (visit[start] == true) {
if (start == last &&
length > 2 &&
sum < this->result) {
//When find a new max weight cycle
this->result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
AjlistNode *temp = this->node[start].next;
while (temp != NULL) {
this->minimum_cycle(temp->id, last, visit, length + 1, sum + (temp->weight));
//visit to next edge
temp = temp->next;
}
// Reset the value of visited node status
visit[start] = false;
}
void reset_path(bool visit[]) {
//Set initial visited node status

for (int i = 0; i < this->size; ++i) {
visit[i] = false;
}
}
void node_cycle_weight() {
bool *visit = new bool[size];
for (int i = 0; i < this->size; ++i) {
this->result = INT_MAX;
this->reset_path(visit);
//Check cycle of node i to i
//Here initial cycle weight is zero
this->minimum_cycle(i, i, visit, 0, 0);
if (this->result == INT_MAX) {
//Assuming that exist cycle weight less than max int

cout << "\n Node [" << i << "] Min weight cycle : None";
} else {
cout << "\n Node [" << i << "] Min weight cycle : " << this->result;
}
}
}
};
int main() {
//7 implies the number of nodes in graph
MyGraph g =  MyGraph(7);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.node_cycle_weight();
return 0;
}```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````// Java Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;

public AjlistNode(int id,int weight) {
//Set value of node key
this.id = id;
this.weight=weight;
this.next = null;
}
}
class Vertices {

public int data;
public AjlistNode next;

public Vertices(int data) {
this.data = data;
this.next = null;
}
}

public class MyGraph
{

//Number of Vertices
public int size;

public Vertices []node;
public int result;
public MyGraph(int size)
{
//set value
this.size = size;
this.result = 0;
this.node = new Vertices[size];
this.set_data();

}

//Set initial node value
public void set_data()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index=0;index<size;index++)
{

node[index]=new Vertices(index);
}
}
}

//Connect two nodes
public void connect(int start,int last ,int weight)
{
AjlistNode new_edge=new AjlistNode(last,weight);

if(node[start].next==null)
{
node[start].next=new_edge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=new_edge;
}
}
public void add_edge(int start,int last,int weight)
{
if(start>=0 && start < size && last >= 0 &&  last < size && node != null)
{
connect(start,last,weight);
if(start==last)
{
return;
}

connect(last,start,weight);
}else
{
System.out.println("\nHere Something Wrong");
}
}

public void print_graph()
{

if(size >0 && node!=null)
{
for(int index = 0; index < size; index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");
AjlistNode temp = node[index].next;
while(temp != null)
{
System.out.print("  "+node[temp.id].data);
temp=temp.next;
}
}
}
}

public void minimum_cycle(int start, int last, boolean[] visit,int length,int sum)
{
if (start > size || last > size || start < 0
|| last < 0 && node == null) {
return;
}
if (visit[start] == true) {

if (start == last  && length > 2 && sum < this.result)
{
//When find a new max weight cycle
this.result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;

//This is used to iterate nodes edges
AjlistNode temp = node[start].next;

while (temp != null)
{
minimum_cycle(temp.id, last, visit,length+1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}
public void reset_path(boolean[] visit)
{
//Set initial visited node status
for (int i = 0; i < size; ++i)
{
visit[i] = false;
}
}
public void node_cycle_weight() {
//Auxiliary space which is used to store information about visited node
boolean[] visit = new boolean[size];

for (int i = 0; i < size; ++i)
{
this.result = Integer.MAX_VALUE;

reset_path(visit);
//Check cycle of node i to i
//Here initial cycle weight is zero
minimum_cycle(i, i, visit,0, 0);

if(this.result==Integer.MAX_VALUE)
{
//Assuming that exist cycle weight less than max int
System.out.print("\n Node ["+i+"]  Min weight cycle : None");
}
else
{
System.out.print("\n Node ["+i+"]  Min weight cycle : "+this.result);
}
}
}
public static void main(String[] args)
{

//7 implies the number of nodes in graph
MyGraph g=new MyGraph(7);

//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge

g.print_graph();
g.node_cycle_weight();
}
}```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````// C# Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
using System;
public class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;
public AjlistNode(int id, int weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
public class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//Number of Vertices
public int size;
public Vertices[] node;
public int result;
public MyGraph(int size) {
//set value
this.size = size;
this.result = 0;
this.node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
for (int index = 0; index < size; index++) {
node[index] = new Vertices(index);
}
}
}
//Connect two nodes
public void connect(int start, int last, int weight) {
AjlistNode new_edge = new AjlistNode(last, weight);
if (node[start].next == null) {
node[start].next = new_edge;
} else {
AjlistNode temp = node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
public void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);
if (start == last) {
return;
}
connect(last, start, weight);
} else {
Console.WriteLine("\nHere Something Wrong");
}
}
public void print_graph() {
if (size > 0 &&
node != null) {
for (int index = 0; index < size; index++) {
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(" " + node[temp.id].data);
temp = temp.next;
}
}
}
}
public void minimum_cycle(int start, int last, Boolean[] visit, int length, int sum) {
if (start > size ||
last > size ||
start < 0 ||
last < 0 &&
node == null) {
return;
}
if (visit[start] == true) {
if (start == last &&
length > 2 &&
sum < this.result) {
//When find a new max weight cycle
this.result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
AjlistNode temp = node[start].next;
while (temp != null) {
minimum_cycle(temp.id, last, visit, length + 1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}
public void reset_path(Boolean[] visit) {
//Set initial visited node status

for (int i = 0; i < size; ++i) {
visit[i] = false;
}
}
public void node_cycle_weight() {
Boolean[]
//Auxiliary space which is used to store information about visited node
visit = new Boolean[size];
for (int i = 0; i < size; ++i) {
this.result = int.MaxValue;
reset_path(visit);
minimum_cycle(i, i, visit, 0, 0);
if (this.result == int.MaxValue) {
Console.Write("\n Node [" + i + "] Min weight cycle : None");
} else {
Console.Write("\n Node [" + i + "] Min weight cycle : " + this.result);
}
}
}
public static void Main(String[] args) {
//7 implies the number of nodes in graph
MyGraph g = new MyGraph(7);
g.print_graph();
g.node_cycle_weight();
}
}```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````<?php
// Php Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
class AjlistNode {
//Vertices node key

public \$id;
public \$weight;
public \$next;

function __construct(\$id, \$weight) {
//Set value of node key
\$this->id = \$id;
\$this->weight = \$weight;
\$this->next = null;
}
}
class Vertices {
public \$data;
public \$next;

function __construct(\$data) {
\$this->data = \$data;
\$this->next = null;
}
}
class MyGraph {
//Number of Vertices

public \$size;
public \$node;
public \$result;

function __construct(\$size) {
//set value
\$this->size = \$size;
\$this->result = 0;
\$this->node = array_fill(0, \$size, null);
\$this->set_data();
}
//Set initial node value

public 	function set_data() {
if (\$this->node == null) {
echo("\nEmpty Graph");
} else {
for (\$index = 0; \$index < \$this->size; \$index++) {
\$this->node[\$index] = new Vertices(\$index);
}
}
}
//Connect two nodes

public 	function connect(\$start, \$last, \$weight) {
\$new_edge = new AjlistNode(\$last, \$weight);
if (\$this->node[\$start]->next == null) {
\$this->node[\$start]->next = \$new_edge;
} else {
\$temp = \$this->node[\$start]->next;
while (\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$new_edge;
}
}

public 	function add_edge(\$start, \$last, \$weight) {
if (\$start >= 0 &&
\$start < \$this->size &&
\$last >= 0 &&
\$last < \$this->size &&
\$this->node != null) {
\$this->connect(\$start, \$last, \$weight);
if (\$start == \$last) {
return;
}
\$this->connect(\$last, \$start, \$weight);
} else {
echo("\nHere Something Wrong");
}
}
public 	function print_graph() {
if (\$this->size > 0 &&
\$this->node != null) {
for (\$index = 0; \$index < \$this->size; \$index++) {
echo("\nAdjacency list of vertex ". \$index ." :");
\$temp = \$this->node[\$index]->next;
while (\$temp != null) {
echo(" ". \$this->node[\$temp->id]->data);
\$temp = \$temp->next;
}
}
}
}
public 	function minimum_cycle(\$start, \$last, & \$visit, \$length, \$sum) {
if (\$start > \$this->size ||
\$last > \$this->size ||
\$start < 0 ||
\$last < 0 &&
\$this->node == null) {
return;
}
if (\$visit[\$start] == true) {
if (\$start == \$last &&
\$length > 2 &&
\$sum < \$this->result) {
//When find a new max weight cycle
\$this->result = \$sum;
}
return;
}
//Here modified  the value of visited node
\$visit[\$start] = true;
//This is used to iterate nodes edges
\$temp = \$this->node[\$start]->next;
while (\$temp != null) {
\$this->minimum_cycle(\$temp->id, \$last, \$visit, \$length + 1, \$sum + (\$temp->weight));
//visit to next edge
\$temp = \$temp->next;
}
// Reset the value of visited node status
\$visit[\$start] = false;
}
public 	function reset_path( & \$visit) {
//Set initial visited node status

for (\$i = 0; \$i < \$this->size; ++\$i) {
\$visit[\$i] = false;
}
}
public 	function node_cycle_weight() {
//Auxiliary space which is used to store information about visited node
\$visit = array_fill(0, \$this->size, false);
for (\$i = 0; \$i < \$this->size; ++\$i) {
\$this->result = PHP_INT_MAX;
\$this->reset_path(\$visit);
//Check cycle of node i to i
//Here initial cycle weight is zero
\$this->minimum_cycle(\$i, \$i, \$visit, 0, 0);
if (\$this->result == PHP_INT_MAX) {
//Assuming that exist cycle weight less than max int

echo("\n Node [". \$i ."] Min weight cycle : None");
} else {
echo("\n Node [". \$i ."] Min weight cycle : ". \$this->result);
}
}
}
}

function main() {
//7 implies the number of nodes in graph
\$g = new MyGraph(7);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
\$g->print_graph();
\$g->node_cycle_weight();

}
main();```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````// Node Js Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
class AjlistNode {
//Vertices node key

constructor(id, weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
class Vertices {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyGraph {
//Number of Vertices

constructor(size) {
//set value
this.size = size;
this.result = 0;
this.node = Array(size).fill(null);
this.set_data();
}

//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
for (var index = 0; index < this.size; index++) {
this.node[index] = new Vertices(index);
}
}
}

//Connect two nodes
connect(start, last, weight) {
var new_edge = new AjlistNode(last, weight);
if (this.node[start].next == null) {
this.node[start].next = new_edge;
} else {
var temp = this.node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}

if (start >= 0 &&
start < this.size &&
last >= 0 &&
last < this.size &&
this.node != null) {
this.connect(start, last, weight);
if (start == last) {
return;
}
this.connect(last, start, weight);
} else {
process.stdout.write("\nHere Something Wrong");
}
}
print_graph() {
if (this.size > 0 &&
this.node != null) {
for (var index = 0; index < this.size; index++) {
process.stdout.write("\nAdjacency list of vertex " + index + " :");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(" " + this.node[temp.id].data);
temp = temp.next;
}
}
}
}
minimum_cycle(start, last, visit, length, sum) {
if (start > this.size ||
last > this.size ||
start < 0 ||
last < 0 &&
this.node == null) {
return;
}

if (visit[start] == true) {
if (start == last &&
length > 2 &&
sum < this.result) {
//When find a new max weight cycle
this.result = sum;
}

return;
}

//Here modified  the value of visited node
visit[start] = true;
//This is used to iterate nodes edges
var temp = this.node[start].next;
while (temp != null) {
this.minimum_cycle(temp.id, last, visit, length + 1, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}

// Reset the value of visited node status
visit[start] = false;
}
reset_path(visit) {
//Set initial visited node status

for (var i = 0; i < this.size; ++i) {
visit[i] = false;
}
}
node_cycle_weight() {
//Auxiliary space which is used to store information about visited node
var visit = Array(this.size).fill(false);
for (var i = 0; i < this.size; ++i) {
this.result = Number.MAX_VALUE;
this.reset_path(visit);
//Check cycle of node i to i
//Here initial cycle weight is zero
this.minimum_cycle(i, i, visit, 0, 0);
if (this.result == Number.MAX_VALUE) {
//Assuming that exist cycle weight less than max int

process.stdout.write("\n Node [" + i + "] Min weight cycle : None");
} else {
process.stdout.write("\n Node [" + i + "] Min weight cycle : " + this.result);
}
}
}
}

function main(args) {
//7 implies the number of nodes in graph
var g = new MyGraph(7);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.node_cycle_weight();
}

main();```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````#  Python 3 Program
#  Find minimum weight cycle on every node of a graph
#  Where cycle length is more than 2
import sys
class AjlistNode :
# Vertices node key
def __init__(self, id, weight) :
# Set value of node key
self.id = id
self.weight = weight
self.next = None

class Vertices :

def __init__(self, data) :
self.data = data
self.next = None

class MyGraph :
# Number of Vertices

def __init__(self, size) :
# set value
self.size = size
self.result = 0
self.node = [None] * size
self.set_data()

# Set initial node value
def set_data(self) :
if (self.node == None) :
print("\nEmpty Graph", end = "")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1

# Connect two nodes
def connect(self, start, last, weight) :
new_edge = AjlistNode(last, weight)
if (self.node[start].next == None) :
self.node[start].next = new_edge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next

temp.next = new_edge

# Add edge of two nodes
def add_edge(self, start, last, weight) :
if (start >= 0 and start < self.size and
last >= 0 and last < self.size and self.node != None) :
self.connect(start, last, weight)
if (start == last) :
return

self.connect(last, start, weight)
else :
print("\nHere Something Wrong", end = "")

def print_graph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," :", end = "")
temp = self.node[index].next
while (temp != None) :
print(" ", self.node[temp.id].data, end = "")
temp = temp.next

index += 1

def minimum_cycle(self, start, last, visit, length, sum) :
if (start > self.size or last > self.size
or start < 0 or last < 0 and self.node == None) :
return

if (visit[start] == True) :
if (start == last and length > 2 and sum < self.result) :
# When find a new max weight cycle
self.result = sum

return

# Here modified  the value of visited node
visit[start] = True
temp = self.node[start].next
while (temp != None) :
self.minimum_cycle(temp.id, last, visit, length + 1, sum + (temp.weight))
# visit to next edge
temp = temp.next

#  Reset the value of visited node status
visit[start] = False

def reset_path(self, visit) :
# Set initial visited node status
i = 0
while (i < self.size) :
visit[i] = False
i += 1

def node_cycle_weight(self) :
visit = [False] * self.size
i = 0
while (i < self.size) :
self.result = sys.maxsize
self.reset_path(visit)
self.minimum_cycle(i, i, visit, 0, 0)
if (self.result == sys.maxsize) :
print("\n Node [", i ,"] Min weight cycle : None", end = "")
else :
print("\n Node [", i ,"] Min weight cycle : ", self.result, end = "")

i += 1

def main() :
# 7 implies the number of nodes in graph
g = MyGraph(7)
# Connected two node with Edges
# First two parameter indicates number start and last nodes
# And third parameter indicates weight of edge
g.print_graph()
g.node_cycle_weight()

if __name__ == "__main__":
main()```
```

Output

``````Adjacency list of vertex  0  :  1  3  4  5
Adjacency list of vertex  1  :  0  2  4
Adjacency list of vertex  2  :  1  3  5
Adjacency list of vertex  3  :  0  2  4
Adjacency list of vertex  4  :  0  1  3  5
Adjacency list of vertex  5  :  0  2  4  6
Adjacency list of vertex  6  :  5
Node [ 0 ] Min weight cycle :  4
Node [ 1 ] Min weight cycle :  10
Node [ 2 ] Min weight cycle :  4
Node [ 3 ] Min weight cycle :  4
Node [ 4 ] Min weight cycle :  6
Node [ 5 ] Min weight cycle :  4
Node [ 6 ] Min weight cycle : None``````
``````#  Ruby Program
#  Find minimum weight cycle on every node of a graph
#  Where cycle length is more than 2
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :weight, :next
# Vertices node key
def initialize(id, weight)
# Set value of node key
self.id = id
self.weight = weight
self.next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_accessor :data, :next

def initialize(data)
self.data = data
self.next = nil
end
end
class MyGraph
# Define the accessor and reader of class MyGraph
attr_accessor :size, :node, :result
# Number of Vertices
def initialize(size)
# set value
self.size = size
self.result = 0
self.node = Array.new(size) {nil}
self.set_data()
end
# Set initial node value
def set_data()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end
# Connect two nodes
def connect(start, last, weight)
new_edge = AjlistNode.new(last, weight)
if (@node[start].next == nil)
@node[start].next = new_edge
else
temp = @node[start].next
while (temp.next != nil)
temp = temp.next
end
temp.next = new_edge
end
end
# Add edge of two nodes
if (start >= 0 &&
start < @size &&
last >= 0 &&
last < @size &&
@node != nil)
self.connect(start, last, weight)
if (start == last)
return
end
self.connect(last, start, weight)
else
print("\nHere Something Wrong")
end
end
def print_graph()
if (@size > 0 &&
@node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ,"  :")
temp = @node[index].next
while (temp != nil)
print(" ", @node[temp.id].data)
temp = temp.next
end
index += 1
end
end
end
def minimum_cycle(start, last, visit, length, sum)
if (start > @size ||
last > @size ||
start < 0 ||
last < 0 &&
@node == nil)
return
end
if (visit[start] == true)
if (start == last &&
length > 2 &&
sum < self.result)
# When find a new max weight cycle
self.result = sum
end
return
end
# Here modified  the value of visited node
visit[start] = true
temp = @node[start].next
while (temp != nil)
self.minimum_cycle(temp.id, last, visit, length + 1, sum + (temp.weight))
# visit to next edge
temp = temp.next
end
#  Reset the value of visited node status
visit[start] = false
end
def reset_path(visit)
# Set initial visited node status
i = 0
while (i < @size)
visit[i] = false
i += 1
end
end
def node_cycle_weight()
visit = Array.new(@size) {false}
i = 0
while (i < @size)
self.result = (2 ** (0. size * 8 - 2))
self.reset_path(visit)
self.minimum_cycle(i, i, visit, 0, 0)
if (self.result == (2 ** (0. size * 8 - 2)))
print("\n Node [", i ,"] Min weight cycle  :None")
else
print("\n Node [", i ,"] Min weight cycle  :", self.result)
end
i += 1
end
end
end
def main()
# 7 implies the number of nodes in graph
g = MyGraph.new(7)
# Connected two node with Edges
# First two parameter indicates number start and last nodes
# And third parameter indicates weight of edge
g.print_graph()
g.node_cycle_weight()
end
main()```
```

Output

``````Adjacency list of vertex 0  : 1 3 4 5
Adjacency list of vertex 1  : 0 2 4
Adjacency list of vertex 2  : 1 3 5
Adjacency list of vertex 3  : 0 2 4
Adjacency list of vertex 4  : 0 1 3 5
Adjacency list of vertex 5  : 0 2 4 6
Adjacency list of vertex 6  : 5
Node [0] Min weight cycle  :4
Node [1] Min weight cycle  :10
Node [2] Min weight cycle  :4
Node [3] Min weight cycle  :4
Node [4] Min weight cycle  :6
Node [5] Min weight cycle  :4
Node [6] Min weight cycle  :None``````
``````// Scala Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
class AjlistNode(var id: Int,
var next: AjlistNode,
var weight: Int) {

def this(id: Int, weight: Int) {
//Set value
this(id,null,weight);
}
}
class Vertices(var data: Int,
var next: AjlistNode) {

def this(data: Int) {
this(data,null);
}
}
class MyGraph(var size: Int,
var node: Array[Vertices],
var result: Int) {
//Number of Vertices
def this(size: Int) {
this(size,Array.fill[Vertices](size)(null),0);
this.set_data();
}
//Set initial node value
def set_data(): Unit = {
if (node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < size) {
node(index) = new Vertices(index);
index += 1;
}
}
}
//Connect two nodes
def connect(start: Int, last: Int, weight: Int): Unit = {
var new_edge: AjlistNode = new AjlistNode(last, weight);

if (node(start).next == null) {
node(start).next = new_edge;
} else {
var temp: AjlistNode = node(start).next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
def add_edge(start: Int, last: Int, weight: Int): Unit = {
if (start >= 0 &&
start < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);

if (start == last) {
return;
}
connect(last, start, weight);
} else {
print("\nHere Something Wrong");
}
}
def print_graph(): Unit = {
if (size > 0 &&
node != null) {
var index: Int = 0;
while (index < size) {
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = node(index).next;
while (temp != null) {
print(" " + node(temp.id).data);
temp = temp.next;
}
index += 1;
}
}
}
def minimum_cycle(start: Int, last: Int, visit:  Array[Boolean], length: Int, sum: Int): Unit = {
if (start > size ||
last > size ||
start < 0 ||
last < 0 &&
node == null) {
return;
}
if (visit(start) == true) {
if (start == last &&
length > 2 &&
sum < this.result) {
//When find a new max weight cycle
this.result = sum;
}
return;
}
//Here modified  the value of visited node
visit(start) = true;
var temp: AjlistNode = node(start).next;
while (temp != null) {
minimum_cycle(temp.id, last, visit, length + 1, sum + (temp.weight));

//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit(start) = false;
}
def reset_path(visit:  Array[Boolean]): Unit = {
//Set initial visited node status
var i: Int = 0;
while (i < size) {
visit(i) = false;
i += 1;
}
}
def node_cycle_weight(): Unit = {
var visit : Array[Boolean] = Array.fill[Boolean](this.size)(false);
var i: Int = 0;
while (i < size) {
this.result = Int.MaxValue;
reset_path(visit);
minimum_cycle(i, i, visit, 0, 0);

if (this.result == Int.MaxValue) {
print("\n Node [" + i + "] Min weight cycle : None");
} else {
print("\n Node [" + i + "] Min weight cycle : " + this.result);
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
//7 implies the number of nodes in graph
var g: MyGraph = new MyGraph(7);

//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g.print_graph();
g.node_cycle_weight();
}
}```
```

Output

``````Adjacency list of vertex 0 : 1 3 4 5
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 1 3 5
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 : 0 1 3 5
Adjacency list of vertex 5 : 0 2 4 6
Adjacency list of vertex 6 : 5
Node [0] Min weight cycle : 4
Node [1] Min weight cycle : 10
Node [2] Min weight cycle : 4
Node [3] Min weight cycle : 4
Node [4] Min weight cycle : 6
Node [5] Min weight cycle : 4
Node [6] Min weight cycle : None``````
``````// Swift Program
// Find minimum weight cycle on every node of a graph
// Where cycle length is more than 2
class AjlistNode {
//Vertices node key
var id: Int;
var weight: Int;
var next: AjlistNode? ;
init(_ id: Int, _ weight: Int) {
//Set value of node key
self.id = id;
self.weight = weight;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ value: Int) {
self.data = value;
self.next = nil;
}
}
class MyGraph {
//Number of Vertices
var size: Int;
var node: [Vertices]? = [Vertices]() ;
var result: Int;
init(_ size: Int) {
//set value
self.size = size;
self.result = 0;
var i = 0;
while (i<size) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Connect two nodes
func connect(_ start: Int, _ last: Int, _ weight: Int) {
let new_edge: AjlistNode? = AjlistNode(last, weight);
if (self.node![start].next == nil) {
self.node![start].next = new_edge;
} else {
var temp: AjlistNode? = self.node![start].next;
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = new_edge;
}
}
func add_edge(_ start: Int, _ last: Int, _ weight: Int) {
if (start >= 0 &&
start < self.size &&
last >= 0 &&
last < self.size &&
self.node != nil) {
self.connect(start, last, weight);
if (start == last) {
return;
}
self.connect(last, start, weight);
} else {
print("\nHere Something Wrong", terminator: "");
}
}
func print_graph() {
if (self.size > 0 &&
self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," :", terminator: "");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(" ", self.node![temp!.id].data, terminator: "");
temp = temp!.next;
}
index += 1;
}
}
}
func minimum_cycle(_ start: Int, _ last: Int, _ visit: inout[Bool], _ length: Int, _ sum: Int) {
if (start > self.size ||
last > self.size ||
start < 0 ||
last < 0 &&
self.node == nil) {
return;
}
if (visit[start] == true) {
if (start == last &&
length > 2 &&
sum < self.result) {
//When find a new max weight cycle
self.result = sum;
}
return;
}
//Here modified  the value of visited node
visit[start] = true;
var temp: AjlistNode? = self.node![start].next;
while (temp != nil) {
self.minimum_cycle(temp!.id, last, &visit, length + 1, sum + (temp!.weight));
//visit to next edge
temp = temp!.next;
}
// Reset the value of visited node status
visit[start] = false;
}
func reset_path(_ visit: inout[Bool]) {
//Set initial visited node status
var i: Int = 0;
while (i < self.size) {
visit[i] = false;
i += 1;
}
}
func node_cycle_weight() {
var visit: [Bool] = Array(repeating: false, count: self.size);
var i: Int = 0;
while (i < self.size) {
self.result = Int.max;
self.reset_path(&visit);
self.minimum_cycle(i, i, &visit, 0, 0);
if (self.result == Int.max) {
print("\n Node [", i ,"] Min weight cycle : None", terminator: "");
} else {
print("\n Node [", i ,"] Min weight cycle : ", self.result, terminator: "");
}
i += 1;
}
}
}
func main() {
//7 implies the number of nodes in graph
let g: MyGraph? = MyGraph(7);
//Connected two node with Edges
//First two parameter indicates number start and last nodes
//And third parameter indicates weight of edge
g!.print_graph();
g!.node_cycle_weight();
}
main();```
```

Output

``````Adjacency list of vertex  0  :  1  3  4  5
Adjacency list of vertex  1  :  0  2  4
Adjacency list of vertex  2  :  1  3  5
Adjacency list of vertex  3  :  0  2  4
Adjacency list of vertex  4  :  0  1  3  5
Adjacency list of vertex  5  :  0  2  4  6
Adjacency list of vertex  6  :  5
Node [ 0 ] Min weight cycle :  4
Node [ 1 ] Min weight cycle :  10
Node [ 2 ] Min weight cycle :  4
Node [ 3 ] Min weight cycle :  4
Node [ 4 ] Min weight cycle :  6
Node [ 5 ] Min weight cycle :  4
Node [ 6 ] Min weight cycle : None``````

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.