3

無向の色付き (隣接するノードの色が異なる) グラフがあり、ハッシュを計算して、2 つのグラフが同型の場合に同じハッシュを持つようにする必要があります (グラフも平面であり、違いが生じるかどうかはわかりません) ）。

私のデータ構造はこれです：

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

このidプロパティはプログラム ロジックに使用されるため、グラフを比較する際に考慮する必要はありません。

私の考えは、グラフのノードを並べ替えてから、最初のノードから、グラフのツリーを生成するために隣接するノードを探索することです。次に、ツリーから一意の文字列を生成します (実際には、探索中に文字列を生成しています)。だから、私がやろうとしているのは、グラフの一種の正規化を見つけることです.

説明

最初にノードを次数で並べ替え、次に色プロパティ名で昇順に並べ替えます。最初のノードを取得し、隣接するノードの探索を開始します。深さ優先検索で同じ方法で並べ替えます。古いノードを拡張しないように、既にアクセスしたノードを追跡します。

私の文字列は次のように生成されます: 深さ優先検索を使用して、新しいノードに到達するたびにグラフ文字列に次を追加します。

  • ノードの色
  • ノード度
  • 訪問したノードのリストのインデックス

冗長かもしれませんが、これらの情報は正しい列聖を保証するのに十分だと思いました。

実際の問題は、ソート中に 2 つのノードが同じ次数と同じ色を持つ場合です。私が行うことは正規化を保証する必要がありますが、あまり効率的ではありません。類似したノード (次数と色が同じ) のグループを取得し、各ノードのサブツリーとサブツリーに関連付けられた文字列を生成し、ノードの並べ替えで次のノードとして最大のものを選択します (降順で並べ替えます)。次に、この最後のノードを削除し、このグループが空になるまで操作を繰り返します。最初のノードを選択した後、訪問したノードのリストを変更した可能性があり、新しい文字列が異なる可能性があるため、これを行う必要があります。

現在、この実装は非常に非効率的です:

# 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

質問

したがって、私は2つの質問があります：

  • 私のアルゴリズムは本当に機能しますか (つまり、機能しているように見えますが、数学的な証明はありません)。
  • ハッシュを計算するためのより高速な (複雑さの少ない) アルゴリズムはありますか?
4

0 に答える 0