Find cycles with specific weights in complete graph (this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=[4,7,6]$).
Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$
Here is a poorly-drawn example:
.
Welcome to CS.SE.
I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.
A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?
This leads to the following python 2.7 code, that does not make the assumption that the graph is complete. Its core is the find function, everything else is for playing and testing.
import random
random.seed()

min_weight,max_weight=1,20
c_length=30

# build the graph (complete in this case)
V = ['A','B','C','D','E']
N = {u:[v for v in V if v!=u] for u in V}
weight = {}
for (u,v) in [(u,v) for u in V for v in N[u] if u&lt;v]:
        weight[(u,v)] = weight[(v,u)] = random.randint(min_weight,max_weight)
for (u,v) in sorted(weight):
        print u+'--'+str(weight[(u,v)])+&quot;--&quot;+v

# build a correct sequence of weights
c = []
u = random.choice(V)
while len(c)&lt;c_length:
        v = random.choice(N[u])
        c.append(weight[(u,v)])
        u = v
print c

# search all paths corresponding to the weight sequence in the graph
def find(c,S):
        if len(c)==0:
                return(S)
        return set([u+r for u in S for r in find(c[1:],[v for v in N[u] if weight[(u,v)]==c[0]])])

result = find(c,V)
print result

# check results
def check(x):
        if len(x) != len(c)+1:
                return(False)
        for i in xrange(len(x)-1):
                if weight[(x[i],x[i+1])] != c[i]:
                        return(False)
        return(True)
for x in result:
        assert(check(x))

Is it correct? It is far from optimal, of course.