Skip to main content

Find a universal sink of a given directed graph

Here given code implementation process.

//C Program 
//Find the universal sink of a given directed graph
#include<stdio.h>

#include<stdlib.h>

struct AjlistNode {
	int vId; //Vertices id
	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) {

	// create Adjacency node
	struct AjlistNode *newEdge = (struct AjlistNode *) malloc(
		sizeof(struct AjlistNode)
	);
	if (newEdge != NULL) {

		newEdge->next = NULL;
		newEdge->vId = E;

		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");
		exit(0);
	}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph *node, int V, int E) {

	if (V < size && E < size) {

		connect_edge(node, V, E);

	} 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");
	}
}
int check_edges(struct Graph *node, int location) {
	if (location == -1) {
		return -1;
	}

	int status = -1;

	struct AjlistNode *temp = NULL;
	for (int i = 0; i < size; ++i) {
		if (i != location) {
			temp = node[i].next;
			status = -1;
			while (temp != NULL) {
				if (temp->vId == location) {
					status = 1;
					break;
				}
				temp = temp->next;
			}
			if (status == -1) {
				break;
			}
		}
	}
	return status;
}

void sink_node(struct Graph *node) {

	if (node != NULL) {

		struct AjlistNode *temp = NULL;

		for (int index = 0; index < size; index++) {
			if (check_edges(node, index) != -1) {

				printf("\n Sink Node is %d \n", index);
				return;
			}
		}
		printf("\n No Sink Node Found \n");

	} else {
		printf("Empty Graph");
	}

}

int main() {

	size = 6;

	struct Graph *g1 = (struct Graph *) malloc(
		sizeof(struct Graph) *size
	);

	if (g1 == NULL) {
		printf("\n Memory overflow");
	} else {
		//First set node keys
		set_data(g1);
		//Connected two node with Edges
		add_edge(g1, 0, 1);
		add_edge(g1, 0, 5);
		add_edge(g1, 1, 5);
		add_edge(g1, 2, 1);
		add_edge(g1, 2, 5);
		add_edge(g1, 3, 5);
		add_edge(g1, 4, 5);
		print_graph(g1);
		sink_node(g1);
	}

	size = 7;

	struct Graph *g2 = (struct Graph *) malloc(
		sizeof(struct Graph) *size
	);
	if (g2 == NULL) {
		printf("\n Memory overflow");
	} else {
		//First set node keys
		set_data(g2);
		//Connected two node with Edges
		add_edge(g2, 0, 1);
		add_edge(g2, 1, 5);
		add_edge(g2, 1, 6);
		add_edge(g2, 2, 4);
		add_edge(g2, 2, 1);
		add_edge(g2, 3, 1);
		add_edge(g2, 4, 1);
		add_edge(g2, 4, 4);
		add_edge(g2, 5, 1);
		add_edge(g2, 6, 0);
		add_edge(g2, 6, 1);
		print_graph(g2);
		sink_node(g2);
	}

	return 0;
}

Output

 Adjacency list of vertex 0  :  1  5
 Adjacency list of vertex 1  :  5
 Adjacency list of vertex 2  :  1  5
 Adjacency list of vertex 3  :  5
 Adjacency list of vertex 4  :  5
 Adjacency list of vertex 5  :
 Sink Node is 5

 Adjacency list of vertex 0  :  1
 Adjacency list of vertex 1  :  5  6
 Adjacency list of vertex 2  :  4  1
 Adjacency list of vertex 3  :  1
 Adjacency list of vertex 4  :  1  4
 Adjacency list of vertex 5  :  1
 Adjacency list of vertex 6  :  0  1
 Sink Node is 1
//C++ Program
//Find a universal sink of a given directed graph
#include<iostream>

using namespace std;
class AjlistNode {
	public:

		//Vertices node key
		int id;
	AjlistNode *next;
	AjlistNode(int value) {
		//Set value of node key
		this->id = value;
		this->next = NULL;
	}
};
class Vertices {
	public:
	int data;
	AjlistNode *next;
    Vertices()
    {
      this->data = 0;
      this->next = NULL;
    }
	Vertices(int value) {
		this->data = value;
		this->next = NULL;
	}
};
class MyGraph {
	public:

