Generating a hierarchy from a Python list

user_15346714 0
Viewed 180

I am using Python 3.8.

The following list contains integers and I need to generate a hierarchy from this list:

list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]

I need this result (output could be a list, e.g. [[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]):

1 ---- 15 ---- 121 ---- 155
 \---- 22 ---- 101
  \--- 23 ---- 105
        \----- 106
         \---- 108 ---- 120

2 ---- 19

5 ---- 25 ---- 28 ----- 29

8 ---- 33
 \---- 35

The hierarchy does not contain any duplicated items. Also first items of the lists in the list1 do not contain repeated/duplicated elements, but second items of the lists in the list1 contain.

How could this hierarchy be generated?

Note: I could do this by using some code but it could be very long and CPU cost could be high (actual list is very long).

hierarchy python-3.x list python
2 Answers

You can try using this recursive function, it is a bit verbose and can be re written using list comprehensions. need is your expected output.

list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]

need = [[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]

graph = {}

for y, x in list1:
    graph.setdefault(x, []).append(y)

def form_graph(graph):
    seen = set()

    def form(k, v):
        if k in seen:
            return []
        res = [[k]]
        res[-1].extend(v)
        seen.add(k)

        for i in v:
            if i in graph:
                res.extend(form(i, graph[i]))
        return res

    result = []
    for k, v in graph.items():
        temp = form(k, v)
        if temp:
            if len(temp) == 1:
                temp = temp[0]
            result.append(temp)
    return result

Output

print(form_graph(graph))
[[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]

print(need == form_graph(graph))
True

Upvote and accept the answer if you find this useful.

user_125029590

You can use a breadth-first search:

from collections import deque, defaultdict
list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]
def get_levels():
   q, r, d = deque(sorted({(b, b) for a, b in list1 if all(k != b for k, _ in list1)})), [], defaultdict(list)
   while q:
      r.append(((n:=q.popleft())[0], [n[-1], *(l:=[a for a, b in list1 if b == n[-1]])]))
      q.extend([(n[0], i) for i in l])
   for a, b in r:
      if len(b) > 1:
         d[a].append(b)
   return [i for b in d.values() for i in ([b] if len(b) > 1 else b)]

print(get_levels())

Output:

[[[1, 15, 22, 23], [15, 121], [22, 101], [23, 105, 106, 108], [121, 155], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]
user_73267380
Related