Finding pattern in tuples Python

Question

I've got pairs of integers stored in tuples (eg (1,2) (4,5) ...). These tuples are stored in a list.

I'm trying to find, among these tuples this kind of pattern (1,2) (2,3) (3,4) (4,1) which starts with whatever integer and then, jumping from the second integer of the tuple to the first of another tuple, ends with the integer that was picked up at the beginning.

Each pattern is stored in a set. Then I store the first integer and the related pattern as a key/value pair. With my example it becomes : dictionary={1:set([1,2,3,4]),...}

Then I merge the patterns which have items in common. For example (1,2) (2,3) (3,1) and (2,4) (4,1) are merged into this set : set([1,2,3,4]). And I delete one of the keys.

Here is my code :

from collections import defaultdict
dictio_chaine=defaultdict(set)
for item1 in A:               # A is the list containing the afore mentioned tuples
    a,b=item1
    l=[a,b]
    for item2 in A:
        if item2[0]==b and b!=a:
            b=item2[1]
            l.append(b)
        if b==a:
            break
    if l[-1]==a:
        dictio_chaine[a].update(l)

liste=combinations(dictio_chaine.iterkeys(),2)  #The following piece of code merges the
for item in liste:                                            #overlapping patterns.
    if item[0] in dictio_chaine and item[1] in dictio_chaine:
        if dictio_chaine[item[0]]&dictio_chaine[item[1]]:
            dictio_chaine[item[0]].update(dictio_chaine[item[1]])
            del dictio_chaine[item[1]]

I'm facing the following problem : the first part of my algorithm, which finds patterns in the list of tuples, is very poor since its performance is in O(n^2).

I think it would be better to create a tree. The pattern (1,2) (2,3) (3,1) becoming 2 is the child of 1, 3 is the child of 2 ...

Then if the pattern (2,5) (5,2)is encountered, it becomes a new branch 5 being the child of 2 which is already the son of 1. Eventually, I'll merge into a single set branches with the same leaves as the first node.

Would it be any better ? How could I implement such a tree, since the only tree I can easily implement is a binary tree which is not fit at all for what I'm trying to do.

Do you have any advice to help me improve my algorithm ?

Answer 1

If I understand the question, you are trying to find simple cycles in a directed graph.

In other words, you can interpret your tuples such as (4,5) as representing a directed edge between node 4 and node 5. You are then trying to find a path that starts at a node, follows a number of these edges, and returns to the starting node.

You can easily do this with the function simple_cycles in the Python library NetworkX. For example,

>>> import networkx as nx
>>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
>>> list(nx.simple_cycles(G))
[[2], [2, 1], [2, 0], [2, 0, 1], [0]]

The time complexity is O((n+e)(c+1)) for n nodes, e edges and c elementary circuits.