	//number of Vertices
	int size;
	Vertices *node;
	MyGraph(int size) {
		//Set value
		this->size = size;
		node = new Vertices[size];
		this->set_data();
	}
	//Set initial node value
	void set_data() {
		if (node == NULL) {
			cout << "\nEmpty Graph";
		} else {
			for (int index = 0; index < this->size; index++) {
				node[index] = index;
			}
		}
	}
	void add_edge(int start, int last) {
		if (start >= 0 &&
			start < this->size &&
			last >= 0 &&
			last < this->size &&
			node != NULL) {
			AjlistNode *newEdge = new AjlistNode(last);
			if (node[start].next == NULL) {
				node[start].next = newEdge;
			} else {
				AjlistNode *temp = node[start].next;
				while (temp->next != NULL) {
					temp = temp->next;
				}
				temp->next = newEdge;
			}
		} else {
			cout << "\nHere Something Wrong";
		}
	}
	int check_edges(int location) {
		if (location == -1) {
			return -1;
		}
		int status = -1;
		AjlistNode *temp = NULL;
		for (int i = 0; i < this->size; ++i) {
			if (i != location) {
				temp = node[i].next;
				status = -1;
				while (temp != NULL) {
					if (temp->id == location) {
						status = 1;
						break;
					}
					temp = temp->next;
				}
				if (status == -1) {
					break;
				}
			}
		}
		return status;
	}
	void sink_node() {
		if (node != NULL) {
			AjlistNode *temp = NULL;
			for (int index = 0; index < this->size; index++) {
				if (this->check_edges(index) != -1) {
					//When find a sink node

					cout << "\n Sink Node is " << index << " \n";
					return;
				}
			}
			cout << "\n No Sink Node Found \n";
		} else {
			cout << "Empty Graph";
		}
	}
	void print_graph() {
		if (this->size > 0 &&
			node != NULL) {
			for (int index = 0; index < this->size; index++) {
				cout << "\nAdjacency list of vertex " << index << " :";
				AjlistNode *temp = node[index].next;
				while (temp != NULL) {
					cout << " " << node[temp->id].data;
					temp = temp->next;
				}
			}
		}
	}
};
int main() {
	MyGraph g1 =  MyGraph(6);
	g1.add_edge(0, 1);
	g1.add_edge(0, 5);
	g1.add_edge(1, 5);
	g1.add_edge(2, 1);
	g1.add_edge(2, 5);
	g1.add_edge(3, 5);
	g1.add_edge(4, 5);
	g1.print_graph();
	g1.sink_node();
	MyGraph g2 =  MyGraph(7);
	//Connected two node with Edges
	g2.add_edge(0, 1);
	g2.add_edge(1, 5);
	g2.add_edge(1, 6);
	g2.add_edge(2, 4);
	g2.add_edge(2, 1);
	g2.add_edge(3, 1);
	g2.add_edge(4, 1);
	g2.add_edge(4, 4);
	g2.add_edge(5, 1);
	g2.add_edge(6, 0);
	g2.add_edge(6, 1);
	g2.print_graph();
	g2.sink_node();
	return 0;
}

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 5
Adjacency list of vertex 2 : 1 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
 Sink Node is 5

Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 5 6
Adjacency list of vertex 2 : 4 1
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 4
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 0 1
 Sink Node is 1
//Java Program
//Find a universal sink of a given directed graph

class AjlistNode {
	//Vertices node key
	public int id;
	public AjlistNode next;

	public AjlistNode(int value) {
		//Set value of node key
		id = value;
		next = null;
	}
}
class Vertices {

	public int data;
	public AjlistNode next;

	public Vertices(int value) {
		data = value;
		next = null;
	}
}


public class MyGraph {

	//number of Vertices
	public int size;

	public Vertices node[];

