# Find maximum weight cycle in an undirected graph in golang

Go program for Find maximum weight cycle in an undirected graph. Here problem description and other solutions.

``````package main
import "math"
import "fmt"
/*
Go program for
Maximum weight cycle in an undirected graph
*/
type AjlistNode struct {
// Vertices node key
id int
weight int
next * AjlistNode
}
func getAjlistNode(id int, weight int) * AjlistNode {
// return new AjlistNode
return &AjlistNode {
id,
weight,
nil,
}
}
type Vertices struct {
data int
next * AjlistNode
last * AjlistNode
}
func getVertices(data int) * Vertices {
// return new Vertices
return &Vertices {
data,
nil,
nil,
}
}
type Graph struct {
// Number of Vertices
size int
result int
node []*Vertices
}
func getGraph(size int) * Graph {
// return new Graph
var me *Graph = &Graph {size,0,make([]*Vertices, size)}
me.setData()
return me
}
// Set initial node value
func(this *Graph) setData() {
if this.size <= 0 {
fmt.Println("\nEmpty Graph")
} else {
for index := 0 ; index < this.size ; index++ {
// Set initial node value
this.node[index] = getVertices(index)
}
}
}
func(this *Graph) connection(start, last, weight int) {
// Safe connection
var edge * AjlistNode = getAjlistNode(last, weight)
if this.node[start].next == nil {
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
func(this *Graph) addEdge(start, last, weight int) {
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
fmt.Println("\nHere Something Wrong")
}
}
func(this Graph) printGraph() {
if this.size > 0 {
// Print graph ajlist Node value
for index := 0 ; index < this.size ; index++ {
fmt.Print("\nAdjacency list of vertex ", index, " :")
var edge * AjlistNode = this.node[index].next
for (edge != nil) {
// Display graph node
fmt.Print("  ", this.node[edge.id].data, "[", edge.weight, "]")
// Visit to next edge
edge = edge.next
}
}
}
}
func(this *Graph) maximumCycle(
start int,
last int,
visit[] bool,
sum int) {
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
for (edge != nil) {
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
}
func(this *Graph) maxWeightCycle() {
if this.size <= 0 {
// Empty graph
return
}
// Auxiliary space which is used to store
var visit = make([] bool, this.size)
// Set initial visited node status
for i := 0 ; i < this.size ; i++ {
visit[i] = false
}
this.result = math.MinInt64
for i := 0 ; i < this.size ; i++ {
// Check cycle of node i to i
// Here initial cycle weight is zero
this.maximumCycle(i, i, visit, 0)
}
if this.result == math.MinInt64 {
fmt.Println("\nMax weight cycle : None ")
} else {
fmt.Println("\nMax weight cycle : ", this.result)
}
}
func main() {
// 6 implies the number of nodes in graph
var g * Graph = getGraph(6)
// Connect node with an edge
// First and second parameter indicate node
// Last parameter is indicate weight
// 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.