Clone a graph

cloneGraph

using System;
using System.Collections.Generic;

// Given a graph, create a deep copy of that graph

// Time: O(e * n), e - number of edges, n - number of vertices/nodes
// Space: O(n), n is number of nodes
namespace CloneGraph
{
    public class Program
    {
        static Dictionary<Node, Node> copiedNodes = new Dictionary<Node, Node>();
        
        public static void Main(string[] args)
        {
            Node a = new Node(1);
            Node b = new Node(2);
            Node c = new Node(3);
            Node d = new Node(4);
            
            a.Neighbors.Add(b);
            a.Neighbors.Add(c);
            
            b.Neighbors.Add(d);
            b.Neighbors.Add(a);
            
            c.Neighbors.Add(d);
            c.Neighbors.Add(a);
            
            d.Neighbors.Add(b);
            d.Neighbors.Add(c);
            
            Console.WriteLine("Original graph is");
            display(a);
            
            // Reset the visited state
            reset(a);
            
            var clonedA = clone(a);
            
            Console.WriteLine("Cloned graph is");
            display(clonedA);
        }
        
        static void reset(Node n) {
            if (n == null || !n.IsVisited) {
                return;
            }
            
            n.IsVisited = false;
            
            foreach(var neighbor in n.Neighbors) {
                reset(neighbor);
            }
        }
        
        static Node clone(Node n) {            
            if (n == null) {
                return null;
            }
            
            if (n.IsVisited) {
                return copiedNodes[n];
            }
            
            n.IsVisited = true;
            var copyNode = deepCopy(n);
            
            foreach (var neighbor in n.Neighbors) {
                copyNode.Neighbors.Add(clone(neighbor));
            }
            
            return copyNode;
        }
        
        static void display(Node n) {
            if (n == null || n.IsVisited) {
                return;
            }
            
            n.IsVisited = true;
            
            Console.WriteLine(n.Data);
            foreach(var neighbor in n.Neighbors) {
                display(neighbor);
            }
        }
        
        static Node deepCopy(Node n) {
            if (copiedNodes.ContainsKey(n)) {
                return copiedNodes[n];
            }
            
            var copyNode = new Node(n.Data);
            copiedNodes.Add(n, copyNode);
            
            return copyNode;
        }
    }
    
    class Node {
        
        public Node(int data) {
            Data = data;
            Neighbors = new List<Node>();
        }
        
        public int Data { get; private set; }
        
        public List<Node> Neighbors;
        
        public bool IsVisited { get; set; }
    }
}