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