magic_uv/utils/graph.py

   1 # SPDX-License-Identifier: GPL-2.0-or-later
   2
   3 __author__ = "Nutti <nutti.metro@gmail.com>"
   4 __status__ = "production"
   5 __version__ = "6.6"
   6 __date__ = "22 Apr 2022"
   7
   8
   9 class Node:
  10     def __init__(self, key, value=None):
  11         self.key = key
  12         self.value = value
  13         self.edges = []
  14
  15     def degree(self):
  16         return len(self.edges)
  17
  18     def connected_nodes(self):
  19         return [e.other(self) for e in self.edges]
  20
  21
  22 class Edge:
  23     def __init__(self, node_1, node_2):
  24         self.node_1 = node_1
  25         self.node_2 = node_2
  26
  27     def other(self, node):
  28         if self.node_1 == node and self.node_2 == node:
  29             raise RuntimeError("Loop edge in {} is not supported."
  30                                .format(node.key))
  31         if node not in (self.node_1, self.node_2):
  32             raise RuntimeError("Node {} does not belong to this edge."
  33                                .format(node.key))
  34         if self.node_1 == node:
  35             return self.node_2
  36         return self.node_1
  37
  38
  39 class Graph:
  40     def __init__(self):
  41         self.edges = []
  42         self.nodes = {}
  43
  44     def add_node(self, node):
  45         if node.key in self.nodes:
  46             raise RuntimeError("Node '{}' is already registered."
  47                                .format(node.key))
  48         self.nodes[node.key] = node
  49
  50     def add_edge(self, node_1, node_2):
  51         if node_1.key not in self.nodes:
  52             raise RuntimeError("Node '{}' is not registered."
  53                                .format(node_1.key))
  54         if node_2.key not in self.nodes:
  55             raise RuntimeError("Node '{}' is not registered."
  56                                .format(node_2.key))
  57
  58         edge = Edge(node_1, node_2)
  59         self.edges.append(edge)
  60         node_1.edges.append(edge)
  61         node_2.edges.append(edge)
  62
  63     def get_node(self, key):
  64         return self.nodes[key]
  65
  66
  67 def dump_graph(graph):
  68     print("=== Node ===")
  69     for _, node in graph.nodes.items():
  70         print("Key: {}, Value {}".format(node.key, node.value))
  71
  72     print("=== Edge ===")
  73     for edge in graph.edges:
  74         print("{} - {}".format(edge.node_1.key, edge.node_2.key))
  75
  76
  77 # VF2 algorithm
  78 #   Ref: https://stackoverflow.com/questions/8176298/
  79 #            vf2-algorithm-steps-with-example
  80 #   Ref: https://github.com/satemochi/saaaaah/blob/master/geometric_misc/
  81 #            isomorph/vf2/vf2.py
  82 def graph_is_isomorphic(graph_1, graph_2):
  83     def is_iso(pairs, matching_node, new_node):
  84         # Algorithm:
  85         #   1. The degree is same (It's faster).
  86         #   2. The connected node is same.
  87         if matching_node.degree() != new_node.degree():
  88             return False
  89
  90         matching_connected = [c.key for c in matching_node.connected_nodes()]
  91         new_connected = [c.key for c in new_node.connected_nodes()]
  92
  93         for p in pairs:
  94             n1 = p[0]
  95             n2 = p[1]
  96             if n1 in matching_connected and n2 not in new_connected:
  97                 return False
  98             if n1 not in matching_connected and n2 in new_connected:
  99                 return False
 100
 101         return True
 102
 103     def dfs(graph_1, graph_2):
 104         def generate_pair(g1, g2, pairs):
 105             remove_1 = [p[0] for p in pairs]
 106             remove_2 = [p[1] for p in pairs]
 107
 108             keys_1 = sorted(list(set(g1.nodes.keys()) - set(remove_1)))
 109             keys_2 = sorted(list(set(g2.nodes.keys()) - set(remove_2)))
 110             for k1 in keys_1:
 111                 for k2 in keys_2:
 112                     yield (k1, k2)
 113
 114         pairs = []
 115         stack = [generate_pair(graph_1, graph_2, pairs)]
 116         while stack:
 117             try:
 118                 k1, k2 = next(stack[-1])
 119                 n1 = graph_1.get_node(k1)
 120                 n2 = graph_2.get_node(k2)
 121                 if is_iso(pairs, n1, n2):
 122                     pairs.append([k1, k2])
 123                     stack.append(generate_pair(graph_1, graph_2, pairs))
 124                     if len(pairs) == len(graph_1.nodes):
 125                         return True, pairs
 126             except StopIteration:
 127                 stack.pop()
 128                 diff = len(pairs) - len(stack)
 129                 for _ in range(diff):
 130                     pairs.pop()
 131
 132         return False, []
 133
 134     # First, check simple condition.
 135     if len(graph_1.nodes) != len(graph_2.nodes):
 136         return False, {}
 137     if len(graph_1.edges) != len(graph_2.edges):
 138         return False, {}
 139
 140     is_isomorphic, pairs = dfs(graph_1, graph_2)
 141
 142     node_pairs = {}
 143     for pair in pairs:
 144         n1 = pair[0]
 145         n2 = pair[1]
 146         node_1 = graph_1.get_node(n1)
 147         node_2 = graph_2.get_node(n2)
 148         node_pairs[node_1] = node_2
 149
 150     return is_isomorphic, node_pairs