Найдите все максимально направленные связанные группы из списка пар - PullRequest
Новая
       36

Найдите все максимально направленные связанные группы из списка пар

1 голос
/ 28 мая 2020

Я хотел бы узнать максимальное количество направленных связанных групп из следующих пар. 

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

Я много раз пытался использовать ориентированные графы. Я думаю, что это то, что я хочу найти, имеет конкретное c имя в теории графов, но я действительно не могу его вспомнить. Моя первая попытка была с DFS, и как я могу создать их цепочку, но результат содержит группу, о которой я говорю выше, и я не хочу ее иметь.

Я использую Python.

Все ваши комментарии приветствуются! Заранее спасибо.

1 Ответ

1 голос
/ 29 мая 2020

Похоже, вы хотите найти максимальные клики , содержащие каждый узел в графе, где максимальная клика для 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']]
...