I've hit a challenge with my personal accounting app I can't even imagine how to approach.

The script is generating some JSON for a Sankey diagram which shows cash moving through the ledgers:

The issue is that the Sankey goes wrong if the cash moves in a circle, eg from Ledger A to Ledger B to C and back to A.

I'm trying to write some code that will evaluate the data and if there's a circular movement then it should break that circle by removing one of the links.

The code starts with a dictionary of dictionaries which contains the amount of cash that's moving between each possible pair of ledgers. The top dictionary contains the ledgers as keys and another dictionary of ledgers as the values. The inner dictionary contains the ledgers as keys and amount of cash moving as the value.

Below is a print(str(dict)) of the dictionary. Zeros mean there's no cash moving between the two ledgers. Have had to truncate due to Stack Overflow charactor limit.

Would you suggest how to even approach this?

{<Ledger: Basic food>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Benefits>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, 
<Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Books>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Clothing>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Coffee & Snacks>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer 
& Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, 
<Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Computer & Electrical>: {<Ledger: Basic food>: 0, <Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: 
Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal 
Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Council tax>: {<Ledger: Basic food>: 0, 
<Ledger: Benefits>: 0, <Ledger: Books>: 0, <Ledger: Clothing>: 0, <Ledger: Coffee & Snacks>: 0, <Ledger: Computer & Electrical>: 0, <Ledger: Council tax>: 0, <Ledger: Electricity & Gas>: 0, <Ledger: Grooming>: 0, <Ledger: Hobbies>: 0, <Ledger: Home Supplies>: 0, <Ledger: Income tax>: 0, <Ledger: Jacks Account>: 0, <Ledger: Jacks Float>: 0, <Ledger: Jacks Income>: 0, <Ledger: Jacks Monzo>: 0, <Ledger: Janes Account>: 0, <Ledger: Janes Float>: 0, <Ledger: Janes Income>: 0, <Ledger: Janes Monzo>: 0, <Ledger: Joint Account>: 0, <Ledger: Lodger>: 0, <Ledger: Mortgage Interest>: 0, <Ledger: Mortgage Payments>: 0, <Ledger: Mortgages>: 0, <Ledger: Personal Gear>: 0, <Ledger: Profit & Loss Accounts>: 0, <Ledger: Property>: 0, <Ledger: Public Transport>: 0, <Ledger: Take away>: 0, <Ledger: Tax Liability>: 0, <Ledger: Taxis>: 0, <Ledger: Toys>: 0}, <Ledger: Electricity & Gas>: 

... truncated

CodePudding user response：

Check out the example below. "all_ledgers" is supposed to represent your top-level dictionary. It loops through the keys with positive values recursively, returning True if it ever encounters the initial target (the start value on the first iteration). If it makes it through the whole search without finding a cycle, it returns False. The cache is there to prevent an infinite loop.

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.")