从对列表中找到所有最大的有向连通组

Question

我想从以下对中找出最大的有向连通群。

pairs = [
    ('creepy', 'sports'), 
    ('AskReddit', 'creepy'),
    ('AskReddit', 'boardgames'), 
    ('AskReddit', 'television'), 
    ('AskReddit', 'movies'), 
    ('AskReddit', 'history'), 
    ('sports', 'television'), 
    ('creepy', 'movies'), 
    ('history', 'television'), 
    ('movies', 'sports'), 
    ('creepy', 'television'), 
    ('movies', 'television')
]

我需要的输出是：

第 1 组：('creepy', 'sports', 'television', 'movies')
第 2 组：('creepy', 'AskReddit', 'movies', 'television')
第 3 组：('AskReddit', 'boardgames')
第 4 组：('AskReddit', 'history', 'television')

例如，我不想拥有组 ('AskReddit', 'history', 'television', 'boardgames')，因为没有从 'boardgames' 到 'television' 和 'history' 的定向连接。

我使用有向图进行了很多次尝试。我认为这是我想找到的在图论中有一个特定名称但我真的想不起来了。我的第一次尝试是使用 DFS，我如何创建它们的链，但输出包含我上面提到的组，我不想拥有它。

我用Python.

欢迎大家发表意见！提前致谢。

Answer 1

您似乎想要找到包含图中每个节点的最大 cliques，其中 v 的最大团是包含 v 的最大完整子图。

在 NetworkX we have nx.find_cliques 中，正是这样做的：

G=nx.Graph()
G.add_edges_from(pairs)
max_cliques = list(nx.find_cliques(G))

print(max_cliques)
[['boardgames', 'AskReddit'],
 ['television', 'sports', 'creepy', 'movies'],
 ['television', 'AskReddit', 'history'],
 ['television', 'AskReddit', 'creepy', 'movies']]

从对列表中找到所有最大的有向连通组

Find all the maximum directed connected groups from a list of pairs

python

algorithm

graph

networkx