Counting number of directed cycles of ellipsis lists in python

Question

I am trying to write a code that counts the number of cycles in a data structure. An example would be:

A = [(), ()]
B = [A, A]
A[0] = B
A[1] = B

So if we draw a box and pointer diagram, there will be 4 cycles:

(index 0, B) -> (index 0, A) -> index(0, B)
(index 0, B) -> (index 1, A) -> index(0, B)
(index 1, B) -> (index 0, A) -> index(0, B)
(index 1, B) -> (index 1, A) -> index(0, B)

I have found posts related to this, the most promising one being: Finding all cycles in a directed graph

But my main problem is that ellipsis list such as the one above is an absolute pain to work with. For example, testing membership

C = [A, B]
B in A     # Gives an error here

This results in other problems. For example, in the post i mentioned above, the solutions recommend building an adjacency list. But first, you have to find a way to label these nodes. The way I did it is:

(0, A) 
(1, A)
(0, B)
(1, B)

Problem is, if you try an construct a dictionary with these as the keys, you will get an error.

What I have managed to come up with so far:

def check_repeated_nodes(tup_lst):   # To test for membership since we cannot use "in"
    unique_nodes = []
    repeated_nodes = []    # If this list is not empty, there is a repeated node and hence a cycle
    for idx, lst in tup_lst:
        is_unique = True       # flag to test the uniqueness of a node
        for unique_idx, unique_lst in unique_nodes:
            if lst is unique_lst and idx is unique_idx:
                repeated_nodes.append((idx, lst))
                is_unique = False
        if is_unique:
            unique_nodes.append((idx, lst))
    return len(repeated_nodes) > 0


def count_cycles(lst):
    cycle_lst = []

    def helper(lst, track = []):
        for i in range(len(lst)):
            node = (i, lst)     # We label a node as (index, list)
            track.append(node)     # append to the tracker list
            if check_repeated_nodes(track):   # If there is a repeated node, we append to our cycle list
                cycle_lst.append(track)
            else:
                if type(lst[i]) == list:     # check if lst[i] is also a node
                    helper(lst[i], track)     # execute the process again if it is a node

    helper(lst)
    return len(cycle_lst)    # The length of this list is the number of cycles

The output I hoped to get was:

[
    [(0, B), (0, A), (0, B)], 
    [(0, B), (1, A), (0, B)],
    [(1, B), (0, A), (0, B)], 
    [(1, B), (1, A), (0, B)]
]

But what I got instead was:

[
    [(0, B), (0, A), (0, B)], 
    [(0, B), (0, A), (0, B), (1, A)], 
    [(0, B), (0, A), (0, B), (1, B), (1, A)], 
    [(0, B), (0, A), (0, B), (1, B), (1, A), (1, B)]
]

I suspect the problem is a backtracking issue? Like the function doesn't return to the start point if it hits a cycle. I have been trying to resolve this for days but I cannot come up with a valid solution. Any advice?

Counting number of directed cycles of ellipsis lists in python

0 Answers0