# efficiently find connected components in undirected graph considering transitive equivalence

I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By "equal" I mean transitive equivalence: If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx
import itertools
from matplotlib import pyplot as plt

EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}

def foo(u, v):
# this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.
return (u, v) in EQUAL_EDGES

def main():
g = nx.Graph()
for u, v in itertools.combinations(g.nodes, 2):
are_equal = foo(u, v)
print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
if are_equal:

conn_comps = nx.connected_components(g)
nx.draw(g, with_labels=True)
plt.show()
return conn_comps

if __name__ == '__main__':
main()


the problem with this approach is that I get many redundant checks that I would like to avoid:

1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2!=3  # redundant check, if 1==2 and 1==3 then 2==3
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok


I want to avoid running in O(n^2) time complexity. What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?

• You might want to reframe your question so it does not rely as much on the Python programming language. Otherwise, it potentially becomes a "programming" question and, hence, off-topic (though you might ask it, for instance, on Stack Overflow). – dkaeae Jan 28 '19 at 14:40