Próbuję znaleźć wszystkie ścieżki z jednego lub więcej połączonych drzew za pomocą Pythona, na przykład, jeśli moje dane to:

a=pd.DataFrame({'predecessor':[1,2,1,4,5,5,5,7,7,10,11,11,8,8,8,14,14,14,16,16,21,16,15,15],
                'successor':[2,3,4,5,6,7,8,9,10,11,12,13,17,18,19,8,15,16,20,21,23,22,19,20]})

Poprzednik i następca oznacza, że dwie liczby są połączone. Tak więc moje drzewa przy użyciu tych danych będą wyglądać:

enter image description here

Co chcę mieć wszystkie ścieżki. Jedna ścieżka jest jak [1,2,3] lub [1,4,5,7 10,11,13]. Moje prawdziwe dane są ogromne, więc użycie ramki danych do przechowywania wszystkich ścieżek nie jest dobrym pomysłem. Może przydatna jest lista list, w której przydatna jest każda poduba, jest przydatna kompletna ścieżka. Mam nadzieję, że wynik jest jak:

[[1,2,3], 
 [1,4,5,7,10,11,13],
 [14,8,17],
 [14,16,21,23],
 ......]

Czy ktoś może mi pomóc?

0
Feng Chen 31 lipiec 2020, 12:17

1 odpowiedź

Najlepsza odpowiedź
import pandas as pd


a = pd.DataFrame({'predecessor': [1, 2, 1, 4, 5, 5, 5, 7, 7, 10, 11, 11, 8, 8, 8, 14, 14, 14, 16, 16, 21, 16, 15, 15],
                  'successor': [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 18, 19, 8, 15, 16, 20, 21, 23, 22, 19, 20]})

# loop to store all the parent-child nodes and find out the root nodes and end nodes.
# A root node is a node only in 'predecessor' but not in 'successor'
# An end node is a node only in 'successor' but not in 'predecessor'
root_nodes = set()
end_nodes = set()
node_relations = {}
for i in range(len(a['predecessor'])):
    predecessor = a['predecessor'][i]
    successor = a['successor'][i]
    if predecessor not in node_relations.keys():
        node_relations[predecessor] = []
    node_relations[predecessor].append(successor)
    if predecessor not in a['successor'].values:
        root_nodes.add(predecessor)
    if successor not in a['predecessor'].values:
        end_nodes.add(successor)

# DFS + Memorization
def get_routes(root, memory):
    # when already in memory
    if root in memory.keys():
        return memory[root]
    # when it is the end node, return node itself as the routes
    if root in end_nodes:
        memory[root] = [[root]]
        return memory[root]
    # Loop all the successor routes and add root node before all of them
    memory[root] = []
    for successor in node_relations[root]:
        for route in get_routes(successor, memory):
            memory[root].append([root] + route)
    return memory[root]

# Loop from root nodes
memory = {}
result = []
for root in root_nodes:
    result.extend(get_routes(root, memory))

1
Jack Song 31 lipiec 2020, 10:16