	public MyGraph(int size) {
		//Set value
		this.size = size;
		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);
			}
		}
	}

	public void add_edge(int start, int last) {
		if (start >= 0 && start < size && last >= 0 && last < size && node != null) {
			AjlistNode newEdge = new AjlistNode(last);

			if (node[start].next == null) {
				node[start].next = newEdge;
			} else {
				AjlistNode temp = node[start].next;
				while (temp.next != null) {
					temp = temp.next;
				}
				temp.next = newEdge;
			}
		} else {
			System.out.println("\nHere Something Wrong");
		}
	}
	public int check_edges(int location) {
		if (location == -1) {
			return -1;
		}

		int status = -1;

		AjlistNode temp = null;
		for (int i = 0; i < size; ++i) {
			if (i != location) {
				temp = node[i].next;
				status = -1;
				while (temp != null) {
					if (temp.id == location) {
						status = 1;
						break;
					}
					temp = temp.next;
				}
				if (status == -1) {
					break;
				}
			}
		}
		return status;
	}

	public void sink_node() {

		if (node != null) {

			AjlistNode temp = null;

			for (int index = 0; index < size; index++) {
				if (check_edges(index) != -1) {
					//When find a sink node
					System.out.print("\n Sink Node is " + index + " \n");
					return;
				}
			}
			System.out.print("\n No Sink Node Found \n");

		} else {
			System.out.print("Empty Graph");
		}
	}
	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 static void main(String[] args) {

		MyGraph g1 = new MyGraph(6);

		g1.add_edge(0, 1);
		g1.add_edge(0, 5);
		g1.add_edge(1, 5);
		g1.add_edge(2, 1);
		g1.add_edge(2, 5);
		g1.add_edge(3, 5);
		g1.add_edge(4, 5);

		g1.print_graph();
		g1.sink_node();

		MyGraph g2 = new MyGraph(7);
		//Connected two node with Edges
		g2.add_edge(0, 1);
		g2.add_edge(1, 5);
		g2.add_edge(1, 6);
		g2.add_edge(2, 4);
		g2.add_edge(2, 1);
		g2.add_edge(3, 1);
		g2.add_edge(4, 1);
		g2.add_edge(4, 4);
		g2.add_edge(5, 1);
		g2.add_edge(6, 0);
		g2.add_edge(6, 1);
		g2.print_graph();
		g2.sink_node();

	}
}

Output

Adjacency list of vertex  0  : 1  5
Adjacency list of vertex  1  : 5
Adjacency list of vertex  2  : 1  5
Adjacency list of vertex  3  : 5
Adjacency list of vertex  4  : 5
Adjacency list of vertex  5  :
 Sink Node is  5

Adjacency list of vertex  0  : 1
Adjacency list of vertex  1  : 5  6
Adjacency list of vertex  2  : 4  1
Adjacency list of vertex  3  : 1
Adjacency list of vertex  4  : 1  4
Adjacency list of vertex  5  : 1
Adjacency list of vertex  6  : 0  1
 Sink Node is  1
<?php
//Php Program
//Find a universal sink of a given directed graph
class AjlistNode {
	//Vertices node key
	public $id;
	public $next;

	function __construct($value) {
		//Set value of node key
		$this->id = $value;
		$this->next = null;
	}
}
class Vertices {
	public $data;
	public $next;

	function __construct($value) {
		$this->data = $value;
		$this->next = null;
	}
}
class MyGraph {
	//number of Vertices
	public $size;
	public $node;

	function __construct($size) {
		//Set value
		$this->size = $size;
		$this->node = array_fill(0, $size, null);
		$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);
			}
		}
	}
	public 	function add_edge($start, $last) {
		if ($start >= 0 &&
			$start < $this->size &&
			$last >= 0 &&
			$last < $this->size &&
			$this->node != null) {
			$newEdge = new AjlistNode($last);
			if ($this->node[$start]->next == null) {
				$this->node[$start]->next = $newEdge;
			} else {
				$temp = $this->node[$start]->next;
				while ($temp->next != null) {
					$temp = $temp->next;
				}
				$temp->next = $newEdge;
			}
		} else {
			echo("\nHere Something Wrong");
		}
	}
	public 	function check_edges($location) {
		if ($location == -1) {
			return -1;
		}
		$status = -1;
		$temp = null;
		for ($i = 0; $i < $this->size; ++$i) {
			if ($i != $location) {
				$temp = $this->node[$i]->next;
				$status = -1;
				while ($temp != null) {
					if ($temp->id == $location) {
						$status = 1;
						break;
					}
					$temp = $temp->next;
				}
				if ($status == -1) {
					break;
				}
			}
		}
		return $status;
	}
	public 	function sink_node() {
		if ($this->node != null) {
			$temp = null;
			for ($index = 0; $index < $this->size; $index++) {
				if ($this->check_edges($index) != -1) {
					//When find a sink node

					echo("\n Sink Node is ". $index ." \n");
					return;
				}
			}
			echo("\n No Sink Node Found \n");
		} else {
			echo("Empty Graph");
		}
	}
	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;
				}
			}
		}
	}
}

