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

  // create Adjacency node
  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 {
      //Add node at last
      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);
  }
}
//Display Adjacency list of vertex
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

    add_edge(node, 0, 1, 1);
    add_edge(node, 1, 2, 2);
    add_edge(node, 2, 0, 4);
    add_edge(node, 2, 3, 3);
    add_edge(node, 2, 4, -3);
    add_edge(node, 3, 0, 2);
    add_edge(node, 3, 4, -3);
    add_edge(node, 4, 0, 4);


    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;
		}
	}
	//Add edge of two nodes
	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.add_edge(0, 1, 1);
	g.add_edge(1, 2, 2);
	g.add_edge(2, 0, 4);
	g.add_edge(2, 3, 3);
	g.add_edge(2, 4, -3);
	g.add_edge(3, 0, 2);
	g.add_edge(3, 4, -3);
	g.add_edge(4, 0, 4);
	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;
    }
  }
  //Add edge of two nodes
  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.add_edge( 0, 1, 1);
    g.add_edge( 1, 2, 2);
    g.add_edge( 2, 0, 4);
    g.add_edge( 2, 3, 3);
    g.add_edge( 2, 4, -3);
    g.add_edge( 3, 0, 2);
    g.add_edge( 3, 4, -3);
    g.add_edge( 4, 0, 4);


    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;
		}
	}
	//Add edge of two nodes
	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.add_edge(0, 1, 1);
		g.add_edge(1, 2, 2);
		g.add_edge(2, 0, 4);
		g.add_edge(2, 3, 3);
		g.add_edge(2, 4, -3);
		g.add_edge(3, 0, 2);
		g.add_edge(3, 4, -3);
		g.add_edge(4, 0, 4);
		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;
		}
	}
	//Add edge of two nodes
	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->add_edge(0, 1, 1);
	$g->add_edge(1, 2, 2);
	$g->add_edge(2, 0, 4);
	$g->add_edge(2, 3, 3);
	$g->add_edge(2, 4, -3);
	$g->add_edge(3, 0, 2);
	$g->add_edge(3, 4, -3);
	$g->add_edge(4, 0, 4);
	$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;
		}
	}

	//Add edge of two nodes
	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 {
			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.add_edge(0, 1, 1);
	g.add_edge(1, 2, 2);
	g.add_edge(2, 0, 4);
	g.add_edge(2, 3, 3);
	g.add_edge(2, 4, -3);
	g.add_edge(3, 0, 2);
	g.add_edge(3, 4, -3);
	g.add_edge(4, 0, 4);
	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.add_edge(0, 1, 1)
	g.add_edge(1, 2, 2)
	g.add_edge(2, 0, 4)
	g.add_edge(2, 3, 3)
	g.add_edge(2, 4, -3)
	g.add_edge(3, 0, 2)
	g.add_edge(3, 4, -3)
	g.add_edge(4, 0, 4)
	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_reader :id, :weight, :next
    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_reader :data, :next
    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_reader :size, :node, :result
    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
	def add_edge(start, last, weight) 
		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.add_edge(0, 1, 1)
	g.add_edge(1, 2, 2)
	g.add_edge(2, 0, 4)
	g.add_edge(2, 3, 3)
	g.add_edge(2, 4, -3)
	g.add_edge(3, 0, 2)
	g.add_edge(3, 4, -3)
	g.add_edge(4, 0, 4)
	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;
		}
	}
	//Add edge of two nodes
	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.add_edge(0, 1, 1);
		g.add_edge(1, 2, 2);
		g.add_edge(2, 0, 4);
		g.add_edge(2, 3, 3);
		g.add_edge(2, 4, -3);
		g.add_edge(3, 0, 2);
		g.add_edge(3, 4, -3);
		g.add_edge(4, 0, 4);
		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!.add_edge(0, 1, 1);
	g!.add_edge(1, 2, 2);
	g!.add_edge(2, 0, 4);
	g!.add_edge(2, 3, 3);
	g!.add_edge(2, 4, -3);
	g!.add_edge(3, 0, 2);
	g!.add_edge(3, 4, -3);
	g!.add_edge(4, 0, 4);
	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.

New Comment







© 2021, kalkicode.com, All rights reserved