将图分成完全子图的算法

Question

我需要一个算法，将无向图的顶点划分为一个或多个子图，以使每个子图都是完全图 (每个顶点都与其他每个顶点相邻)。每个顶点必须恰好属于其中一个子图。

以下是一个示例：

input = [
    (A, B),
    (B, C),
    (A, C),
    (B, D),
    (D, E),
]
output = myalgo(input)  # [(A, B, C), (D, E)]

下面是更好描述问题的图片:

输入列表按距离降序排序，这就是为什么我连接A-B-C而不是B-D的原因。

我认为这可能称为“强连通分量”，并已经尝试了以下解决方案：

• 在无向图中查找强连通分量: 它寻找的是不同的东西

• 在无向图中查找所有循环: 它给我许多循环，并且并不是最好的，它不关心输入顺序。

• 一个从数据对中创建集群的算法 in Python: 它连接了所有分量，只因为它们之间有一条路径(A-B-C-D-E)。

• Kosaraju算法: 它只适用于有向图。

- MarcoBuster

---

“强连接”是指“组件内的所有元素必须直接相互链接”吗？ - Lukas Thaler

@LukasThaler 是的 - MarcoBuster

听起来像是一个有趣的练习。让我看看我能想出什么 :D - Lukas Thaler

Answer 1

这是一个实现将图分割为完整子图的类。它并不是经过优化的，可能可以显著改进，但它是一个起点。

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']]

- Lukas Thaler

---

如果输入是一个去掉一条边的大团，则正确答案是所有分割该缺失边的顶点集合。你更喜欢哪个？ - Dave

这是由用户输入决定的。OP在他们的问题中提到了边的顺序很重要。如果上面图中的(B,D)边是第一个输入的，我们将得到组件(A,C)和(B,D)，(以及(E)，如果你想考虑它作为一个组件，但我的实现目前不考虑它)。 - Lukas Thaler

Answer 2

from collections import defaultdict


def create_adjacency_matrix(connections):
    matrix = defaultdict(dict)
    for a, b in connections:
        matrix[a][b] = 1
        matrix[b][a] = 1
    return matrix


def is_connected_to_all(vertex, group, matrix):
    for v in group:
        if vertex != v and vertex not in matrix[v]:
            return False
    return True


def group_vertexes(input):
    matrix = create_adjacency_matrix(input)
    groups = []
    current_group = set()
    for vertex in matrix.keys():
        if is_connected_to_all(vertex, current_group, matrix):
            current_group.add(vertex)
        else:
            groups.append(current_group)
            current_group = {vertex}
    groups.append(current_group)
    return groups

input = [("A", "B"), ("B", "C"), ("A", "C"), ("B", "E"), ("E", "D")]
print(group_vertexes(input))
# [{'C', 'B', 'A'}, {'D', 'E'}]

警告：这依赖于Python 3.7+中dict保持插入顺序的事实。在旧版本中，您必须使用matrix = DefaultOrderedDict(dict) https://dev59.com/SG025IYBdhLWcg3wJCVD#35968897：

- RafalS

---

矩阵是一个不错的想法，但如果我在输入中添加另一个 ('C', 'E')，算法就会出错。我认为更新逻辑需要更加健壮，以处理更复杂的输入。 - Lukas Thaler

你能提供整个错误的输入吗？因为我测试过，对于当前输入末尾的 ('C','E') 是有效的。 - RafalS

inp = [('A', 'B'),('B', 'C'),('A', 'C'),('B', 'D'),('D', 'E'),('C', 'E')] 的结果为 [{'B', 'C', 'A'}, {'E', 'D'}, {'E', 'C'}]。 - Lukas Thaler

所以你可能使用的是低于3.7版本的Python，因为我依赖于字典保持插入顺序。 - RafalS

实际上是在3.7上运行的。对于这个输入，你得到了什么输出？ - Lukas Thaler

是的，你说得对 :P。我运行了一个修改过的版本，其中使用了for vertex in matrix.keys():这个替代选项。我修改了第一个版本以使用正确的逻辑。 - RafalS

Answer 3

另一次尝试：

。

lst = [
    ('A', 'B'),
    ('B', 'C'),
    ('A', 'C'),
    ('B', 'D'),
    ('D', 'E'),
]

d = {}
for i, j in lst:
    d.setdefault(i, []).append(j)
    d.setdefault(j, []).append(i)

from itertools import combinations

rv, seen_segments, seen_vertices = [], set(), set()
for k, v in d.items():
    if len(v) == 1:
        segment = set((k, v[0])).difference(seen_vertices)
        seen_vertices.update(segment)
        rv.append([tuple(segment), ])
    else:
        graph = []
        for i, j in combinations([k] + v, 2):
            if not j in d[i]:
                break
            else:
                graph.append(tuple(sorted((i, j))))
        else:
            if graph:
                graph = [segment for segment in graph if segment not in seen_segments]
                seen_segments.update(graph)
                if graph:
                    rv.append(graph)

from pprint import pprint
pprint(rv)

输出：

[[('A', 'B'), ('A', 'C'), ('B', 'C')], [('D', 'E')]]

---

对于输入

lst = [
    ('A', 'B'),
    ('B', 'C'),
]

输出：

[[('A', 'B')], [('C',)]]

---

对于输入：

lst = [
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'D'),
]

输出：

[[('B', 'A')], [('D', 'C')]]

- Andrej Kesely

Answer 4

你可以找到所有路径，然后按连通性进行分组：

from itertools import groupby as gb
d = [('A', 'B'), ('B', 'C'), ('A', 'C'), ('B', 'D'), ('D', 'E')]
def connect_num(node):
    return [sum(a == node for a, _ in d), sum(b == node for _, b in d)]

def group_paths(data):
   new_d = sorted([[i, connect_num(i)] for i in data], key=lambda x:max(x[1]))
   return [[k for k, _ in b] for _, b in gb(new_d, key=lambda x:max(x[1]))]

def get_paths(start, c = [], seen = []):
   new_vals = [a for a, _ in d if a not in seen+c]
   if (vals:=[b for a, b in d if a == start]):
      for i in vals:
         yield from get_paths(i, c=c+vals, seen=seen)
   else:
      yield c
      for i in new_vals:
         yield from get_paths(i, c = [i], seen=c+seen)

result = sorted(map(set, get_paths(d[0][0])), key=len, reverse=True)
new_result = [a for i, a in enumerate(result) if not any(all(k in c for k in a) for c in result[:i])]
final_result = [group_paths(i) for i in new_result]

输出：

#final_result[0]
[['E', 'D'], ['A', 'C', 'B']]

- Ajax1234