Использование lru_cache с генераторами в рекурсивной функции для поиска вершин ⇐ Python

[Anonymous]

Я впервые задаю вопрос, но он настолько странный, что я считаю, что, возможно, стоит задать его здесь. Я решаю задачу, в которой у меня есть граф с двумя типами вершин: те, которые нельзя удалить, и те, которые можно удалить. Я хочу удалить как можно больше вершин из моего графа, сохраняя при этом нужные вершины связанными. Я решил применить решение методом грубой силы, но хочу быть умным и использовать декоратор lru_cache functools, чтобы избежать пересчета различных перестановок одних и тех же вершин. Есть ли какой-нибудь способ сделать это эффективно?
Ниже приведен первый вариант кода, на котором я остановился:

Код: Выделить всё

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]]

Мой вопрос: действительно ли lru_cache что-нибудь делает? Я немного не в теме, и буду благодарен за любые советы/понимание

Подробнее здесь: https://stackoverflow.com/questions/793 ... -searching