List all negative cycles in directed graph

Here given code implementation process.

// C Program 
// List all negative cycles in directed graph
#include<stdio.h>

#include<stdlib.h>

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

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

struct Stack {
	int data;
	struct Stack *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");
	}
}
//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) {
		//first create Adjacency node
		struct AjlistNode *newEdge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
		if (newEdge != NULL) {

			newEdge->next = NULL;
			newEdge->vId = 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");
		}
	} 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->vId is graph node vertices
				//in this case temp->vId is same as 
				//node[temp->vId].data

				printf("  %d", node[temp->vId].data);
				temp = temp->next;
			}
		}
	} else {
		printf("Empty Graph");
	}
}
void push(struct Stack **root, int data) {
	struct Stack *element = (struct Stack *) malloc(sizeof(struct Stack));

	if (element != NULL) {
		element->data = data;
		element->next = *root;
		*root = element;
	}
}
void pop(struct Stack **root) {
	if ( *root == NULL) return; //already empty
	struct Stack *temp = *root;
	*root = temp->next;
	temp->next = NULL;
	free(temp);
	temp = NULL;
}

//Display Path from source to destination
void print_path(struct Stack *temp) {
	if (temp == NULL) {
		return;
	}
	print_path(temp->next);
	printf("%3d", temp->data);
}



void show_path(int start, int end, int visit[],
	struct Graph *node, struct Stack **output, int sum) {

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

		if (start == end && sum < 0) {
			printf("\n Cycle Pair (");
			print_path( *output);
			printf("%3d ) = %d ", end, sum);
		}

		return;
	} else {
		push(output, start);
	}
	visit[start] = 1;
	struct AjlistNode *temp = node[start].next;
	while (temp != NULL) {
		show_path(temp->vId, end, visit, node, output, sum + (temp->weight));

		temp = temp->next;
	}

	pop(output);
	visit[start] = 0;
}
void set_visit(int arr[]) {
	for (int i = 0; i < size; ++i) {
		arr[i] = 0;
	}
}
void nagative_cycle(struct Graph *node) {

	int visit[size];
	struct Stack *root = NULL;
	for (int i = 0; i < size; ++i) {
		set_visit(visit);
		show_path(i, i, visit, node, & root, 0);
		while (root != NULL) {
			pop( & root);
		}


	}

}

int main() {

	size = 4;
	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, 2, -2);
		add_edge(node, 1, 0, 4);
		add_edge(node, 1, 2, -3);
		add_edge(node, 2, 3, -2);
		add_edge(node, 3, 0, 2);
		add_edge(node, 3, 1, -1);

		print_graph(node);

		nagative_cycle(node);


	}
	return 0;
}

Output

 Adjacency list of vertex 0  :  2
 Adjacency list of vertex 1  :  0  2
 Adjacency list of vertex 2  :  3
 Adjacency list of vertex 3  :  0  1
 Cycle Pair (  0  2  3  0 ) = -2
 Cycle Pair (  0  2  3  1  0 ) = -1
 Cycle Pair (  1  0  2  3  1 ) = -1
 Cycle Pair (  1  2  3  1 ) = -6
 Cycle Pair (  2  3  0  2 ) = -2
 Cycle Pair (  2  3  1  0  2 ) = -1
 Cycle Pair (  2  3  1  2 ) = -6
 Cycle Pair (  3  0  2  3 ) = -2
 Cycle Pair (  3  1  0  2  3 ) = -1
 Cycle Pair (  3  1  2  3 ) = -6
// C++ Program
// List all negative cycles in directed graph
#include<iostream>

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 MyStack {
	public:
		int element;
	MyStack *next;
	MyStack(int element, MyStack *top) {
		this->element = element;
		this->next = top;
	}
};
class MyGraph {
	public:

