Algorithm to determine if two graphs are the same-CodePudding

Given a graph the root node of which is defined by a Node object:

class Node:

    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
    
    def __eq__(self, other) -> bool:
        
        if isinstance(other, self.__class__):
            return self.__repr__() == other.__repr__()
    
    def __repr__(self):
        return f"Node(val: {self.val}, neighbors: {self.neighbors})"
    
    def __str__(self):
        return self.__repr__()

The Graph class is defined as below, which uses the Node class above to construct itself from an adjacency list

class Graph:
    
    def __init__(self, adj_list=[]):
        
        self.root = adj_list or self.make_graph(adj_list)
        
        
    def __repr__(self):
        return str(self.root)
    
    def __str__(self):
        return self.__repr__()
    
    def __eq__(self, other):
    
        if isinstance(other, self.__class__):
            return other.root == self.root
        
        return False
    
    
    def make_graph(self, adj_list) -> Node:

        # Ref: https://stackoverflow.com/a/72499884/16378872
        nodes = [Node(i   1) for i in range(len(adj_list))]
        
        for i, neighbors in enumerate(adj_list):
            nodes[i].neighbors = [nodes[j-1] for j in neighbors]
            
        return nodes[0]

For example the adjacency list [[2,4],[1,3],[2,4],[1,3]] is transformed to a Graph as below

graph = Graph([[2,4],[1,3],[2,4],[1,3]])

print(graph)

Node(val: 1, neighbors: [Node(val: 2, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [Node(val: 2, neighbors: [...]), Node(val: 4, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [...])])])]), Node(val: 4, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [Node(val: 2, neighbors: [Node(val: 1, neighbors: [...]), Node(val: 3, neighbors: [...])]), Node(val: 4, neighbors: [...])])])])

Now if I have 2 graphs:

graph1 = Graph([[2,4],[1,3],[2,4],[1,3]])
graph2 = Graph([[2,4],[1,3],[2,4],[1,3]])

print(graph1 == graph2)

True

I can check their equality by comparing the return values of Node.__repr__() of both these graph objects graph1 and graph2 which essentially is done via the __eq__() special method of Graph that is comparing the equality of the root nodes of both the graphs, hence using the __repr__() special method of Node as explained above.

The __repr__ method truncates the deeply nested neighbors in the output as [...], however there could be some nodes deep inside that do not have equal values of Node.val, hence making the comparison result unreliable by this method.

My concern is, is there a better and more reliable way to do this equality test instead of just comparing the __repr__() of both the graph's root nodes?.

CodePudding user response：

You can implement a depth-first traversal and compare nodes by value and degree. Mark nodes as visited to avoid they are traversed a second time:

    def __eq__(self, other) -> bool:
        visited = set()
        
        def dfs(a, b):
            if a.val != b.val or len(a.neighbors) != len(b.neighbors):
                return False
            if a.val in visited:
                return True
            visited.add(a.val)
            return all(dfs(*pair) for pair in zip(a.neighbors, b.neighbors))
            
        return isinstance(other, self.__class__) and dfs(self, other)

This code assumes that a node's value uniquely identifies the node within the same graph.

This also assumes that the graph is connected, otherwise components that are disconnected from the root will not be compared.