Clone Graph

Clone Graph

We are given a graph represented by a collection of nodes and their neighbors. The goal is to clone this graph, creating a new graph with the same structure and values.

Here's my solution,

class Node:
    """
    Represents a node in a graph.
    """

    def __init__(self, val=0, neighbors=None):
        """
        Initializes a new Node.

        Args:
            val (int): The value associated with the node (default is 0).
            neighbors (List[Node]): List of neighboring nodes (default is an empty list).
        """
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution:
    """
    Provides a solution for cloning a graph.
    """

    def cloneGraph(self, node: Node) -> Node:
        """
        Clones the given graph starting from the specified node.

        Args:
            node (Node): The starting node to clone.

        Returns:
            Node: The cloned graph.
        """
        oldToNew = {}

        def dfs(node):
            """
            Performs depth-first search to clone the graph.

            Args:
                node (Node): The current node to process.

            Returns:
                Node: The cloned node.
            """
            if node in oldToNew:
                return oldToNew[node]

            copy = Node(node.val)
            oldToNew[node] = copy

            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy

        return dfs(node) if node else None

Depth-First Search (DFS) with Hash Map

We can use depth-first search (DFS) to traverse the original graph and create a copy of each node.

To avoid duplicating nodes, we’ll use a hash map (oldToNew) to keep track of the mapping between original nodes and their corresponding cloned nodes.

The DFS function will recursively create the cloned nodes and their neighbors.

DFS Function (dfs)

The dfs function takes an input node and returns its cloned counterpart.

If the node is already in the oldToNew map, we return the corresponding cloned node.

Otherwise, we create a new node with the same value as the original node and add it to the map.

We then recursively process each neighbor of the original node, creating their cloned counterparts and connecting them appropriately.

Cloning Process

For each neighbor of the original node, we recursively call dfs(nei) to get the cloned neighbor.

We add this cloned neighbor to the neighbors list of the newly created cloned node.

This ensures that the cloned graph maintains the same structure as the original.

Time Complexity

The DFS process visits each node once, so the time complexity is O(V), where V is the number of nodes in the graph.

Space Complexity

We use additional space for the hash map (oldToNew) to store the mapping between original and cloned nodes. Therefore, the space complexity is O(V) as well.

Unit Tests

I have created some unit tests to verify the accuracy and robustness of the cloneGraph method in the Solution class. Below, I’ve provided a set of test cases using the unittest framework:

import unittest

class TestSolution(unittest.TestCase):
    def test_cloneGraph_single_node(self):
        # Test with a single node graph
        node1 = Node(1)
        s = Solution()
        cloned_node1 = s.cloneGraph(node1)
        self.assertEqual(cloned_node1.val, 1)
        self.assertEqual(len(cloned_node1.neighbors), 0)

    def test_cloneGraph_multiple_nodes(self):
        # Test with a graph containing multiple nodes
        node1 = Node(1)
        node2 = Node(2)
        node3 = Node(3)
        node1.neighbors = [node2, node3]
        node2.neighbors = [node1, node3]
        node3.neighbors = [node1, node2]

        s = Solution()
        cloned_node1 = s.cloneGraph(node1)

        # Check values
        self.assertEqual(cloned_node1.val, 1)
        self.assertEqual(cloned_node1.neighbors[0].val, 2)
        self.assertEqual(cloned_node1.neighbors[1].val, 3)

        # Check references (should be different objects)
        self.assertIsNot(cloned_node1, node1)
        self.assertIsNot(cloned_node1.neighbors[0], node2)
        self.assertIsNot(cloned_node1.neighbors[1], node3)

    def test_cloneGraph_empty_graph(self):
        # Test with an empty graph (None input)
        s = Solution()
        cloned_node = s.cloneGraph(None)
        self.assertIsNone(cloned_node)

if __name__ == "__main__":
    unittest.main()