		//number of Vertices
		int size;
	Vertices *node;
	MyStack *top;
	MyGraph(int size) {
		//set value
		this->size = size;
		this->top = NULL;
		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 push(int element) {
		MyStack *node = new MyStack(element, this->top);
		this->top = node;
	}
	void pop() {
		if (this->top != NULL) {
          	MyStack *temp = this->top;
			this->top = this->top->next;
          	delete(temp);
          	temp=NULL;
		}
	}
	//Display Path from source to destination
	void print_path(MyStack *temp) {
		if (temp == NULL) {
			return;
		}
		this->print_path(temp->next);
		cout << " " << temp->element;
	}
	void show_path(int start, int last, bool visit[], int sum) {
		if (start > this->size ||
			last > this->size ||
			start < 0 ||
			last < 0 &&
			this->node == NULL) {
			return;
		}
		if (visit[start] == true &&
			(start == last) &&
			sum < 0) {
			cout << "\n Cycle Pair (";
			this->print_path(this->top);
			cout << " " << last << " ) = " << sum << " ";
			return;
		} else
		if (visit[start] == true) {
			return;
		}
		//Add element into stack
		this->push(start);
		visit[start] = true;
		AjlistNode *temp = this->node[start].next;
		while (temp != NULL) {
			this->show_path(temp->id, last, visit, sum + (temp->weight));
			temp = temp->next;
		}
		this->pop();
		visit[start] = false;
	}
	//reset the visited nodes
	void set_visit(bool visit[]) {
		for (int i = 0; i < this->size; ++i) {
			visit[i] = false;
		}
	}
	void nagative_cycle() {
		bool *visit = new bool[size];
		for (int i = 0; i < this->size; ++i) {
			this->set_visit(visit);
			this->show_path(i, i, visit, 0);
			while (this->top != NULL) {
				this->pop();
			}
		}
	}
};
int main() {
	//4 implies the number of nodes in graph
	MyGraph g =  MyGraph(4);
	//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, 2, -2);
	g.add_edge(1, 0, 4);
	g.add_edge(1, 2, -3);
	g.add_edge(2, 3, -2);
	g.add_edge(3, 0, 2);
	g.add_edge(3, 1, -1);
	g.print_graph();
	g.nagative_cycle();
	return 0;
}

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
// Java Program
// List all negative cycles in 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;
  }
}
class MyStack {
  public int element;
  public MyStack next;
  public MyStack(int element,MyStack top) 
  {
    this.element = element;
    this.next = top;
  }
}

public class MyGraph
{

  //number of Vertices
  public int size;
  
  public Vertices []node;
  public MyStack top;

