Удаление циклических данных в словаре словарей

Я столкнулся с проблемой в своем приложении для ведения личной бухгалтерии, к которой не могу даже представить, как подступиться.

Сценарий генерирует JSON для диаграммы Sankey, которая показывает движение денег через бухгалтерские книги:

Sankey diagram in accounting app

Проблема в том, что Sankey работает неправильно, если наличные перемещаются по кругу, например, из регистрационной книги A в регистрационную книгу B, в C и обратно в A.

Я пытаюсь написать код, который будет оценивать данные и если есть круговое движение, то он должен разорвать этот круг, удалив одну из связей.

Код начинается со словаря словарей, который содержит сумму наличности, перемещающуюся между каждой возможной парой бухгалтерских книг. Верхний словарь содержит бухгалтерские книги в качестве ключей и другой словарь бухгалтерских книг в качестве значений. Внутренний словарь содержит бухгалтерские книги в качестве ключей и количество перемещаемых наличных денег в качестве значения.

Ниже приведен print(str(dict)) словаря. Нули означают отсутствие движения денег между двумя бухгалтерскими книгами. Пришлось усечь из-за ограничения количества символов в Stack Overflow.

Посоветуйте, как вообще к этому подступиться?

... truncated

Посмотрите на пример ниже. "all_ledgers" должен представлять ваш словарь верхнего уровня. Он рекурсивно перебирает ключи с положительными значениями, возвращая True, если встречает начальную цель (начальное значение на первой итерации). Если он проходит весь поиск, не найдя цикла, он возвращает False. Кэш используется для предотвращения бесконечного цикла.

all_ledgers={'a':{'b':0,'c':1},
      'b':{'a':1},
      'c':{'b':1}}

def find_cycle(start,target=""):
    if target=="":
        target=start
    try:
        cache
    except NameError:
        cache = [start]
    for ledger in all_ledgers[start].keys():
        if all_ledgers[start][ledger]>0 and ledger==target:
            return True
        elif all_ledgers[start][ledger]>0 and ledger not in cache:
            cache.append(ledger)
            return find_cycle(ledger,target)
    return False
        
if find_cycle('a'):
    print("There is a cycle.")
else:
    print("There is no cycle.")

Исходя из ответа @JacobDavis, вам нужно дать ему завершить цикл. В нынешнем виде он может выйти слишком рано после нахождения первой передачи.

ledgers = {
  "a": {"a": 0, "b": 1, "c": 0, "d": 0, "e": 0},
  "b": {"a": 0, "b": 0, "c": 1, "d": 1, "e": 0},
  "c": {"a": 0, "b": 0, "c": 0, "d": 0, "e": 1},
  "d": {"a": 1, "b": 0, "c": 0, "d": 0, "e": 0},
  "e": {"a": 0, "b": 0, "c": 0, "d": 0, "e": 0}
}


def find_cycle(all_ledgers: dict, start: str, target="", cycle=()):
    cycle = tuple(list(cycle) + [start])
    if target == "":
        target = start

    for ledger in all_ledgers[start].keys():
        if all_ledgers[start][ledger] > 0 and ledger == target:
            return True, cycle
        elif all_ledgers[start][ledger] > 0 and ledger not in cycle:
            flag, cycle2 = find_cycle(all_ledgers, ledger, target, cycle)

    if flag:  # this if will let the loop finish
                cycle = cycle2
                return True, cycle
    else:  # if the loop finished w/o finding a cycle return false
        return False, cycle


for sub_ledger in ledgers.keys():
    chk, cyc = find_cycle(ledgers, sub_ledger)
    if chk:
        print(f"There is a cycle starting in ledger {sub_ledger}: {cyc}")
    else:
        print(f"There is no cycle starting in ledger {sub_ledger}")

Я немного модифицировал функцию, чтобы она принимала исходные данные и выводила обнаруженный цикл. Если вы запустите ее на всех субрегистрах, вы должны найти все циклы. Если перед переходом к следующей книге вы разорвете связь, то она не должна выскочить при проверке следующей книги.

Вернуться на верх