Clone a Directed Graph
Here given code implementation process.
//C program
//Clone a 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 = 6;
//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) {
//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;
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");
}
}
struct Graph *clone_graph(struct Graph *first) {
struct Graph *second = (struct Graph *) malloc(sizeof(struct Graph) *size);
if (first != NULL) {
struct AjlistNode *temp = NULL;
set_data(second);
for (int index = 0; index < size; index++) {
temp = first[index].next;
while (temp != NULL) {
//add edges
add_edge(second, index, temp->vId);
temp = temp->next;
}
}
}
return second;
}
int main() {
struct Graph *g1 = NULL;
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, 0);
add_edge(g1, 1, 0);
add_edge(g1, 1, 4);
add_edge(g1, 1, 5);
add_edge(g1, 2, 0);
add_edge(g1, 2, 4);
add_edge(g1, 2, 5);
add_edge(g1, 3, 4);
add_edge(g1, 3, 5);
add_edge(g1, 5, 4);
printf(" First Graph ");
print_graph(g1);
struct Graph *g2 = clone_graph(g1);
printf("\n\n Clone Graph");
print_graph(g2);
}
return 0;
}
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4// C++ program
// Clone a Directed Graph
#include<iostream>
using namespace std;
class AjlistNode {
public:
//Vertices node key
int id;
AjlistNode *next;
AjlistNode(int id) {
//Set value of node key
this->id = id;
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 MyGraph {
public:
//number of Vertices
int size;
Vertices *node;
MyGraph(int size) {
this->size = size;
this->node = new Vertices[size];
//set initial values of graph node
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
int index = 0;
while (index < this->size) {
this->node[index] = index;
index++;
}
}
}
//Connect two node
void add_edge(int start, int last) {
AjlistNode *newEdge = new AjlistNode(last);
if (this->node[start].next == NULL) {
//Include first adjacency list node of location start
this->node[start].next = newEdge;
} else {
AjlistNode *temp = this->node[start].next;
//Add new node at the last of edge
while (temp->next != NULL) {
temp = temp->next;
}
//Add node
temp->next = newEdge;
}
}
//Display graph elements
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
int index = 0;
while (index < this->size) {
cout << "\nAdjacency list of vertex " << index << " : ";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << this->node[temp->id].data << " ";
temp = temp->next;
}
index++;
}
}
}
MyGraph clone_graph() {
//First create same number of nodes
//Assume given graph are contains nodes
MyGraph graph = MyGraph(this->size);
if (this->node != NULL) {
AjlistNode *temp = NULL;
for (int index = 0; index < this->size; index++) {
temp = this->node[index].next;
while (temp != NULL) {
//Add edges of new graph
graph.add_edge(index, temp->id);
temp = temp->next;
}
}
}
return graph;
}
};
int main() {
MyGraph g1 = MyGraph(6);
//Connected two node with Edges
g1.add_edge(0, 0);
g1.add_edge(1, 0);
g1.add_edge(1, 4);
g1.add_edge(1, 5);
g1.add_edge(2, 0);
g1.add_edge(2, 4);
g1.add_edge(2, 5);
g1.add_edge(3, 4);
g1.add_edge(3, 5);
g1.add_edge(5, 4);
cout << "First Graph ";
g1.print_graph();
MyGraph g2 = g1.clone_graph();
cout << "\n\nClone Graph";
g2.print_graph();
return 0;
}
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4// Java program
// Clone a Directed Graph
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
public MyGraph(int size) {
this.size = size;
this.node = new Vertices[size];
//set initial values of graph node
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
System.out.println("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);
if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 && node != null) {
int index = 0;
while (index < size) {
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;
}
index++;
}
}
}
public MyGraph clone_graph() {
//First create same number of nodes
//Assume given graph are contains nodes
MyGraph graph = new MyGraph(this.size);
if (this.node != null) {
AjlistNode temp = null;
for (int index = 0; index < this.size; index++) {
temp = this.node[index].next;
while (temp != null) {
//Add edges of new graph
graph.add_edge(index, temp.id);
temp = temp.next;
}
}
}
return graph;
}
public static void main(String[] args) {
MyGraph g1 = new MyGraph(6);
//Connected two node with Edges
g1.add_edge(0, 0);
g1.add_edge(1, 0);
g1.add_edge(1, 4);
g1.add_edge(1, 5);
g1.add_edge(2, 0);
g1.add_edge(2, 4);
g1.add_edge(2, 5);
g1.add_edge(3, 4);
g1.add_edge(3, 5);
g1.add_edge(5, 4);
System.out.print("First Graph ");
g1.print_graph();
MyGraph g2 = g1.clone_graph();
System.out.print("\n\nClone Graph");
g2.print_graph();
}
}
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4// C# program
// Clone a Directed Graph
using System;
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
public MyGraph(int size) {
this.size = size;
this.node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);
if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 &&
node != null) {
int index = 0;
while (index < size) {
Console.Write("\nAdjacency list of vertex " + index + " : ");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
public MyGraph clone_graph() {
//First create same number of nodes
//Assume given graph are contains nodes
MyGraph graph = new MyGraph(this.size);
if (this.node != null) {
AjlistNode temp = null;
for (int index = 0; index < this.size; index++) {
temp = this.node[index].next;
while (temp != null) {
graph.add_edge(index, temp.id);
temp = temp.next;
}
}
}
return graph;
}
public static void Main(String[] args) {
MyGraph g1 = new MyGraph(6);
g1.add_edge(0, 0);
g1.add_edge(1, 0);
g1.add_edge(1, 4);
g1.add_edge(1, 5);
g1.add_edge(2, 0);
g1.add_edge(2, 4);
g1.add_edge(2, 5);
g1.add_edge(3, 4);
g1.add_edge(3, 5);
g1.add_edge(5, 4);
Console.Write("First Graph ");
g1.print_graph();
MyGraph g2 = g1.clone_graph();
Console.Write("\n\nClone Graph");
g2.print_graph();
}
}
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4<?php
// Php program
// Clone a Directed Graph
class AjlistNode {
//Vertices node key
public $id;
public $next;
function __construct($id) {
//Set value of node key
$this->id = $id;
$this->next = null;
}
}
class Vertices {
public $data;
public $next;
function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class MyGraph {
//number of Vertices
private $size;
private $node;
function __construct($size) {
$this->size = $size;
$this->node = array_fill(0, $size, 0);
//set initial values of graph node
$this->set_data();
}
//Set initial node value
public function set_data() {
if ($this->node == null) {
echo("\nEmpty Graph");
} else {
$index = 0;
while ($index < $this->size) {
$this->node[$index] = new Vertices($index);
$index++;
}
}
}
//Connect two node
public function add_edge($start, $last) {
$newEdge = new AjlistNode($last);
if ($this->node[$start]->next == null) {
//Include first adjacency list node of location start
$this->node[$start]->next = $newEdge;
} else {
$temp = $this->node[$start]->next;
//Add new node at the last of edge
while ($temp->next != null) {
$temp = $temp->next;
}
//Add node
$temp->next = $newEdge;
}
}
//Display graph elements
public function print_graph() {
if ($this->size > 0 &&
$this->node != null) {
$index = 0;
while ($index < $this->size) {
echo("\nAdjacency list of vertex ". $index ." : ");
$temp = $this->node[$index]->next;
while ($temp != null) {
echo($this->node[$temp->id]->data ." ");
$temp = $temp->next;
}
$index++;
}
}
}
public function clone_graph() {
//First create same number of nodes
//Assume given graph are contains nodes
$graph = new MyGraph($this->size);
if ($this->node != null) {
$temp = null;
for ($index = 0; $index < $this->size; $index++) {
$temp = $this->node[$index]->next;
while ($temp != null) {
//Add edges of new graph
$graph->add_edge($index, $temp->id);
$temp = $temp->next;
}
}
}
return $graph;
}
}
function main() {
$g1 = new MyGraph(6);
//Connected two node with Edges
$g1->add_edge(0, 0);
$g1->add_edge(1, 0);
$g1->add_edge(1, 4);
$g1->add_edge(1, 5);
$g1->add_edge(2, 0);
$g1->add_edge(2, 4);
$g1->add_edge(2, 5);
$g1->add_edge(3, 4);
$g1->add_edge(3, 5);
$g1->add_edge(5, 4);
echo("First Graph ");
$g1->print_graph();
$g2 = $g1->clone_graph();
echo("\n\nClone Graph");
$g2->print_graph();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4// Node Js program
// Clone a Directed Graph
class AjlistNode {
//Vertices node key
constructor(id) {
//Set value of node key
this.id = id;
this.next = null;
}
}
class Vertices {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyGraph {
//number of Vertices
constructor(size) {
this.size = size;
this.node = Array(size).fill(null);
//set initial values of graph node
this.set_data();
}
//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
var index = 0;
while (index < this.size) {
this.node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
add_edge(start, last) {
var newEdge = new AjlistNode(last);
if (this.node[start].next == null) {
//Include first adjacency list node of location start
this.node[start].next = newEdge;
} else {
var temp = this.node[start].next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
print_graph() {
if (this.size > 0 &&
this.node != null) {
var index = 0;
while (index < this.size) {
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;
}
index++;
}
}
}
clone_graph() {
//First create same number of nodes
//Assume given graph are contains nodes
var graph = new MyGraph(this.size);
if (this.node != null) {
var temp = null;
for (var index = 0; index < this.size; index++) {
temp = this.node[index].next;
while (temp != null) {
//Add edges of new graph
graph.add_edge(index, temp.id);
temp = temp.next;
}
}
}
return graph;
}
}
function main(args) {
var g1 = new MyGraph(6);
//Connected two node with Edges
g1.add_edge(0, 0);
g1.add_edge(1, 0);
g1.add_edge(1, 4);
g1.add_edge(1, 5);
g1.add_edge(2, 0);
g1.add_edge(2, 4);
g1.add_edge(2, 5);
g1.add_edge(3, 4);
g1.add_edge(3, 5);
g1.add_edge(5, 4);
process.stdout.write("First Graph ");
g1.print_graph();
var g2 = g1.clone_graph();
process.stdout.write("\n\nClone Graph");
g2.print_graph();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4# Python 3 program
# Clone a Directed Graph
class AjlistNode :
def __init__(self, id) :
# Set value of node key
self.id = id
self.next = None
class Vertices :
def __init__(self, data) :
self.data = data
self.next = None
class MyGraph :
def __init__(self, size) :
self.size = size
self.node = [0] * size
# set initial values of graph node
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 node
def add_edge(self, start, last) :
newEdge = AjlistNode(last)
if (self.node[start].next == None) :
# Include first adjacency list node of location start
self.node[start].next = newEdge
else :
temp = self.node[start].next
# Add new node at the last of edge
while (temp.next != None) :
temp = temp.next
# Add node
temp.next = newEdge
# Display graph elements
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 clone_graph(self) :
# First create same number of nodes
# Assume given graph are contains nodes
graph = MyGraph(self.size)
if (self.node != None) :
temp = None
index = 0
while (index < self.size) :
temp = self.node[index].next
while (temp != None) :
# Add edges of new graph
graph.add_edge(index, temp.id)
temp = temp.next
index += 1
return graph
def main() :
g1 = MyGraph(6)
# Connected two node with Edges
g1.add_edge(0, 0)
g1.add_edge(1, 0)
g1.add_edge(1, 4)
g1.add_edge(1, 5)
g1.add_edge(2, 0)
g1.add_edge(2, 4)
g1.add_edge(2, 5)
g1.add_edge(3, 4)
g1.add_edge(3, 5)
g1.add_edge(5, 4)
print("First Graph ", end = "")
g1.print_graph()
g2 = g1.clone_graph()
print("\n\nClone Graph", end = "")
g2.print_graph()
if __name__ == "__main__":
main()
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4 # Ruby program
# Clone a Directed Graph
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :next
attr_accessor :id, :next
def initialize(id)
# Set value of node key
self.id = id
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 MyGraph
# Define the accessor and reader of class MyGraph
attr_reader :size, :node
attr_accessor :size, :node
def initialize(size)
self.size = size
self.node = Array.new(size) {0}
# set initial values of graph node
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 node
def add_edge(start, last)
newEdge = AjlistNode.new(last)
if (@node[start].next == nil)
# Include first adjacency list node of location start
@node[start].next = newEdge
else
temp = @node[start].next
# Add new node at the last of edge
while (temp.next != nil)
temp = temp.next
end
# Add node
temp.next = newEdge
end
end
# Display graph elements
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 clone_graph()
# Assume given graph are contains nodes
# First create same number of nodes
graph = MyGraph.new(self.size)
if (self.node != nil)
temp = nil
index = 0
while (index < self.size)
temp = self.node[index].next
while (temp != nil)
# Add edges of new graph
graph.add_edge(index, temp.id)
temp = temp.next
end
index += 1
end
end
return graph
end
end
def main()
g1 = MyGraph.new(6)
# Connected two node with Edges
g1.add_edge(0, 0)
g1.add_edge(1, 0)
g1.add_edge(1, 4)
g1.add_edge(1, 5)
g1.add_edge(2, 0)
g1.add_edge(2, 4)
g1.add_edge(2, 5)
g1.add_edge(3, 4)
g1.add_edge(3, 5)
g1.add_edge(5, 4)
print("First Graph ")
g1.print_graph()
g2 = g1.clone_graph()
print("\n\nClone Graph")
g2.print_graph()
end
main()
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4 // Scala program
// Clone a 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;
}
}
}
//Connect two node
def add_edge(start: Int, last: Int): Unit = {
var newEdge: AjlistNode = new AjlistNode(last);
if (this.node(start).next == null) {
//Include first adjacency list node of location start
this.node(start).next = newEdge;
} else {
var temp: AjlistNode = this.node(start).next;
//Add new node at the last of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
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;
}
}
}
def clone_graph(): MyGraph = {
//First create same number of nodes
//Assume given graph are contains nodes
var graph: MyGraph = new MyGraph(this.size);
if (this.node != null) {
var temp: AjlistNode = null;
var index: Int = 0;
while (index < this.size) {
temp = this.node(index).next;
while (temp != null) {
//Add edges of new graph
graph.add_edge(index, temp.id);
temp = temp.next;
}
index += 1;
}
}
return graph;
}
}
object Main {
def main(args: Array[String]): Unit = {
var g1: MyGraph = new MyGraph(6);
//Connected two node with Edges
g1.add_edge(0, 0);
g1.add_edge(1, 0);
g1.add_edge(1, 4);
g1.add_edge(1, 5);
g1.add_edge(2, 0);
g1.add_edge(2, 4);
g1.add_edge(2, 5);
g1.add_edge(3, 4);
g1.add_edge(3, 5);
g1.add_edge(5, 4);
print("First Graph ");
g1.print_graph();
var g2: MyGraph = g1.clone_graph();
print("\n\nClone Graph");
g2.print_graph();
}
}
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4// Swift program
// Clone a 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 clone_graph() -> MyGraph? {
//First create same number of nodes
//Assume given graph are contains nodes
let graph: MyGraph? = MyGraph(self.size);
if (self.node != nil) {
var temp: AjlistNode? = nil;
var index: Int = 0;
while (index < self.size) {
temp = self.node![index].next;
while (temp != nil) {
//Add edges of new graph
graph!.add_edge(index, temp!.id);
temp = temp!.next;
}
index += 1;
}
}
return graph;
}
}
func main() {
let g1: MyGraph? = MyGraph(6);
//Connected two node with Edges
g1!.add_edge(0, 0);
g1!.add_edge(1, 0);
g1!.add_edge(1, 4);
g1!.add_edge(1, 5);
g1!.add_edge(2, 0);
g1!.add_edge(2, 4);
g1!.add_edge(2, 5);
g1!.add_edge(3, 4);
g1!.add_edge(3, 5);
g1!.add_edge(5, 4);
print("First Graph ", terminator: "");
g1!.print_graph();
let g2: MyGraph? = g1!.clone_graph();
print("\n\nClone Graph", terminator: "");
g2!.print_graph();
}
main();
Output
First Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Clone Graph
Adjacency list of vertex 0 : 0
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
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