  public MyGraph(int size)
  {
    //set value
    this.size = size;
    this.top = null;
    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 push(int element)
  {
    MyStack node = new MyStack(element,top);

    top = node;

  }
  public void pop()
  {
    if(top != null)
    {
      top = top.next;
    }
  }
  //Display Path from source to destination
  public void print_path(MyStack temp) {
    if (temp == null) {
      return;
    }
    print_path(temp.next);
    System.out.print("  "+ temp.element);
  }
  public void show_path(int start, int last, boolean[] visit, int sum) {
    if (start > size || last > size || 
        start < 0 || last < 0 && node == null) {
      return;
    }
    if (visit[start] == true && (start == last) && sum < 0) {
    
      System.out.print("\n Cycle Pair (");
      print_path(top);
      System.out.print("  "+last+" ) = "+sum+" " );
      
      return;
    } 
    else if(visit[start]==true)
    {
      return;
    }
    //Add element into stack
    push(start);
    visit[start] = true;
    AjlistNode temp = node[start].next;
    while (temp != null) {
      show_path(temp.id, last, visit, sum + (temp.weight));
      temp = temp.next;
    }
    pop();
    visit[start] = false;
  }
  //reset the visited nodes
  public void set_visit(boolean[] visit) {
    for (int i = 0; i < size; ++i) {
      visit[i] = false;
    }
  }
  public void nagative_cycle() {
    
    boolean[] visit = new boolean[size];
    for (int i = 0; i < size; ++i) {
      set_visit(visit);
      show_path(i, i, visit, 0);
      while (this.top != null) {
        pop();
      }
    }
  } 

  public static void main(String[] args) 
  {

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

    //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, 2, -2);
    g.add_edge( 1, 0, 4);
    g.add_edge( 1, 2, -3);
    g.add_edge( 2, 3, -2);
    g.add_edge( 3, 0, 2);
    g.add_edge( 3, 1, -1);

    g.print_graph();
    g.nagative_cycle();
  }
}

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
// C# Program
// List all negative cycles in 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 MyStack {
	public int element;
	public MyStack next;
	public MyStack(int element, MyStack top) {
		this.element = element;
		this.next = top;
	}
}
public class MyGraph {
	//number of Vertices
	public int size;
	public Vertices[] node;
	public MyStack top;
	public MyGraph(int size) {
		//set value
		this.size = size;
		this.top = null;
		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 push(int element) {
		MyStack node = new MyStack(element, top);
		top = node;
	}
	public void pop() {
		if (top != null) {
			top = top.next;
		}
	}
	//Display Path from source to destination
	public void print_path(MyStack temp) {
		if (temp == null) {
			return;
		}
		print_path(temp.next);
		Console.Write(" " + temp.element);
	}
	public void show_path(int start, int last, Boolean[] visit, int sum) {
		if (start > size ||
			last > size ||
			start < 0 ||
			last < 0 &&
			node == null) {
			return;
		}
		if (visit[start] == true &&
			(start == last) &&
			sum < 0) {
			Console.Write("\n Cycle Pair (");
			print_path(top);
			Console.Write(" " + last + " ) = " + sum + " ");
			return;
		} else
		if (visit[start] == true) {
			return;
		}
		push(start);
		visit[start] = true;
		AjlistNode temp = node[start].next;
		while (temp != null) {
			show_path(temp.id, last, visit, sum + (temp.weight));
			temp = temp.next;
		}
		pop();
		visit[start] = false;
	}
	//reset the visited nodes
	public void set_visit(Boolean[] visit) {
		for (int i = 0; i < size; ++i) {
			visit[i] = false;
		}
	}
	public void nagative_cycle() {
		Boolean[] visit = new Boolean[size];
		for (int i = 0; i < size; ++i) {
			set_visit(visit);
			show_path(i, i, visit, 0);
			while (this.top != null) {
				pop();
			}
		}
	}
	public static void Main(String[] args) {
		//4 implies the number of nodes in graph
		MyGraph g = new MyGraph(4);
		g.add_edge(0, 2, -2);
		g.add_edge(1, 0, 4);
		g.add_edge(1, 2, -3);
		g.add_edge(2, 3, -2);
		g.add_edge(3, 0, 2);
		g.add_edge(3, 1, -1);
		g.print_graph();
		g.nagative_cycle();
	}
}

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
<?php
// Php Program
// List all negative cycles in 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 MyStack {
	public $element;
	public $next;

	function __construct($element, $top) {
		$this->element = $element;
		$this->next = $top;
	}
}
class MyGraph {
	//number of Vertices

	public $size;
	public $node;
	public $top;

