Verwendung von lru_cache mit Generatoren in einer rekursiven Funktion für die Scheitelpunktsuche
Posted: 12 Jan 2025, 05:26
Dies ist das erste Mal, dass ich eine Frage stelle, aber sie ist so seltsam, dass es sich meiner Meinung nach lohnen könnte, sie hier zu stellen. Ich löse ein Problem, bei dem ich ein Diagramm habe, das zwei Arten von Scheitelpunkten aufweist: solche, die nicht entfernt werden können, und solche, die entfernt werden können. Ich möchte möglichst viele Scheitelpunkte in meinem Diagramm entfernen und gleichzeitig die Verbindung der interessierenden Scheitelpunkte beibehalten. Ich habe mich für eine Brute-Force-Lösung entschieden, möchte aber klug vorgehen und den lru_cache-Dekorator von functools verwenden, um die Neuberechnung verschiedener Permutationen derselben Scheitelpunkte zu vermeiden. Gibt es eine Möglichkeit, dies effektiv zu tun?
Unten ist der erste Entwurf des Codes, für den ich mich entschieden habe:
Meine Frage lautet: Macht lru_cache tatsächlich etwas? Ich bin etwas überfordert und wäre für jede Anleitung/Einsicht dankbar 
Unten ist der erste Entwurf des Codes, für den ich mich entschieden habe:
Code: Select all
from functools import lru_cache
import networkx as nx
import numpy as np
from itertools import combinations
@lru_cache(maxsize=None)
def iter_node_2(
t_matrix: tuple[tuple],
must_retain_nodes: tuple,
removed_nodes: tuple, ):
# Since NDArrays are not hashable I bring in the array as a tuple
matrix = np.array(t_matrix)
G = nx.from_numpy_array(matrix)
for node in removed_nodes:
G.remove_node(node)
for node in G.nodes:
if node not in must_retain_nodes:
g_t = G.copy()
g_t.remove_node(node)
# check that every vertex that we care about is connected
if all([nx.has_path(g_t, *a) for a in combinations(must_retain_nodes,2)]):
new_removed_nodes = [*removed_nodes, node]
# sort the tuple to avoid different permutations of the same node
new_removed_nodes.sort()
temp_sol = list(iter_node_2(t_matrix, must_retain_nodes, tuple(new_removed_nodes)))
# collect solutions where multiple nodes are removed since yield only works with one recursive layer
for sol in temp_sol:
yield sol
yield new_removed_nodes
matrix = np.array([
[0,0,1,0,1,],
[0,0,0,1,1,],
[1,0,0,1,0,],
[0,1,1,0,0,],
[1,1,0,0,0,],
])
must_retain_nodes = (0,1)
hashable_matrix = tuple((tuple(a) for a in matrix))
solutions = list(iter_node_2(
hashable_matrix,
must_retain_nodes,
(),
))
print(solutions)
# should return: [[2, 3], [2], [2, 3], [3], [4]]