Хеш-функция для цветных изоморфных графов

Question

У меня есть неориентированный цветной (смежные узлы имеют разные цвета) график, и мне нужно вычислить хэш, чтобы, если два графика изоморфны, они имели одинаковый хэш (график также плоский, я не знаю, может ли он иметь некоторое значение).

Моя структура данных такова:

class Node:
    def __init__(self, id, color):
        self.id = id # int
        self.color = color # string
        self.adjacentNodes = set()

Свойство id используется для логики программы, поэтому его не следует учитывать при сравнении графиков.

Моя идея состоит в том, чтобы отсортировать узлы графа и затем, начиная с первого узла, исследовать соседние узлы, чтобы сгенерировать дерево графа. Затем я генерирую уникальную строку из дерева (на самом деле я генерирую строку во время исследования). Итак, что я пытаюсь сделать, так это найти своего рода канонизацию графа.

Описание

Я сортирую узлы сначала по градусу , а затем по цвету имени свойства в порядке возрастания. Я беру первый узел и начинаю исследовать соседние узлы с поиском по глубине, сортируя их таким же образом Я отслеживаю уже посещенные узлы, чтобы не расширять старые.

Моя строка генерируется так: используя поиск по глубине, каждый раз, когда я достигаю нового узла, я добавляю к строке графика следующее:

• узел цвета
• степень узла
• индекс в списке посещенных узлов

Возможно, это излишне, но я подумал, что этой информации было достаточно, чтобы гарантировать правильную канонизацию.

Реальная проблема заключается в том, что во время сортировки два узла имеют одинаковый градус и один и тот же цвет . То, что я делаю, должно гарантировать канонизацию, но не очень эффективно. Взяв группу схожих узлов (одинаковой степени и цвета), я генерирую поддерево для каждого узла и связанную строку с поддеревом и выбираю самый большой (сортируя их в порядке убывания), как следующий в сортировке узлов. Затем я удаляю этот последний узел и повторяю операцию, пока эта группа не станет пустой. Мне нужно сделать это, потому что после выбора первого узла я мог бы изменить список посещенных узлов, и тогда новые строки могли бы быть разными.

В настоящее время эта реализация очень неэффективна:

# actually this function return the unique string associated with the graph
# that will be hashed with the function hash() in a second moment
def new_hash(graph, queue=[]): # graph: list of Node
    if not queue: # first call: find the root of the tree
        graph.sort(key = lambda x: (len(x.adjacentNodes), x.color), reverse=True)
        groups = itertools.groupby(graph, key = lambda x: (len(x.adjacentNodes), x.color))
        roots = []
        result_hash = ''

        for _, group in groups:
            roots  = [x for x in group]
            break # I just need the first (the candidates roots)

        temp_hashes = []

        for node in roots:
            temp_queue = [node.id]
            temp_hash = node.color + str(len(node.adjacentNodes)) + str(temp_queue.index(node.id))
            temp_hash += new_hash(list(node.adjacentNodes), temp_queue)
            temp_hashes.append((node, temp_hash, temp_queue))

        temp_hashes.sort(key = lambda x: x[1], reverse=True)
        queue = temp_hashes[0][2]        
        result_hash += temp_hashes[0][1]
        result_hash += new_hash(list(temp_hashes[0][0].adjacentNodes), queue=queue)
    else:
        graph.sort(key = lambda x: (len(x.adjacentNodes), x.color), reverse=True)
        groups = itertools.groupby(graph, key = lambda x: (len(x.adjacentNodes), x.color))
        grouped_nodes = []
        result_hash = ''

        for _, group in groups:
            grouped_nodes.append([x for x in group])

        for group in grouped_nodes:
            while len(group) > 0:
                temp_hashes = []

                for node in group:
                    if node.id in queue:
                        temp_hash = node.color + str(len(node.adjacentNodes)) + str(queue.index(node.id))
                        temp_hashes.append((node, temp_hash, queue))
                    else:
                        temp_queue = queue[:]
                        temp_queue.append(node.id)
                        temp_hash = node.color + str(len(node.adjacentNodes)) + str(temp_queue.index(node.id))
                        temp_hash += new_hash(list(node.adjacentNodes), queue=temp_queue)
                        temp_hashes.append((node, temp_hash, temp_queue))

                temp_hashes.sort(key = lambda x: x[1], reverse=True)
                queue = temp_hashes[0][2]
                result_hash += temp_hashes[0][1]
                group.remove(temp_hashes[0][0])

    return result_hash

Вопросы

Поэтому у меня два вопроса:

• действительно ли мой алгоритм работает (я имею в виду, он работает, но у меня нет математических доказательств)?
• Есть ли более быстрый алгоритм (менее сложный) для вычисления хеша?