Skip to main content

Find maximum weight cycle in an undirected graph in kotlin

Kotlin program for Find maximum weight cycle in an undirected graph. Here problem description and explanation.

/*
    Kotlin program for 
    Maximum weight cycle in an undirected graph
*/
class AjlistNode
{
	// Vertices node key
	var id: Int;
	var weight: Int;
	var next: AjlistNode ? ;
	constructor(id: Int, weight: Int)
	{
		// Set value of node key
		this.id = id;
		this.weight = weight;
		this.next = null;
	}
}
class Vertices
{
	var data: Int;
	var next: AjlistNode ? ;
	var last: AjlistNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
		this.last = null;
	}
}
class Graph
{
	// Number of Vertices
	var size: Int;
	var result: Int;
	var node: Array < Vertices ? > ;
	constructor(size: Int)
	{
		// Set value
		this.size = size;
		this.result = 0;
		this.node = Array(size)
		{
			null
		};
		this.setData();
	}
	// Set initial node value
	fun setData(): Unit
	{
		if (this.size <= 0)
		{
			println("\nEmpty Graph");
		}
		else
		{
			var index: Int = 0;
			while (index < this.size)
			{
				// Set initial node value
				this.node[index] = Vertices(index);
				index += 1;
			}
		}
	}
	fun connection(start: Int, last: Int, weight: Int): Unit
	{
		// Safe connection
		var edge: AjlistNode ? = AjlistNode(last, weight);
		if (this.node[start]?.next == null)
		{
			this.node[start]?.next = edge;
		}
		else
		{
			// Add edge at the end
			this.node[start]?.last?.next = edge;
		}
		// Get last edge 
		this.node[start]?.last = edge;
	}
	//  Handling the request of adding new edge
	fun addEdge(start: Int, last: Int, weight: Int): Unit
	{
		if (start >= 0 && start < this.size && 
            last >= 0 && last < this.size)
		{
			this.connection(start, last, weight);
			if (start == last)
			{
				return;
			}
			this.connection(last, start, weight);
		}
		else
		{
			// When invalid nodes
			println("\nHere Something Wrong");
		}
	}
	fun printGraph(): Unit
	{
		if (this.size > 0)
		{
			var index: Int = 0;
			// Print graph ajlist Node value
			while (index < this.size)
			{
				print("\nAdjacency list of vertex " + index + " :");
				var edge: AjlistNode ? = this.node[index]?.next;
				while (edge != null)
				{
					// Display graph node 
					print("  " + this.node[edge.id]?.data + "[" + 
                      edge.weight + "]");
					// Visit to next edge
					edge = edge.next;
				}
				index += 1;
			}
		}
	}
	fun maximumCycle(start: Int, last: Int, visit: Array < Boolean > , sum: Int): Unit
	{
		if (start >= this.size || last >= this.size || 
            start < 0 || last < 0 || this.size <= 0)
		{
			return;
		}
		if (visit[start] == true)
		{
			if (start == last && 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 edge: AjlistNode ? = this.node[start]?.next;
		while (edge != null)
		{
			this.maximumCycle(edge.id, last, 
          visit, sum + (edge.weight));
			// Visit to next edge
			edge = edge.next;
		}
		// Reset the value of visited node status
		visit[start] = false;
	}
	fun maxWeightCycle(): Unit
	{
		if (this.size <= 0)
		{
			// Empty graph
			return;
		}
		// Auxiliary space which is used to store 
		// information about visited node
		val visit: Array < Boolean > = Array(this.size)
		{
			false
		};
		this.result = Int.MIN_VALUE;
		var i: Int = 0;
		while (i < this.size)
		{
			// Check cycle of node i to i
			// Here initial cycle weight is zero
			this.maximumCycle(i, i, visit, 0);
			i += 1;
		}
		if (this.result == Int.MIN_VALUE)
		{
			println("\nMax weight cycle : None ");
		}
		else
		{
			println("\nMax weight cycle : " + this.result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// 6 implies the number of nodes in graph
	val g: Graph = Graph(6);
	// Connect node with an edge
	// First and second parameter indicate node
	// Last parameter is indicate weight
	g.addEdge(0, 1, 3);
	g.addEdge(0, 3, -3);
	g.addEdge(0, 4, 7);
	g.addEdge(0, 5, 1);
	g.addEdge(1, 2, 11);
	g.addEdge(1, 4, 8);
	g.addEdge(1, 5, 0);
	g.addEdge(2, 3, 1);
	g.addEdge(2, 5, 5);
	g.addEdge(3, 4, 2);
	g.addEdge(4, 5, 8);
	// Print graph element
	g.printGraph();
	// Test
	g.maxWeightCycle();
}

Output

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




Comment

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

New Comment