	function __construct($size) {
		//set value
		$this->size = $size;
		$this->top = null;
		$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 push($element) {
		$node = new MyStack($element, $this->top);
		$this->top = $node;
	}
	public 	function pop() {
		if ($this->top != null) {
			$this->top = $this->top->next;
		}
	}
	//Display Path from source to destination

	public 	function print_path($temp) {
		if ($temp == null) {
			return;
		}
		$this->print_path($temp->next);
		echo(" ". $temp->element);
	}
	public 	function show_path($start, $last, & $visit, $sum) {
		if ($start > $this->size ||
			$last > $this->size ||
			$start < 0 ||
			$last < 0 &&
			$this->node == null) {
			return;
		}
		if ($visit[$start] == true &&
			($start == $last) &&
			$sum < 0) {
			echo("\n Cycle Pair (");
			$this->print_path($this->top);
			echo(" ". $last ." ) = ". $sum ." ");
			return;
		} else
		if ($visit[$start] == true) {
			return;
		}
		//Add element into stack
		$this->push($start);
		$visit[$start] = true;
		$temp = $this->node[$start]->next;
		while ($temp != null) {
			$this->show_path($temp->id, $last, $visit, $sum + ($temp->weight));
			$temp = $temp->next;
		}
		$this->pop();
		$visit[$start] = false;
	}
	//reset the visited nodes

	public 	function set_visit( & $visit) {
		for ($i = 0; $i < $this->size; ++$i) {
			$visit[$i] = false;
		}
	}
	public 	function nagative_cycle() {
		$visit = array_fill(0, $this->size, false);
		for ($i = 0; $i < $this->size; ++$i) {
			$this->set_visit($visit);
			$this->show_path($i, $i, $visit, 0);
			while ($this->top != null) {
				$this->pop();
			}
		}
	}
}

function main() {
	//4 implies the number of nodes in graph
	$g = new MyGraph(4);
	//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, 2, -2);
	$g->add_edge(1, 0, 4);
	$g->add_edge(1, 2, -3);
	$g->add_edge(2, 3, -2);
	$g->add_edge(3, 0, 2);
	$g->add_edge(3, 1, -1);
	$g->print_graph();
	$g->nagative_cycle();

}
main();

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
// Node Js Program
// List all negative cycles in directed graph
class AjlistNode {

	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 MyStack {
	constructor(element, top) {
		this.element = element;
		this.next = top;
	}
}
class MyGraph {
	constructor(size) {
		//set value
		this.size = size;
		this.top = null;
		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;
				}
			}
		}
	}
	push(element) {
		var node = new MyStack(element, this.top);
		this.top = node;
	}
	pop() {
		if (this.top != null) {
			this.top = this.top.next;
		}
	}

	//Display Path from source to destination
	print_path(temp) {
		if (temp == null) {
			return;
		}
		this.print_path(temp.next);
		process.stdout.write(" " + temp.element);
	}
	show_path(start, last, visit, sum) {
		if (start > this.size ||
			last > this.size ||
			start < 0 ||
			last < 0 &&
			this.node == null) {
			return;
		}

		if (visit[start] == true &&
			(start == last) &&
			sum < 0) {
			process.stdout.write("\n Cycle Pair (");
			this.print_path(this.top);
			process.stdout.write(" " + last + " ) = " + sum + " ");
			return;
		} else
		if (visit[start] == true) {
			return;
		}

		//Add element into stack
		this.push(start);
		visit[start] = true;
		var temp = this.node[start].next;
		while (temp != null) {
			this.show_path(temp.id, last, visit, sum + (temp.weight));
			temp = temp.next;
		}
		this.pop();
		visit[start] = false;
	}

	//reset the visited nodes
	set_visit(visit) {
		for (var i = 0; i < this.size; ++i) {
			visit[i] = false;
		}
	}
	nagative_cycle() {
		var visit = Array(this.size).fill(false);
		for (var i = 0; i < this.size; ++i) {
			this.set_visit(visit);
			this.show_path(i, i, visit, 0);
			while (this.top != null) {
				this.pop();
			}
		}
	}
}

function main(args) {
	//4 implies the number of nodes in graph
	var g = new MyGraph(4);
	//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, 2, -2);
	g.add_edge(1, 0, 4);
	g.add_edge(1, 2, -3);
	g.add_edge(2, 3, -2);
	g.add_edge(3, 0, 2);
	g.add_edge(3, 1, -1);
	g.print_graph();
	g.nagative_cycle();
}

main();

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
#  Python 3 Program
#  List all negative cycles in directed graph
class AjlistNode :
	
	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 MyStack :
	
	def __init__(self, element, top) :
		self.element = element
		self.next = top
	

