Skip to main content

Clone a Directed Graph

The problem at hand is about cloning a directed graph, which involves creating an identical copy of a given graph while maintaining the structure and connections between its nodes and edges. A directed graph consists of nodes (vertices) and directed edges connecting these nodes, indicating the flow or direction between them. Cloning a graph is essential in various applications such as graph algorithms, network simulations, and data processing.

Problem Statement and Description

The task is to write a program that can clone a directed graph. In other words, given a source graph, the program should create a new graph that is structurally identical but independent from the original graph. This means that changes made to the cloned graph should not affect the original graph, and vice versa.

Example

Let's consider a simple example to understand the problem. Imagine you have the following directed graph:

Original Graph:
0 -> 0
1 -> 0, 4, 5
2 -> 0, 4, 5
3 -> 4, 5
4 ->
5 -> 4

Cloning this graph should result in:

Cloned Graph:
0 -> 0
1 -> 0, 4, 5
2 -> 0, 4, 5
3 -> 4, 5
4 ->
5 -> 4

Idea to Solve the Problem

To clone a directed graph, we can follow these steps:

  1. Create a new array of nodes to represent the cloned graph.
  2. Traverse the original graph's nodes and create corresponding nodes in the cloned graph.
  3. For each node in the original graph, traverse its adjacency list and create corresponding adjacency nodes in the cloned graph.
  4. Link the cloned nodes and adjacency nodes to replicate the original graph's structure.

Standard Pseudocode

procedure clone_graph(original_graph):
    create an array 'cloned_graph' of size equal to the number of nodes in original_graph
    
    for each node in original_graph:
        create a new node in cloned_graph with the same data as the original node
        
    for each node in original_graph:
        for each adjacency node in node's adjacency list:
            add an edge from corresponding node in cloned_graph to the corresponding adjacency node
            
    return cloned_graph

Algorithm Explanation

  1. The clone_graph function takes the original graph as input.
  2. It initializes an array cloned_graph to store the cloned nodes.
  3. It then iterates through each node in the original graph and creates a new node in the cloned_graph array with the same data.
  4. After creating the nodes, it again iterates through each node in the original graph and its adjacency list. For each adjacency node, it adds an edge from the corresponding node in the cloned_graph to the corresponding adjacency node.
  5. Finally, the function returns the cloned graph.

Program Solution

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

Time Complexity

  • The creation of nodes takes O(V) time, where V is the number of vertices in the graph.
  • Adding edges for each node's adjacency list takes O(E), where E is the total number of edges.
  • Overall, the time complexity of cloning a graph is O(V + E), where V is the number of vertices and E is the number of edges.
Last updated on by Kalkicode




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