function main() {
	$g1 = new MyGraph(6);
	$g1->add_edge(0, 1);
	$g1->add_edge(0, 5);
	$g1->add_edge(1, 5);
	$g1->add_edge(2, 1);
	$g1->add_edge(2, 5);
	$g1->add_edge(3, 5);
	$g1->add_edge(4, 5);
	$g1->print_graph();
	$g1->sink_node();
	$g2 = new MyGraph(7);
	//Connected two node with Edges
	$g2->add_edge(0, 1);
	$g2->add_edge(1, 5);
	$g2->add_edge(1, 6);
	$g2->add_edge(2, 4);
	$g2->add_edge(2, 1);
	$g2->add_edge(3, 1);
	$g2->add_edge(4, 1);
	$g2->add_edge(4, 4);
	$g2->add_edge(5, 1);
	$g2->add_edge(6, 0);
	$g2->add_edge(6, 1);
	$g2->print_graph();
	$g2->sink_node();

}
main();

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 5
Adjacency list of vertex 2 : 1 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
 Sink Node is 5

Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 5 6
Adjacency list of vertex 2 : 4 1
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 4
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 0 1
 Sink Node is 1
//Node Js Program
//Find a universal sink of a given directed graph
class AjlistNode {
	constructor(value) {
		//Set value of node key
		this.id = value;
		this.next = null;
	}
}
class Vertices {
	constructor(value) {
		this.data = value;
		this.next = null;
	}
}
class MyGraph {
	constructor(size) {
		//Set value
		this.size = size;
		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);
			}
		}
	}
	add_edge(start, last) {
		if (start >= 0 &&
			start < this.size &&
			last >= 0 &&
			last < this.size &&
			this.node != null) {
			var newEdge = new AjlistNode(last);
			if (this.node[start].next == null) {
				this.node[start].next = newEdge;
			} else {
				var temp = this.node[start].next;
				while (temp.next != null) {
					temp = temp.next;
				}
				temp.next = newEdge;
			}
		} else {
			process.stdout.write("\nHere Something Wrong");
		}
	}
	check_edges(location) {
		if (location == -1) {
			return -1;
		}
		var status = -1;
		var temp = null;
		for (var i = 0; i < this.size; ++i) {
			if (i != location) {
				temp = this.node[i].next;
				status = -1;
				while (temp != null) {
					if (temp.id == location) {
						status = 1;
						break;
					}
					temp = temp.next;
				}

				if (status == -1) {
					break;
				}
			}
		}

		return status;
	}
	sink_node() {
		if (this.node != null) {
			var temp = null;
			for (var index = 0; index < this.size; index++) {
				if (this.check_edges(index) != -1) {
					//When find a sink node

					process.stdout.write("\n Sink Node is " + index + " \n");
					return;
				}
			}

			process.stdout.write("\n No Sink Node Found \n");
		} else {
			process.stdout.write("Empty Graph");
		}
	}
	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;
				}
			}
		}
	}
}

function main(args) {
	var g1 = new MyGraph(6);
	g1.add_edge(0, 1);
	g1.add_edge(0, 5);
	g1.add_edge(1, 5);
	g1.add_edge(2, 1);
	g1.add_edge(2, 5);
	g1.add_edge(3, 5);
	g1.add_edge(4, 5);
	g1.print_graph();
	g1.sink_node();
	var g2 = new MyGraph(7);
  
	//Connected two node with Edges
	g2.add_edge(0, 1);
	g2.add_edge(1, 5);
	g2.add_edge(1, 6);
	g2.add_edge(2, 4);
	g2.add_edge(2, 1);
	g2.add_edge(3, 1);
	g2.add_edge(4, 1);
	g2.add_edge(4, 4);
	g2.add_edge(5, 1);
	g2.add_edge(6, 0);
	g2.add_edge(6, 1);
	g2.print_graph();
	g2.sink_node();
}

main();

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 5
Adjacency list of vertex 2 : 1 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
 Sink Node is 5

Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 5 6
Adjacency list of vertex 2 : 4 1
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 4
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 0 1
 Sink Node is 1
# Python 3 Program
# Find a universal sink of a given directed graph

