finding_circles.py

good_ones = [
    [],
    [
        {
            'id': 1,
            'links': [2, 4]
        },
        {
            'id': 2,
            'links': [4]
        },
        {
            'id': 4,
            'links': []
        }
    ],
    [
        {
            'id': 1,
            'links': []
        },
        {
            'id': 3,
            'links': [6, 7]
        },
        {
            'id': 6,
            'links': [1, 7]
        },
        {
            'id': 7,
            'links': [1]
        }
    ],
    [
        {
            'id': 1,
            'links': []
        }

    ]

]

bad_ones = [

    [
        {
            'id': 1,
            'links': []
        },
        {
            'id': 2,
            'links': [4]
        },
        {
            'id': 4,
            'links': [5]
        },
        {
            'id': 5,
            'links': [2]
        }
    ],
    [
        {
            'id': 1,
            'links': []
        },
        {
            'id': 2,
            'links': [4]
        },
        {
            'id': 4,
            'links': [1, 6]
        },
        {
            'id': 6,
            'links': [2]
        }
    ],
    [
        {
            'id': 1,
            'links': []
        },
        {
            'id': 3,
            'links': [6, 7]
        },
        {
            'id': 6,
            'links': [1, 7]
        },
        {
            'id': 7,
            'links': [1, 3]
        }
    ],
    [
        {
            'id': 1,
            'links': [1]
        }

    ],
]

def find_data_elment(id, data):

    d = filter(lambda element: element['id'] == id, data)

    return d[0]


def circular_so_far(elements_so_far, link_id, data):

    new_elements_so_far = elements_so_far + [link_id]

    if len(new_elements_so_far) != len(set(new_elements_so_far)):
        print 'Circle found - elments:', new_elements_so_far
        return True

    new_links = find_data_elment(link_id, data)['links']

    for link in new_links:

        if circular_so_far(new_elements_so_far, link, data):
            return True

    return False


def is_circular(data):

    for element in data:

        id = element['id']

        if circular_so_far([], id, data):
            return True

    return False



for good in good_ones:
    assert is_circular(good) == False

for bad in bad_ones:
    assert is_circular(bad) == True