CODEWITHSUNDEEP
pythongraphnetworkx
Alireza
Alireza

Reputation: 420

Finding the nodes with exactly similar inputs from other nodes in Networkx

What is a fast way to find the groups of nodes that have the exactly same input edges from the exactly same nodes in Networkx?

For example if the graph is

1->2
1->3
1->4
3->4

then only nodes 2 and 3 are similar. And the result would be

[[2, 3]]

Upvotes: 0

Views: 94

Answers (1)

Ben Grossmann
Ben Grossmann

Reputation: 4772

It seems as though what you're looking for is this. Given a directed graph, you're looking for groups of nodes such that two nodes u,v are in the same group whenever the set of nodes w for which w->u is an edge is the same as the set of nodes w for which w->v is an edge.

To put it another way, you're looking for groups of nodes such that for any u,v in the same group, the adjacency lists of u and v within the reversed graph are the same.

If I have interpreted your question correctly, then you should find the following script to be useful.

import networkx as nx
from collections import defaultdict

edges = [[1,2],[1,3],[1,4],[3,4]]
G = nx.DiGraph()
G.add_edges_from(edges)

source_list = defaultdict(list)
for n,d in G.reverse().adjacency():
    source_list[tuple(sorted(d))].append(n)
groups = list(source_list.values())

print(groups)                           # [[1], [2, 3], [4]]
print([g for g in groups if len(g)>1])  # [[2, 3]]

Upvotes: 2

Related Questions