Find global ordering from local ordering

user_2092731 0
Viewed 54

Suppose you have a list of tuples

[(a,d), (a,c), (b,c), (a,b), (c,d)]

with the second element of a tuple greater that the first

assume there is only one ordered list (containing all the elements that show up in at least one tuple) consistent will all tuples. In this case the list

[a,b,c,d]

How do we find the list?

graph-theory python
2 Answers

In the simplest case, your objects are instances of a class in which methods __eq__, __hash__ and __lt__ are defined. The first two methods allow you to use set while the third method allows you to use sorted. Here is an example (lst is your initial list of tuples):

sorted_elements = sorted({el for t in lst for el in t})

You can use the previous solution with numbers and chars (this is just an example):

>>> lst = [(3,4), (7,8), (7,9), (1,3)]
>>> sorted_elements = sorted({el for t in lst for el in t})
>>> sorted_elements
[1, 3, 4, 7, 8, 9]

>>> lst = [('a','b'), ('c','e'), ('c','z')]
>>> sorted_elements = sorted({el for t in lst for el in t})
>>> sorted_elements
['a', 'b', 'c', 'e', 'z']

In a more general case, you might want to use topological sorting (for example, by using the networkx package). In this case your objects are of type A:

import networkx as nx

G = nx.DiGraph()
G.add_edges_from(lst)

sorted_elements = list(nx.topological_sort(G))

Here is an example:

import networkx as nx

class A:
    def __init__(self, name):
        self.name = name

a, b, c, d = A('a'), A('b'), A('c'), A('d')
lst = [(a,d), (a,c), (b,c), (a,b), (c,d)]

G = nx.DiGraph()
G.add_edges_from(lst)

sorted_elements = list(nx.topological_sort(G))

print([el.name for el in sorted_elements]) # ['a', 'b', 'c', 'd']
user_52961060

Thanks to Jason Harper who noted that the problem is known as topological sorting.

The module graphlib (requires python3) does this. However, you have to get graphlib-backport

        pip3 uninstall graphlib
        pip3 install graphlib-backport

Before I did this I had a very old version of graphlib

from graphlib import TopologicalSorter
  
# creating an instance of TopologicalSorter
# initial graph is optional
ts = TopologicalSorter()
  
ts.add('d','a')
ts.add('c','a')
ts.add('c','b')
ts.add('b','a')
ts.add('d','c')
print([*ts.static_order()])


#Output
['a', 'b', 'c', 'd']
user_20927310
Related