# Maximum weight cycle in an directed graph

Here given code implementation process.

``````//C Program
//Maximum weight cycle in an directed graph
#include <stdio.h>

#include <stdlib.h>

#include <limits.h> //for INT_MIN

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

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

int size; //number of nodes

//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);

} 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 maximum_cycle(int start, int end, int *visit,
struct Graph *node, int *result, int sum) {

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

if (visit[start] == 1) {

if (start == end && sum > *result) {
//When find a new max weight cycle
*result = sum;
}

return;
}

visit[start] = 1;

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

while (temp != NULL) {

maximum_cycle(temp->id, end, visit, node, result, sum + (temp->weight));
//visit to next edge
temp = temp->next;
}

visit[start] = 0;
}

void max_cycle_weight(struct Graph *node) {

int visit[size];

int result = INT_MIN;
//Set initial visited node status
for (int i = 0; i < size; ++i) {
visit[i] = 0;
}
for (int i = 0; i < size; ++i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
maximum_cycle(i, i, visit, node, & result, 0);
}
if (result == INT_MIN) {

printf("\n Max weight cycle : None \n");
} else {
printf("\n Max weight cycle : %d \n", result);
}
}
int main()

{

size = 5;
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);
max_cycle_weight(node);

}
return 0;
}```
```

#### Output

`````` Adjacency list of vertex 0  :  1
Adjacency list of vertex 1  :  2
Adjacency list of vertex 2  :  0  3  4
Adjacency list of vertex 3  :  0  4
Adjacency list of vertex 4  :  0
Max weight cycle : 8``````
``````// C++ Program
// Maximum weight cycle in an directed graph
#include<iostream>
#include <limits.h> //for INT_MIN

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);
} 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 maximum_cycle(int start, int end, bool visit[], int sum) {
if (start > this->size ||
end > this->size ||
start < 0 ||
end < 0 &&
this->node == NULL) {
return;
}
if (visit[start] == true) {
if (start == end &&
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->maximum_cycle(temp->id, end, visit, sum + (temp->weight));
//visit to next edge
temp = temp->next;
}
// Reset the value of visited node status
visit[start] = false;
}
void max_cycle_weight() {
bool *visit = new bool[size];
//Set initial visited node status
for (int i = 0; i < this->size; ++i) {
visit[i] = false;
}
this->result = INT_MIN;
for (int i = 0; i < this->size; ++i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
this->maximum_cycle(i, i, visit, 0);
}
if (this->result == INT_MIN) {
cout << "\n Max weight cycle : None \n";
} else {
cout << "\n Max weight cycle : " << this->result << "\n";
}
}
};
int main() {
//5 implies the number of nodes in graph
MyGraph g =  MyGraph(5);
//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.max_cycle_weight();
return 0;
}```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````// Java Program
// Maximum weight cycle in an directed graph

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

}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 maximum_cycle(int start, int end, boolean[] visit,int sum)
{
if (start > size || end > size || start < 0
|| end < 0 && node == null) {
return;
}
if (visit[start] == true) {

if (start == end && sum > result)
{
//When find a new max weight cycle
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)
{
maximum_cycle(temp.id, end, visit, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}

public void max_cycle_weight() {
//Auxiliary space which is used to store information about visited node
boolean[] visit = new boolean[size];

//Set initial visited node status
for (int i = 0; i < size; ++i)
{
visit[i] = false;
}
this.result = Integer.MIN_VALUE;

for (int i = 0; i < size; ++i)
{
//Check cycle of node i to i
//Here initial cycle weight is zero
maximum_cycle(i, i, visit, 0);
}
if (result == Integer.MIN_VALUE)
{
System.out.print("\n Max weight cycle : None \n");
} else {
System.out.print("\n Max weight cycle : "+this.result+"\n");
}
}
public static void main(String[] args)
{

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

//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.max_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````// C# Program
// Maximum weight cycle in an directed graph
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);
} 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 maximum_cycle(int start, int end, Boolean[] visit, int sum) {
if (start > size ||
end > size ||
start < 0 ||
end < 0 &&
node == null) {
return;
}
if (visit[start] == true) {
if (start == end &&
sum > result) {
//When find a new max weight cycle
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) {
maximum_cycle(temp.id, end, visit, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[start] = false;
}
public void max_cycle_weight() {
Boolean[]
//Auxiliary space which is used to store information about visited node
visit = new Boolean[size];
//Set initial visited node status

for (int i = 0; i < size; ++i) {
visit[i] = false;
}
this.result = int.MinValue;
for (int i = 0; i < size; ++i) {
maximum_cycle(i, i, visit, 0);
}
if (result == int.MinValue) {
Console.Write("\n Max weight cycle : None \n");
} else {
Console.Write("\n Max weight cycle : " + this.result + "\n");
}
}
public static void Main(String[] args) {
//5 implies the number of nodes in graph
MyGraph g = new MyGraph(5);
g.print_graph();
g.max_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````<?php
// Php Program
// Maximum weight cycle in an directed graph
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, 0);
\$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);
} 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 maximum_cycle(\$start, \$end, & \$visit, \$sum) {
if (\$start > \$this->size ||
\$end > \$this->size ||
\$start < 0 ||
\$end < 0 &&
\$this->node == null) {
return;
}
if (\$visit[\$start] == true) {
if (\$start == \$end &&
\$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->maximum_cycle(\$temp->id, \$end, \$visit, \$sum + (\$temp->weight));
//visit to next edge
\$temp = \$temp->next;
}
// Reset the value of visited node status
\$visit[\$start] = false;
}
public 	function max_cycle_weight() {
//Auxiliary space which is used to store information about visited node
\$visit = array_fill(0, \$this->size, false);
//Set initial visited node status

for (\$i = 0; \$i < \$this->size; ++\$i) {
\$visit[\$i] = false;
}
\$this->result = -PHP_INT_MAX;
for (\$i = 0; \$i < \$this->size; ++\$i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
\$this->maximum_cycle(\$i, \$i, \$visit, 0);
}
if (\$this->result == -PHP_INT_MAX) {
echo("\n Max weight cycle : None \n");
} else {
echo("\n Max weight cycle : ". \$this->result ."\n");
}
}
}

function main() {
//5 implies the number of nodes in graph
\$g = new MyGraph(5);
//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->max_cycle_weight();

}
main();```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````// Node Js Program
// Maximum weight cycle in an directed graph
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);
} 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;
}
}
}
}
maximum_cycle(start, end, visit, sum) {
if (start > this.size ||
end > this.size ||
start < 0 ||
end < 0 &&
this.node == null) {
return;
}

if (visit[start] == true) {
if (start == end &&
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.maximum_cycle(temp.id, end, visit, sum + (temp.weight));
//visit to next edge
temp = temp.next;
}

// Reset the value of visited node status
visit[start] = false;
}
max_cycle_weight() {
//Auxiliary space which is used to store information about visited node
var visit = Array(this.size).fill(false);
//Set initial visited node status

for (var i = 0; i < this.size; ++i) {
visit[i] = false;
}
this.result = -Number.MAX_VALUE;
for (var i = 0; i < this.size; ++i) {
//Check cycle of node i to i
//Here initial cycle weight is zero
this.maximum_cycle(i, i, visit, 0);
}

if (this.result == -Number.MAX_VALUE) {
process.stdout.write("\n Max weight cycle : None \n");
} else {
process.stdout.write("\n Max weight cycle : " + this.result + "\n");
}
}
}

