您需要的是一个可以计算图中连通组件的算法。虽然您可以使用DFS或BFS手动编写它,但有时使用现成的解决方案(例如
scipy.sparse.csgraph.connected_components)更方便。
您必须以一种算法可以处理的方式转换您的图。
键和值反转
反转键和值并构建字典dct
。
from collections import defaultdict
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
edge_dict = {
'ED7':[[15,-10,0], [20,-10,0]],
'ED10':[[0,0,0],[10,0,0]],
'ED13':[[15,0,0], [20,0,0]],
'ED4':[[20,0,0], [25,0,0]],
'ED2':[[15,0,0], [10,0,0]],
'ED5':[[0,-10,0],[10,-10,0]],
'ED6':[[15,-10,0], [10,-10,0]],
'ED8':[[20,-10,0], [25,-10,0]]
}
edge_pairs = [ ['ED10', 'ED5'], ['ED4', 'ED8'] ]
dct = defaultdict(list)
for item in edge_dict.items():
key = item[0]
value = item[1]
for lst in value:
hashed_lst = str(lst)
dct[hashed_lst].append(key)
print(dct)
这将是
dct
的输出结果。
邻接表
构建一个ED标签的邻接表,并将其命名为graph_dct
。如果两个标签之间存在一条边,则它们属于同一组。
graph_dct = defaultdict(list)
for lst in dct.values():
for item in lst:
for item2 in lst:
if item != item2:
graph_dct[item].append(item2)
print(graph_dct)
以下是graph_dct
的输出结果。
邻接矩阵
这是scipy连通组件算法的要求。我们必须将邻接表转换为邻接矩阵。它将被称为sparse_matrix
。
graph_dct_keys = list(graph_dct.keys());
sparse_matrix = []
for key in graph_dct_keys:
row = [0] * len(graph_dct_keys)
for item in graph_dct[key]:
row[graph_dct_keys.index(item)] = 1
sparse_matrix.append(row)
算法
现在我们将sparse_matrix
传递给连通组件算法,然后它会给你分组。
components = csr_matrix(sparse_matrix)
n_components, labels = connected_components(csgraph=components, directed=False, return_labels=True)
labels_dct = defaultdict(list)
for idx, item in enumerate(labels):
labels_dct[str(item)].append(graph_dct_keys[idx])
print(labels_dct.values())
results = list(labels_dct.values())
现在你有了一个名为
results
的列表,其中包含可以轻松构建您期望答案的标签列表。
排序
接下来,我们将根据要求对
results
进行排序,并生成期望的答案。
results = [['ED7', 'ED6', 'ED8', 'ED5'], ['ED10', 'ED2', 'ED13', 'ED4']]
rib1_edges = ['ED10', 'ED5']
rib2_edges = ['ED4', 'ED8']
for idx,lst in enumerate(results):
results[idx] = sorted(lst, key=lambda x: int(x.lstrip('ED')) )
for idx,lst in enumerate(results):
results[idx] = [ x for x in rib1_edges if x in lst ] + \
[ x for x in lst if x not in rib1_edges and x not in rib2_edges ] + \
[ x for x in rib2_edges if x in lst ]
print(results)
这将给出所需的结果,
[['ED5','ED6','ED7','ED8'],['ED10','ED2','ED13','ED4']]
。
获取答案
请注意,如果您使用Python 3.6以下版本,则无法保证此字典将按顺序插入。在这种情况下,键可能以任何Python内部算法确定的表面上随机的顺序出现。
因此,如果您正在运行Python 3.6+,可以使用字典,但为了可移植性,最好使用OrderedDict。
from collections import OrderedDict
edge_dict = {
'ED7':[[15,-10,0], [20,-10,0]],
'ED10':[[0,0,0],[10,0,0]],
'ED13':[[15,0,0], [20,0,0]],
'ED4':[[20,0,0], [25,0,0]],
'ED2':[[15,0,0], [10,0,0]],
'ED5':[[0,-10,0],[10,-10,0]],
'ED6':[[15,-10,0], [10,-10,0]],
'ED8':[[20,-10,0], [25,-10,0]]
}
result = [
['ED5', 'ED6', 'ED7', 'ED8'],
['ED10', 'ED2', 'ED13', 'ED4']
]
answer = []
for lst in result:
od = OrderedDict()
for item in lst:
od[item] = edge_dict[item]
answer.append(od)
import pprint
pp = pprint.PrettyPrinter()
pp.pprint(answer)
然后这将给我们期望的答案。
[OrderedDict([('ED5', [[0, -10, 0], [10, -10, 0]]),
('ED6', [[15, -10, 0], [10, -10, 0]]),
('ED7', [[15, -10, 0], [20, -10, 0]]),
('ED8', [[20, -10, 0], [25, -10, 0]])]),
OrderedDict([('ED10', [[0, 0, 0], [10, 0, 0]]),
('ED2', [[15, 0, 0], [10, 0, 0]]),
('ED13', [[15, 0, 0], [20, 0, 0]]),
('ED4', [[20, 0, 0], [25, 0, 0]])])]