python - 将图划分为完整子图的算法
问题描述
我需要一种算法来将无向图的顶点划分为一个或多个子图,这样每个子图都是一个完整的图(每个顶点都与其他每个顶点相邻)。每个顶点都需要恰好位于其中一个子图中。
这是一个例子:
input = [
(A, B),
(B, C),
(A, C),
(B, D),
(D, E),
]
output = myalgo(input) # [(A, B, C), (D, E)]
这是一个更好地描述问题的图像:
输入列表按距离降序排序,这就是我连接 ABC 而不是 BD 的原因。
我认为这可能被称为“强连接组件”,并且已经尝试了以下解决方案:
在无向图中找到强连通分量:它正在寻找不同的东西
在无向图中查找所有循环:它给了我很多循环而不是最好的循环,它不关心输入顺序。
一种从 python 中的数据对创建集群的算法:它连接所有组件,只是因为它们之间有一条路径(ABCDE)。
Kosaraju 的算法:它只适用于有向图。
解决方案
这是一个将分割实现为完整子图的类。它绝不是优化的,可能会得到显着改进,但它是一个起点
class SCCManager:
def __init__(self, edges):
self.clusters = []
self.edges = edges
def clusters_in(self, conn):
first, second = conn
f_clust = None
s_clust = None
for i, clust in enumerate(self.clusters):
if first in clust:
f_clust = i
if second in clust:
s_clust = i
# break early if both already found
if f_clust and s_clust:
break
return (f_clust, s_clust)
def all_connected(self, cluster, vertex):
for v in cluster:
connected = (v, vertex) in self.edges or (vertex, v) in self.edges
# break early if any element is not connected to the candidate
if not connected:
return False
return True
def get_scc(self):
for edge in self.edges:
c_first, c_second = self.clusters_in(edge)
# case 1: none of the vertices are in an existing cluster
# -> create new cluster containing the vertices
if c_first == c_second == None:
self.clusters.append([edge[0], edge[1]])
continue
# case 2: first is in a cluster, second isn't
# -> add to cluster if eligible
if c_first != None and c_second == None:
# check if the second is connected to all cluster components
okay = self.all_connected(self.clusters[c_first], edge[1])
# add to cluster if eligible
if okay:
self.clusters[c_first].append(edge[1])
continue
# case 3: other way round
if c_first == None and c_second != None:
okay = self.all_connected(self.clusters[c_second], edge[0])
if okay:
self.clusters[c_second].append(edge[0])
continue
# case 4: both are in different clusters
# -> merge clusters if allowed
if c_first != c_second:
# check if clusters can be merged
for v in self.clusters[c_first]:
merge = self.all_connected(self.clusters[c_second], v)
# break if any elements are not connected
if not merge:
break
# merge if allowed
if merge:
self.clusters[c_first].extend(self.clusters[c_second])
self.clusters.remove(self.clusters[c_second])
# case 5: both are in the same cluster
# won't happen if input is sane, but doesn't require an action either way
return self.clusters
...这是一个工作示例:
inp = [
('A', 'B'),
('B', 'C'),
('A', 'C'),
('B', 'D'),
('D', 'E'),
('C', 'E')
]
test = SCCManager(inp)
print(test.get_scc())
[['A', 'B', 'C'], ['D', 'E']]
推荐阅读
- javascript - 使用 jquery 或 react 或 node 通过 Linkedin 发送邀请
- python - Python Plotly 显示值的标签
- testing - 遇到未定义提供程序的错误!即使定义了提供程序也会遇到
- javascript - Ajax 调用返回函数而不是数据
- c++ - 比 scanf() 或 cin 更快地将整数输入数组的方法?
- vue-router - Nuxt vue-router如何动态路由到页面
- visual-studio-code - Visual Studio Code:查找空文件
- android - 如何将图像意图共享给其他应用程序(在 WhatsApp 和其他应用程序等应用程序中共享图像)?
- android - 为什么我在 listAdapter 上得到空值?
- vba - 如何删除除最新邮件外的邮件?