python与算法：冲突图结构分组分析

result={('AB','BC'):True,
        ('AB','EA'):True,
        ('AB','BD'):True,
        ('AB','DA'):True,
        ('BC','EB'):True,
        ('BC','DB'):True,
        ('AC','EB'):True,
        ('AC','EA'):True,
        ('AC','BD'):True,
        ('AC','DA'):True,
        ('AC','DB'):True,
        ('BD','AB'):True,
        ('BD','AC'):True,
        ('BD','DA'):True,
        ('BD','EC'):True,
        ('BD','EB'):True,
        ('EA','AC'):True,
        ('EA','AB'):True,
        ('EA','AD'):True,
        ('AD','EA'):True,
        ('AD','EB'):True,
        ('AD','EC'):True,
        ('DA','AB'):True,
        ('DA','AC'):True,
        ('DA','BD'):True,
        ('DA','EB'):True,
        ('DA','EC'):True,
        ('DB','AC'):True,
        ('DB','BC'):True,
        ('DB','EC'):True,
        ('EC','BD'):True,
        ('EC','DA'):True,
        ('EC','DB'):True,
        ('EC','AD'):True
}
# 计算所有的路
verbs=[]
for key,value in result.items():
    k1,k2=key
    verbs.append(k1)
    verbs.append(k2)
verbs=list(set(verbs))
print(verbs)
def not_adjacent_with_set(v,new_group,result):
    if len(new_group)==0:
        return True
    else:
        con=True
        for i in new_group:
            if (i,v) in result or (v,i) in result:
                con=False
        return con
def coloring(result,verbs):
    color=0
    groups=[]
    verts=verbs
    while len(verts)>0:
        new_group=[]
        for v in verts:
            if not_adjacent_with_set(v,new_group,result):
                new_group.append(v)
                verts.remove(v)
        groups.append((color,new_group))
        color+=1
    return groups
coloring(result,verbs)

[(0, ['EC', 'EA', 'EB']),
 (1, ['BD', 'DB', 'AD']),
 (2, ['AB']),
 (3, ['AC', 'BC']),
 (4, ['DA'])]

from random import shuffle
groups=[]
for i in range(100):
    verbs=[]
    for key,value in result.items():
        k1,k2=key
        verbs.append(k1)
        verbs.append(k2)
    verbs=list(set(verbs))
    shuffle(verbs)
    new_result=coloring(result,verbs)
    groups.append(new_result)
print(len(groups))