从成对列表中查找所有最大有向连通组

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

看起来，您想要找到包含图中每个节点的最大集团，其中v的最大团是包含v的最大完整子图。

在NetworkX中，我们有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']]