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() g.add_nodes_from(range(1, 5 + 1)) 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: g.add_edge(u, v) 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?