In python, with networkx, I have a large list li = [o1, o2, ...] of objects of a class Myclass. The class has a partial ordering for objects defined through the method __lt__. This is a strict ordering, as it is defined so that o1 < o1 is always False, and o1 < o2 and o2 < o1 cannot both be true. An example of strict partial order is set inclusion: we have the ordering {x} < {x,y} < {x,y,z}. But on the other hand, (a < b) == False does not imply (b < a) == True. For instance {z} < {x, y} AND {x, y} < {z} are both false because neither set can be included in the other. I am trying to build the Hasse diagram for large lists li. My current approach is to build a directed acyclic graph from the partial order and then use networkx transitive reduction to remove the transitive edges. import networkx as nx G = nx.DiGraph() G.add_nodes_from(li) n = len(li) for i in range(n): for j in range(n): if i == j: continue if li < li[j]: G.add_edge(li[j], li) hasse_diagram = nx.transitive_reduction(G) The problem with this is that the first step is O(n^2), so for large lists the graphs quickly become gigantic and despite the transitive reduction itself being optimised, it quickly takes a lot of time. Is there a way to optimise the process? Continue reading...
