利用图论与NetworkX库高效分组字典中具有相同相似度的条目

my_dict = {
    'A': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'D': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'T': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'O': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
    # ... 更多条目
}

from math import sqrt

def square_root(x):
    return round(sqrt(sum([a * a for a in x])), 3)

def cosine_similarity(a, b):
    # 确保a是较长的字典，以简化向量构建
    input1, input2 = (a, b) if len(a) > len(b) else (b, a)

    vector1 = list(input1.values())
    vector2 = []

    for k in input1.keys():
        vector2.append(float(input2.get(k, 0))) # 如果key不存在，则视为0

    numerator = sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
    denominator = square_root(vector1) * square_root(vector2)
    return round(numerator / float(denominator), 3) if denominator != 0 else 0.0 # 避免除以零

# 假设 my_dict 已定义
keys = tuple(my_dict.keys())
pairwise_similarities = {}

for k1 in keys:
    for k2 in keys:
        if k1 != k2:
            # 避免重复计算 (k1, k2) 和 (k2, k1)
            if (k2, k1) not in pairwise_similarities:
                pairwise_similarities[(k1, k2)] = cosine_similarity(my_dict[k1], my_dict[k2])

# 结果可能包含大量冗余信息，例如：
# {
#     ('A', 'D'): 1.0,
#     ('A', 'C'): 1.0,
#     ('D', 'C'): 1.0,
#     # ...
# }

from collections import defaultdict
from itertools import combinations
import networkx as nx
from math import sqrt

# ----------------------------------------------------------------
# 1. 原始数据和相似度计算函数 (与问题描述中的函数相同)
# ----------------------------------------------------------------

def square_root(x):
    return round(sqrt(sum([a * a for a in x])), 3)

def cosine_similarity(a, b):
    input1, input2 = (a, b) if len(a) > len(b) else (b, a)
    vector1 = list(input1.values())
    vector2 = []
    for k in input1.keys():
        vector2.append(float(input2.get(k, 0)))

    numerator = sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
    denominator = square_root(vector1) * square_root(vector2)
    return round(numerator / float(denominator), 3) if denominator != 0 else 0.0

# 示例数据
my_dict = {
    'A': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'D': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'T': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1},
    'C': {'HUE_SAT': 1, 'GROUP_INPUT': 1, 'GROUP_OUTPUT': 1}, # 添加'C'以便形成一个1.0相似度的组
    'O': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
    'L': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
    'S': {'GROUP_INPUT': 3, 'MAPPING': 2, 'TEX_NOISE': 2, 'UVMAP': 2, 'VALTORGB': 3, 'GROUP_OUTPUT': 1, 'AMBIENT_OCCLUSION': 1, 'MIX': 4, 'REROUTE': 1, 'NEW_GEOMETRY': 1, 'VECT_MATH': 1},
}

# ----------------------------------------------------------------
# 2. 计算所有实体对的相似度
# ----------------------------------------------------------------

# 使用itertools.combinations生成所有不重复的实体对
all_entity_pairs_similarities = {}
for p, q in combinations(my_dict.keys(), 2):
    all_entity_pairs_similarities[(p, q)] = cosine_similarity(my_dict[p], my_dict[q])

print("所有实体对的相似度 (部分):")
print({k: v for i, (k, v) in enumerate(all_entity_pairs_similarities.items()) if i < 5}) # 打印前5个
print("-" * 30)

# ----------------------------------------------------------------
# 3. 为每个独特的相似度值构建图
# ----------------------------------------------------------------

# 使用defaultdict来自动创建图
graphs = defaultdict(nx.Graph)
for (p, q), s in all_entity_pairs_similarities.items():
    # 浮点数比较可能存在精度问题，建议对相似度值进行适当的四舍五入或量化
    # 例如，s_key = int(1000 * s + 0.5) 可以将相似度映射到整数键
    # 或者直接使用round(s, N)
    s_key = round(s, 5) # 四舍五入到5位小数作为键
    graphs[s_key].add_edge(p, q)

print(f"构建了 {len(graphs)} 个图，对应不同的相似度值。")
print("-" * 30)

# ----------------------------------------------------------------
# 4. 查找每个图中的极大团
# ----------------------------------------------------------------

cliques = {}
for s_value, G in graphs.items():
    # nx.find_cliques 返回一个迭代器，生成图G中的所有极大团
    for clique in nx.find_cliques(G):
        # 团的节点数量必须大于1才有意义，因为单个节点不是“组”
        if len(clique) > 1:
            # 将团转换为元组作为键，相似度值作为值
            # 注意：同一个团可能在不同的相似度图中找到，但其相似度值是唯一的
            cliques[tuple(sorted(clique))] = s_value # 对团内的元素进行排序，确保键的唯一性

print("分组结果 (团):")
for k, v in cliques.items():
    print(f"{k}: {v}")

# 预期输出示例 (可能因数据和相似度计算略有不同):
# ('A', 'C', 'D', 'T'): 1.0
# ('L', 'O', 'S'): 1.0 (如果它们之间相似度也是1.0)