function main(args) {
//5 implies the number of nodes in graph
var g = new MyGraph(5);
//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.max_cycle_weight();
}

main();```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````#  Python 3 Program
#  Maximum weight cycle in an directed graph

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 = [0] * 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)
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 maximum_cycle(self, start, end, visit, sum) :
if (start > self.size or end > self.size
or start < 0 or end < 0 and self.node == None) :
return

if (visit[start] == True) :
if (start == end 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.maximum_cycle(temp.id, end, visit, sum + (temp.weight))
# visit to next edge
temp = temp.next

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

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

self.result = -sys.maxsize
i = 0
while (i < self.size) :
self.maximum_cycle(i, i, visit, 0)
i += 1

if (self.result == -sys.maxsize) :
print("\n Max weight cycle : None \n", end = "")
else :
print("\n Max weight cycle : ", self.result ,"\n", end = "")

def main() :
# 5 implies the number of nodes in graph
g = MyGraph(5)
# 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.max_cycle_weight()

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

#### Output

``````Adjacency list of vertex  0  :  1
Adjacency list of vertex  1  :  2
Adjacency list of vertex  2  :  0  3  4
Adjacency list of vertex  3  :  0  4
Adjacency list of vertex  4  :  0
Max weight cycle :  8``````
``````#  Ruby Program
#  Maximum weight cycle in an directed graph
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)
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 maximum_cycle(start, last, visit, sum)
if (start > @size ||
last > @size ||
start < 0 ||
last < 0 &&
@node == nil)
return
end
if (visit[start] == true)
if (start == last &&
sum > @result)
# When find a new max weight cycle
@result = sum
end
return
end
# Here modified  the value of visited node
visit[start] = true
temp = @node[start].next
while (temp != nil)
self.maximum_cycle(temp.id, last, visit, sum + (temp.weight))
# visit to next edge
temp = temp.next
end
#  Reset the value of visited node status
visit[start] = false
end
def max_cycle_weight()
visit = Array.new(@size) {false}
# Set initial visited node status
i = 0
while (i < @size)
visit[i] = false
i += 1
end
self.result = -(2 ** (0. size * 8 - 2))
i = 0
while (i < @size)
self.maximum_cycle(i, i, visit, 0)
i += 1
end
if (@result == -(2 ** (0. size * 8 - 2)))
print("\n Max weight cycle  : None \n")
else
print("\n Max weight cycle  : ", self.result ,"\n")
end
end
end
def main()
# 5 implies the number of nodes in graph
g = MyGraph.new(5)
# 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.max_cycle_weight()
end
main()```
```

#### Output

``````Adjacency list of vertex 0  : 1
Adjacency list of vertex 1  : 2
Adjacency list of vertex 2  : 0 3 4
Adjacency list of vertex 3  : 0 4
Adjacency list of vertex 4  : 0
Max weight cycle  : 8
``````
``````// Scala Program
// Maximum weight cycle in an directed graph
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) {
//set value
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);
} 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 maximum_cycle(start: Int, end: Int, visit: Array[Boolean], sum: Int): Unit = {
if (start > size ||
end > size ||
start < 0 ||
end < 0 &&
node == null) {
return;
}
if (visit(start) == true) {
if (start == end &&
sum > result) {
//When find a new max weight cycle
result = sum;
}
return;
}
//Here modified  the value of visited node
visit(start) = true;
var temp: AjlistNode = node(start).next;
while (temp != null) {
maximum_cycle(temp.id, end, visit, sum + (temp.weight));

//visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit(start) = false;
}
def max_cycle_weight(): Unit = {
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);

//Set initial visited node status
var i: Int = 0;
while (i < size) {
visit(i) = false;
i += 1;
}
this.result = Int.MinValue;
i = 0;
while (i < size) {
maximum_cycle(i, i, visit, 0);
i += 1;
}
if (result == Int.MinValue) {
print("\n Max weight cycle : None \n");
} else {
print("\n Max weight cycle : " + this.result + "\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
//5 implies the number of nodes in graph
var g: MyGraph = new MyGraph(5);

//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.max_cycle_weight();
}
}```
```

#### Output

``````Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 0 3 4
Adjacency list of vertex 3 : 0 4
Adjacency list of vertex 4 : 0
Max weight cycle : 8``````
``````// Swift Program
// Maximum weight cycle in an directed graph
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;
}
}

func add_edge(_ start: Int, _ last: Int,_ weight: Int) {
if (start >= 0 &&
start < self.size &&
last >= 0 &&
last < self.size &&
self.node != nil) {
let newEdge: AjlistNode? = AjlistNode(last,weight);
if (self.node![start].next == nil) {
self.node![start].next = newEdge;
} else {
var temp: AjlistNode? = self.node![start].next;
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = newEdge;
}
} 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 maximum_cycle(_ start: Int, _ end: Int, _ visit: inout[Bool], _ sum: Int) {
if (start > self.size ||
end > self.size ||
start < 0 ||
end < 0 &&
self.node == nil) {
return;
}
if (visit[start] == true) {
if (start == end &&
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.maximum_cycle(temp!.id, end, &visit, sum + (temp!.weight));
//visit to next edge
temp = temp!.next;
}
// Reset the value of visited node status
visit[start] = false;
}
func max_cycle_weight() {
var visit: [Bool] = Array(repeating: false, count: self.size);
//Set initial visited node status
var i: Int = 0;
while (i < self.size) {
visit[i] = false;
i += 1;
}
self.result = Int.min;
i = 0;
while (i < self.size) {
self.maximum_cycle(i, i, &visit, 0);
i += 1;
}
if (self.result == Int.min) {
print("\n Max weight cycle : None \n", terminator: "");
} else {
print("\n Max weight cycle : ", self.result ,"\n", terminator: "");
}
}
}
func main() {
//5 implies the number of nodes in graph
let g: MyGraph? = MyGraph(5);
//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!.max_cycle_weight();
}
main();```
```

#### Output

``````Adjacency list of vertex  0  :  1
Adjacency list of vertex  1  :  2
Adjacency list of vertex  2  :  0  3  4
Adjacency list of vertex  3  :  0  4
Adjacency list of vertex  4  :  0
Max weight cycle :  8``````

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.