class MyGraph :

	def __init__(self, size) :
		# set value
		self.size = size
		self.top = None
		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 push(self, element) :
		nodes = MyStack(element, self.top)
		self.top = nodes
	
	def pop(self) :
		if (self.top != None) :
			self.top = self.top.next
		
	
	# Display Path from source to destination
	def print_path(self, temp) :
		if (temp == None) :
			return
		
		self.print_path(temp.next)
		print(" ", temp.element, end = "")
	
	def show_path(self, start, last, visit, sum) :
		if (start > self.size or last > self.size or 
            start < 0 or last < 0 and self.node == None) :
			return
		
		if (visit[start] == True and(start == last) and sum < 0) :
			print("\n Cycle Pair (", end = "")
			self.print_path(self.top)
			print(" ", last ," ) = ", sum ," ", end = "")
			return
		elif (visit[start] == True) :
			return
		
		self.push(start)
		visit[start] = True
		temp = self.node[start].next
		while (temp != None) :
			self.show_path(temp.id, last, visit, sum + (temp.weight))
			temp = temp.next
		
		self.pop()
		visit[start] = False
	
	# reset the visited nodes
	def set_visit(self, visit) :
		i = 0
		while (i < self.size) :
			visit[i] = False
			i += 1
		
	
	def nagative_cycle(self) :
		visit = [False] * self.size
		i = 0
		while (i < self.size) :
			self.set_visit(visit)
			self.show_path(i, i, visit, 0)
			while (self.top != None) :
				self.pop()
			
			i += 1
		
	

def main() :
	g = MyGraph(4)
	g.add_edge(0, 2, -2)
	g.add_edge(1, 0, 4)
	g.add_edge(1, 2, -3)
	g.add_edge(2, 3, -2)
	g.add_edge(3, 0, 2)
	g.add_edge(3, 1, -1)
	g.print_graph()
	g.nagative_cycle()


if __name__ == "__main__":
	main()

Output

Adjacency list of vertex  0  :  2
Adjacency list of vertex  1  :  0  2
Adjacency list of vertex  2  :  3
Adjacency list of vertex  3  :  0  1
 Cycle Pair (  0  2  3  0  ) =  -2
 Cycle Pair (  0  2  3  1  0  ) =  -1
 Cycle Pair (  1  0  2  3  1  ) =  -1
 Cycle Pair (  1  2  3  1  ) =  -6
 Cycle Pair (  2  3  0  2  ) =  -2
 Cycle Pair (  2  3  1  0  2  ) =  -1
 Cycle Pair (  2  3  1  2  ) =  -6
 Cycle Pair (  3  0  2  3  ) =  -2
 Cycle Pair (  3  1  0  2  3  ) =  -1
 Cycle Pair (  3  1  2  3  ) =  -6
