CODEWITHSUNDEEP
pythonalgorithmgraphnetworkx
heiLou
heiLou

Reputation: 207

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

I would like to find out the maximum directed connected groups from the following pairs.

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

The output that I need to have is:

For example, I do not want to have the group ('AskReddit', 'history', 'television', 'boardgames') because there is not a directed connection from 'boardgames' both to 'television' and 'history'.

I made many many tries using directed graphs. I think that this is that I want to find has a specific name in graph theory but I really can not remember it. My first try was with DFS and how can I create a chain of them but the output contains the group that I refer above and I do not want to have it.

I use Python.

All your comments are welcome! Thanks in advance.

Upvotes: 1

Views: 777

Answers (1)

yatu
yatu

Reputation: 88285

It looks like you want to find the maximal cliques containing each node in the graph, where a maximal clique for v is a largest complete subgraph containing v.

In NetworkX we have nx.find_cliques, which does exactly that:

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

Upvotes: 1

Related Questions