class AjlistNode :
	# Vertices node key 
	def __init__(self, value) :
		# Set value of node key
		self.id = value
		self.next = None
	

class Vertices :
	
	def __init__(self, value) :
		self.data = value
		self.next = None
	

class MyGraph :
	# number of Vertices 
	def __init__(self, size) :
		# Set value
		self.size = size
		self.node = [None] * 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
			
		
	
	def add_edge(self, start, last) :
		if (start >= 0 and start < self.size and last >= 0 and last < self.size and self.node != None) :
			newEdge = AjlistNode(last)
			if (self.node[start].next == None) :
				self.node[start].next = newEdge
			else :
				temp = self.node[start].next
				while (temp.next != None) :
					temp = temp.next
				
				temp.next = newEdge
			
		else :
			print("\nHere Something Wrong", end = "")
		
	
	def check_edges(self, location) :
		if (location == -1) :
			return -1
		
		status = -1
		temp = None
		i = 0
		while (i < self.size) :
			if (i != location) :
				temp = self.node[i].next
				status = -1
				while (temp != None) :
					if (temp.id == location) :
						status = 1
						break
					
					temp = temp.next
				
				if (status == -1) :
					break
				
			
			i += 1
		
		return status
	
	def sink_node(self) :
		if (self.node != None) :
			temp = None
			index = 0
			while (index < self.size) :
				if (self.check_edges(index) != -1) :
					print("\n Sink Node is ", index ," \n", end = "")
					return
				
				index += 1
			
			print("\n No Sink Node Found \n", end = "")
		else :
			print("Empty Graph", 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 main() :
	#  First graph 
	g1 = MyGraph(6)
	g1.add_edge(0, 1)
	g1.add_edge(0, 5)
	g1.add_edge(1, 5)
	g1.add_edge(2, 1)
	g1.add_edge(2, 5)
	g1.add_edge(3, 5)
	g1.add_edge(4, 5)
	g1.print_graph()
	g1.sink_node() 
	#  Second graph 
	g2 = MyGraph(7)
	g2.add_edge(0, 1)
	g2.add_edge(1, 5)
	g2.add_edge(1, 6)
	g2.add_edge(2, 4)
	g2.add_edge(2, 1)
	g2.add_edge(3, 1)
	g2.add_edge(4, 1)
	g2.add_edge(4, 4)
	g2.add_edge(5, 1)
	g2.add_edge(6, 0)
	g2.add_edge(6, 1)
	g2.print_graph()
	g2.sink_node()


if __name__ == "__main__":
	main()

Output

Adjacency list of vertex  0  :  1  5
Adjacency list of vertex  1  :  5
Adjacency list of vertex  2  :  1  5
Adjacency list of vertex  3  :  5
Adjacency list of vertex  4  :  5
Adjacency list of vertex  5  :
 Sink Node is  5

Adjacency list of vertex  0  :  1
Adjacency list of vertex  1  :  5  6
Adjacency list of vertex  2  :  4  1
Adjacency list of vertex  3  :  1
Adjacency list of vertex  4  :  1  4
Adjacency list of vertex  5  :  1
Adjacency list of vertex  6  :  0  1
 Sink Node is  1
# Ruby Program
# Find a universal sink of a given directed graph

class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :next
    attr_accessor :id, :next 
	# Vertices node key 
	def initialize(value) 
		# Set value of node key
		@id = value
		@next = nil
	end
end
class Vertices
    # Define the accessor and reader of class Vertices
    attr_reader :data, :next
    attr_accessor :data, :next 

	def initialize(value) 
		@data = value
		@next = nil
	end
end
class MyGraph
    # Define the accessor and reader of class MyGraph
    attr_reader :size, :node
    attr_accessor :size, :node 
	# number of Vertices 
	def initialize(size) 
		# Set value
		self.size = size
		@node = Array.new(size) {nil}
		self.set_data()
	end 
	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
	def add_edge(start, last) 
		if (start >= 0 &&
			start < @size &&
			last >= 0 &&
			last < @size &&
			@node != nil) 
			newEdge = AjlistNode.new(last)
			if (@node[start].next == nil) 
				@node[start].next = newEdge
			else 
				temp = @node[start].next
				while (temp.next != nil) 
					temp = temp.next
				end
				temp.next = newEdge
			end
		else 
			print("\nHere Something Wrong")
		end
	end
	def check_edges(location) 
		if (location == -1) 
			return -1
		end
		status = -1
		temp = nil
		i = 0
		while (i < @size) 
			if (i != location) 
				temp = @node[i].next
				status = -1
				while (temp != nil) 
					if (temp.id == location) 
						status = 1
						break
					end
					temp = temp.next
				end
				if (status == -1) 
					break
				end
			end
			i += 1
		end
		return status
	end
	def sink_node() 
		if (@node != nil) 
			temp = nil
			index = 0
			while (index < @size) 
				if (self.check_edges(index) != -1) 
					print("\n Sink Node is ", index ," \n")
					return
				end
				index += 1
			end
			print("\n No Sink Node Found \n")
		else 
			print("Empty Graph")
		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
end
def main() 
	#  First graph 
	g1 = MyGraph.new(6)
	g1.add_edge(0, 1)
	g1.add_edge(0, 5)
	g1.add_edge(1, 5)
	g1.add_edge(2, 1)
	g1.add_edge(2, 5)
	g1.add_edge(3, 5)
	g1.add_edge(4, 5)
	g1.print_graph()
	g1.sink_node() 
	#  Second graph 
	g2 = MyGraph.new(7)
	g2.add_edge(0, 1)
	g2.add_edge(1, 5)
	g2.add_edge(1, 6)
	g2.add_edge(2, 4)
	g2.add_edge(2, 1)
	g2.add_edge(3, 1)
	g2.add_edge(4, 1)
	g2.add_edge(4, 4)
	g2.add_edge(5, 1)
	g2.add_edge(6, 0)
	g2.add_edge(6, 1)
	g2.print_graph()
	g2.sink_node()
end
main()

Output

Adjacency list of vertex 0  : 1 5
Adjacency list of vertex 1  : 5
Adjacency list of vertex 2  : 1 5
Adjacency list of vertex 3  : 5
Adjacency list of vertex 4  : 5
Adjacency list of vertex 5  :
 Sink Node is 5 

Adjacency list of vertex 0  : 1
Adjacency list of vertex 1  : 5 6
Adjacency list of vertex 2  : 4 1
Adjacency list of vertex 3  : 1
Adjacency list of vertex 4  : 1 4
Adjacency list of vertex 5  : 1
Adjacency list of vertex 6  : 0 1
 Sink Node is 1 
/*Scala Program
Find a universal sink of a given directed graph*/
class AjlistNode(var id: Int,
	var next: AjlistNode) {
	def this(id: Int) {
		//Set value of node
		this(id,null);
	}
}
class Vertices(var data: Int,
	var next: AjlistNode) {


	def this(data: Int) {
		this(data,null);
	}
}
class MyGraph(var size: Int,
	var node: Array[Vertices]) {
	
	def this(size: Int) {
		//set value
        this(size,Array.fill[Vertices](size)(null));
		//set initial values of graph node
		this.set_data();
	}
	//Set initial node value
	def set_data(): Unit = {
		if (this.node == null) {
			print("\nEmpty Graph");
		} else {
			var index: Int = 0;
			while (index < this.size) {
				this.node(index) = new Vertices(index);
				index += 1;
			}
		}
	}
	def add_edge(start: Int, last: Int): Unit = {
		if (start >= 0 &&
			start < this.size &&
			last >= 0 &&
			last < this.size &&
			this.node != null) {
			var newEdge: AjlistNode = new AjlistNode(last);

			if (this.node(start).next == null) {
				this.node(start).next = newEdge;
			} else {
				var temp: AjlistNode = this.node(start).next;
				while (temp.next != null) {
					temp = temp.next;
				}
				temp.next = newEdge;
			}
		} else {
			print("\nHere Something Wrong");
		}
	}
	def check_edges(location: Int): Int = {
		if (location == -1) {
			return -1;
		}
		var status: Int = -1;
		var temp: AjlistNode = null;
		var i: Int = 0;
		while (i < this.size) {
			if (i != location) {
				temp = this.node(i).next;
				status = -1;
				while (temp != null && status == -1) {
					if (temp.id == location) {
						status = 1;
					}
					temp = temp.next;
				}
				if (status == -1) {
					return -1;
				}
			}
			i += 1;
		}
		return status;
	}
	def sink_node(): Unit = {
		if (this.node != null) {
			var temp: AjlistNode = null;
			var index: Int = 0;
			while (index < this.size) {
				if (check_edges(index) != -1) {
					print("\n Sink Node is " + index + " \n");

					return;
				}
				index += 1;
			}
			print("\n No Sink Node Found \n");
		} else {
			print("Empty Graph");
		}
	}
	def print_graph(): Unit = {
		if (this.size > 0 &&
			this.node != null) {
			var index: Int = 0;
			while (index < this.size) {
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode = this.node(index).next;
				while (temp != null) {
					print(" " + this.node(temp.id).data);
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		// First graph 
		var g1: MyGraph = new MyGraph(6);
		g1.add_edge(0, 1);
		g1.add_edge(0, 5);
		g1.add_edge(1, 5);
		g1.add_edge(2, 1);
		g1.add_edge(2, 5);
		g1.add_edge(3, 5);
		g1.add_edge(4, 5);
		g1.print_graph();
		g1.sink_node();

		// Second graph 
		var g2: MyGraph = new MyGraph(7);
		g2.add_edge(0, 1);
		g2.add_edge(1, 5);
		g2.add_edge(1, 6);
		g2.add_edge(2, 4);
		g2.add_edge(2, 1);
		g2.add_edge(3, 1);
		g2.add_edge(4, 1);
		g2.add_edge(4, 4);
		g2.add_edge(5, 1);
		g2.add_edge(6, 0);
		g2.add_edge(6, 1);
		g2.print_graph();
		g2.sink_node();
	}
}

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 5
Adjacency list of vertex 2 : 1 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
 Sink Node is 5

Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 5 6
Adjacency list of vertex 2 : 4 1
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 4
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 0 1
 Sink Node is 1
/*Swift Program
Find a universal sink of a given directed graph*/
class AjlistNode {
	//Vertices node key
	var id: Int;
	var next: AjlistNode? ;
	init(_ id: Int) {
		//Set value of node key
		self.id = id;
		self.next = nil;
	}
}
class Vertices {
	var data: Int;
	var next: AjlistNode? ;
	init(_ data: Int) {
		self.data = data;
		self.next = nil;
	}
}
class MyGraph {
	//number of Vertices
	var size: Int;
	var node: [Vertices]? = [Vertices]() ;
	init(_ size: Int) {
		self.size = size;
		
		var i = 0;
		while (i<size) {
          self.node!.append(Vertices(i));
          i+=1;
        }
	}
	
	//Connect two node
	func add_edge(_ start: Int, _ last: Int) {
		let newEdge: AjlistNode? = AjlistNode(last);
		if (self.node![start].next == nil) {
			//Include first adjacency list node of location start 
			self.node![start].next = newEdge;
		} else {
			var temp: AjlistNode? = self.node![start].next;
			//Add new node at the last of edge
			while (temp!.next != nil) {
				temp = temp!.next;
			}
			//Add node 
			temp!.next = newEdge;
		}
	}
	//Display graph elements
	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 check_edges(_ location: Int) -> Int {
		if (location == -1) {
			return -1;
		}
		var status: Int = -1;
		var temp: AjlistNode? = nil;
		var i: Int = 0;
		while (i < self.size) {
			if (i != location) {
				temp = self.node![i].next;
				status = -1;
				while (temp != nil) {
					if (temp!.id == location) {
						status = 1;
						break;
					}
					temp = temp!.next;
				}
				if (status == -1) {
					break;
				}
			}
			i += 1;
		}
		return status;
	}
	func sink_node() {
		if (self.node != nil) {
			
			var index: Int = 0;
			while (index < self.size) {
				if (self.check_edges(index) != -1) {
					print("\n Sink Node is ", index ," \n", terminator: "");
					return;
				}
				index += 1;
			}
			print("\n No Sink Node Found \n", terminator: "");
		} else {
			print("Empty Graph", terminator: "");
		}
	}
}
func main() {
	// First graph 
	let g1: MyGraph? = MyGraph(6);
	g1!.add_edge(0, 1);
	g1!.add_edge(0, 5);
	g1!.add_edge(1, 5);
	g1!.add_edge(2, 1);
	g1!.add_edge(2, 5);
	g1!.add_edge(3, 5);
	g1!.add_edge(4, 5);
	g1!.print_graph();
	g1!.sink_node();
  
	// Second graph 
	let g2: MyGraph? = MyGraph(7);
	g2!.add_edge(0, 1);
	g2!.add_edge(1, 5);
	g2!.add_edge(1, 6);
	g2!.add_edge(2, 4);
	g2!.add_edge(2, 1);
	g2!.add_edge(3, 1);
	g2!.add_edge(4, 1);
	g2!.add_edge(4, 4);
	g2!.add_edge(5, 1);
	g2!.add_edge(6, 0);
	g2!.add_edge(6, 1);
	g2!.print_graph();
	g2!.sink_node();
}
main();

Output

Adjacency list of vertex  0  : 1  5
Adjacency list of vertex  1  : 5
Adjacency list of vertex  2  : 1  5
Adjacency list of vertex  3  : 5
Adjacency list of vertex  4  : 5
Adjacency list of vertex  5  :
 Sink Node is  5

Adjacency list of vertex  0  : 1
Adjacency list of vertex  1  : 5  6
Adjacency list of vertex  2  : 4  1
Adjacency list of vertex  3  : 1
Adjacency list of vertex  4  : 1  4
Adjacency list of vertex  5  : 1
Adjacency list of vertex  6  : 0  1
 Sink Node is  1
//C# Program
//Find a universal sink of a given directed graph
using System;
public class AjlistNode {
	//Vertices node key
	public int id;
	public AjlistNode next;
	public AjlistNode(int value) {
		//Set value of node key
		id = value;
		next = null;
	}
}
public class Vertices {
	public int data;
	public AjlistNode next;
	public Vertices(int value) {
		data = value;
		next = null;
	}
}
public class MyGraph {
	//number of Vertices
	public int size;
	public Vertices []node;
	public MyGraph(int size) {
		//Set value
		this.size = size;
		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);
			}
		}
	}
	public void add_edge(int start, int last) {
		if (start >= 0 &&
			start < size &&
			last >= 0 &&
			last < size &&
			node != null) {
			AjlistNode newEdge = new AjlistNode(last);
			if (node[start].next == null) {
				node[start].next = newEdge;
			} else {
				AjlistNode temp = node[start].next;
				while (temp.next != null) {
					temp = temp.next;
				}
				temp.next = newEdge;
			}
		} else {
			Console.WriteLine("\nHere Something Wrong");
		}
	}
	public int check_edges(int location) {
		if (location == -1) {
			return -1;
		}
		int status = -1;
		AjlistNode temp = null;
		for (int i = 0; i < size; ++i) {
			if (i != location) {
				temp = node[i].next;
				status = -1;
				while (temp != null) {
					if (temp.id == location) {
						status = 1;
						break;;
					}
					temp = temp.next;
				}
				if (status == -1) {
					break;;
				}
			}
		}
		return status;
	}
	public void sink_node() {
		if (node != null) {
			
			for (int index = 0; index < size; index++) {
				if (check_edges(index) != -1) {
					Console.Write("\n Sink Node is " + index + " \n");
					return;
				}
			}
			Console.Write("\n No Sink Node Found \n");
		} else {
			Console.Write("Empty Graph");
		}
	}
	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 static void Main(String[] args) {
		MyGraph g1 = new MyGraph(6);
		g1.add_edge(0, 1);
		g1.add_edge(0, 5);
		g1.add_edge(1, 5);
		g1.add_edge(2, 1);
		g1.add_edge(2, 5);
		g1.add_edge(3, 5);
		g1.add_edge(4, 5);
		g1.print_graph();
		g1.sink_node();
		MyGraph g2 = new MyGraph(7);
		g2.add_edge(0, 1);
		g2.add_edge(1, 5);
		g2.add_edge(1, 6);
		g2.add_edge(2, 4);
		g2.add_edge(2, 1);
		g2.add_edge(3, 1);
		g2.add_edge(4, 1);
		g2.add_edge(4, 4);
		g2.add_edge(5, 1);
		g2.add_edge(6, 0);
		g2.add_edge(6, 1);
		g2.print_graph();
		g2.sink_node();
	}
}

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 5
Adjacency list of vertex 2 : 1 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
 Sink Node is 5

Adjacency list of vertex 0 : 1
Adjacency list of vertex 1 : 5 6
Adjacency list of vertex 2 : 4 1
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 4
Adjacency list of vertex 5 : 1
Adjacency list of vertex 6 : 0 1
 Sink Node is 1




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