// Scala Program
// List all negative cycles in 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 MyStack(var element: Int,
	var next: MyStack) {


	def this(element: Int) {
		this(element,null);
	}
}
class MyGraph(var size: Int,
	var node: Array[Vertices],
		var top: MyStack) {
	def this(size: Int) {
		//set value
		this(size,Array.fill[Vertices](size)(null),null);
		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 push(element: Int): Unit = {
		var node: MyStack = new MyStack(element, top);
		top = node;
	}
	def pop(): Unit = {
		if (top != null) {
			top = top.next;
		}
	}
	//Display Path from source to destination
	def print_path(temp: MyStack): Unit = {
		if (temp == null) {
			return;
		}
		print_path(temp.next);
		print(" " + temp.element);
	}
	def show_path(start: Int, last: Int, visit: Array[Boolean], sum: Int): Unit = {
		if (start > size ||
			last > size ||
			start < 0 ||
			last < 0 &&
			node == null) {
			return;
		}
		if (visit(start) == true &&
			(start == last) &&
			sum < 0) {
			print("\n Cycle Pair (");
			print_path(top);
			print(" " + last + " ) = " + sum + " ");

			return;
		} else
		if (visit(start) == true) {
			return;
		}
		push(start);
		visit(start) = true;
		var temp: AjlistNode = node(start).next;
		while (temp != null) {
			show_path(temp.id, last, visit, sum + (temp.weight));
			temp = temp.next;
		}
		pop();
		visit(start) = false;
	}
	//reset the visited nodes
	def set_visit(visit: Array[Boolean]): Unit = {
		var i: Int = 0;
		while (i < size) {
			visit(i) = false;
			i += 1;
		}
	}
	def nagative_cycle(): Unit = {
		var visit:Array[Boolean] = Array.fill[Boolean](this.size)(false);
		var i: Int = 0;
		while (i < size) {
			set_visit(visit);
			show_path(i, i, visit, 0);
			while (this.top != null) {
				pop();
			}
			i += 1;
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		var g: MyGraph = new MyGraph(4);
		g.add_edge(0, 2, -2);
		g.add_edge(1, 0, 4);
		g.add_edge(1, 2, -3);
		g.add_edge(2, 3, -2);
		g.add_edge(3, 0, 2);
		g.add_edge(3, 1, -1);
		g.print_graph();
		g.nagative_cycle();
	}
}

Output

Adjacency list of vertex 0 : 2
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2
 Cycle Pair ( 0 2 3 1 0 ) = -1
 Cycle Pair ( 1 0 2 3 1 ) = -1
 Cycle Pair ( 1 2 3 1 ) = -6
 Cycle Pair ( 2 3 0 2 ) = -2
 Cycle Pair ( 2 3 1 0 2 ) = -1
 Cycle Pair ( 2 3 1 2 ) = -6
 Cycle Pair ( 3 0 2 3 ) = -2
 Cycle Pair ( 3 1 0 2 3 ) = -1
 Cycle Pair ( 3 1 2 3 ) = -6
// Swift Program
// List all negative cycles in 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 MyStack {
  var element: Int ;
  var next: MyStack? ;
  init(_ element: Int , _ top : MyStack? ) {
    self.element = element;
    self.next = top;
  }
}
class MyGraph {
    //number of Vertices
    var size: Int;
    var node: [Vertices]? = [Vertices]();
    var top: MyStack? ;
    init(_ size: Int) {
      //set value
      self.size = size;
      self.top = nil;
      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 push(_ element: Int) {
		let node: MyStack? = MyStack(element, self.top);
		self.top = node;
	}
	func pop() {
		if (self.top != nil) {
			self.top = self.top!.next;
		}
	}
	//Display Path from source to destination
	func print_path(_ temp: MyStack? ) {
		if (temp == nil) {
			return;
		}
		self.print_path(temp!.next);
		print(" ", temp!.element, terminator: "");
	}
	func show_path(_ start: Int, _ last: Int, _ visit: inout[Bool], _ sum: Int) {
		if (start > self.size ||
			last > self.size ||
			start < 0 ||
			last < 0 &&
			self.node == nil) {
			return;
		}
		if (visit[start] == true &&
			(start == last) &&
			sum < 0) {
			print("\n Cycle Pair (", terminator: "");
			self.print_path(self.top);
			print(" ", last ," ) = ", sum ," ", terminator: "");
			return;
		} else
		if (visit[start] == true) {
			return;
		}
		self.push(start);
		visit[start] = true;
		var temp: AjlistNode? = self.node![start].next;
		while (temp != nil) {
			self.show_path(temp!.id, last, &visit, sum + (temp!.weight));
			temp = temp!.next;
		}
		self.pop();
		visit[start] = false;
	}
	//reset the visited nodes
	func set_visit(_ visit: inout[Bool]) {
		var i: Int = 0;
		while (i < self.size) {
			visit[i] = false;
			i += 1;
		}
	}
	func nagative_cycle() {
		var visit: [Bool] = Array(repeating: false, count: self.size);
		var i: Int = 0;
		while (i < self.size) {
			self.set_visit(&visit);
			self.show_path(i, i, &visit, 0);
			while (self.top != nil) {
				self.pop();
			}
			i += 1;
		}
	}
}
func main() {
	let g: MyGraph? = MyGraph(4);
	g!.add_edge(0, 2, -2);
	g!.add_edge(1, 0, 4);
	g!.add_edge(1, 2, -3);
	g!.add_edge(2, 3, -2);
	g!.add_edge(3, 0, 2);
	g!.add_edge(3, 1, -1);
	g!.print_graph();
	g!.nagative_cycle();
}
main();

Output

Adjacency list of vertex  0  :  2
Adjacency list of vertex  1  :  0  2
Adjacency list of vertex  2  :  3
Adjacency list of vertex  3  :  0  1
 Cycle Pair (  0  2  3  0  ) =  -2
 Cycle Pair (  0  2  3  1  0  ) =  -1
 Cycle Pair (  1  0  2  3  1  ) =  -1
 Cycle Pair (  1  2  3  1  ) =  -6
 Cycle Pair (  2  3  0  2  ) =  -2
 Cycle Pair (  2  3  1  0  2  ) =  -1
 Cycle Pair (  2  3  1  2  ) =  -6
 Cycle Pair (  3  0  2  3  ) =  -2
 Cycle Pair (  3  1  0  2  3  ) =  -1
 Cycle Pair (  3  1  2  3  ) =  -6
#  Ruby Program
#  List all negative cycles in directed graph
class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :weight, :next
    attr_accessor :id, :weight, :next 


	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 MyStack
    # Define the accessor and reader of class MyStack
    attr_reader :element, :next
    attr_accessor :element, :next 
	
	def initialize(element, top) 
		self.element = element
		self.next = top
	end
end
class MyGraph
    # Define the accessor and reader of class MyGraph
    attr_reader :size, :node, :top
    attr_accessor :size, :node, :top 
	
	
	def initialize(size) 
		# set value
		self.size = size
		self.top = nil
		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 push(element) 
		node = MyStack.new(element, @top)
		@top = node
	end
	def pop() 
		if (@top != nil) 
			@top = @top.next
		end
	end
	# Display Path from source to destination
	def print_path(temp) 
		if (temp == nil) 
			return
		end
		self.print_path(temp.next)
		print(" ", temp.element)
	end
	def show_path(start, last, visit, sum) 
		if (start > @size ||
			last > @size ||
			start < 0 ||
			last < 0 &&
			@node == nil) 
			return
		end
		if (visit[start] == true &&
			(start == last) &&
			sum < 0) 
			print("\n Cycle Pair (")
			self.print_path(@top)
			print(" ", last ," ) = ", sum ," ")
			return
		elsif (visit[start] == true) 
			return
		end
		self.push(start)
		visit[start] = true
		temp = @node[start].next
		while (temp != nil) 
			self.show_path(temp.id, last, visit, sum + (temp.weight))
			temp = temp.next
		end
		self.pop()
		visit[start] = false
	end
	# reset the visited nodes
	def set_visit(visit) 
		i = 0
		while (i < @size) 
			visit[i] = false
			i += 1
		end
	end
	def nagative_cycle() 
		visit = Array.new(@size) {false}
		i = 0
		while (i < @size) 
			self.set_visit(visit)
			self.show_path(i, i, visit, 0)
			while (self.top != nil) 
				self.pop()
			end
			i += 1
		end
	end
end
def main() 
	g = MyGraph.new(4)
	g.add_edge(0, 2, -2)
	g.add_edge(1, 0, 4)
	g.add_edge(1, 2, -3)
	g.add_edge(2, 3, -2)
	g.add_edge(3, 0, 2)
	g.add_edge(3, 1, -1)
	g.print_graph()
	g.nagative_cycle()
end
main()

Output

Adjacency list of vertex 0  : 2
Adjacency list of vertex 1  : 0 2
Adjacency list of vertex 2  : 3
Adjacency list of vertex 3  : 0 1
 Cycle Pair ( 0 2 3 0 ) = -2 
 Cycle Pair ( 0 2 3 1 0 ) = -1 
 Cycle Pair ( 1 0 2 3 1 ) = -1 
 Cycle Pair ( 1 2 3 1 ) = -6 
 Cycle Pair ( 2 3 0 2 ) = -2 
 Cycle Pair ( 2 3 1 0 2 ) = -1 
 Cycle Pair ( 2 3 1 2 ) = -6 
 Cycle Pair ( 3 0 2 3 ) = -2 
 Cycle Pair ( 3 1 0 2 3 ) = -1 
 Cycle Pair ( 3 1 2 3 ) = -6 


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