Finding non-overlapping loops in a circular tripartite graph

Question

I'm working on a music theory problem (see below the TL;DR for details), and came up with this graph problem.

My academic background hasn't much to do with graphs, so sorry if not using the correct names and feel free to reformulate the problem as needed.

Consider a circular tripartite graph (vertices from blue set connect back to vertices of the red set), but for simplicity, I repeated the vertices of the red set on the right, so it is easier to layout:

For each vertex of the red set, I'd like to find a loop, so that all those loops are non-overlapping (disjoint?).

If there are multiple solutions, I'd like to know all the solutions.

I haven't been able to match this problem to an existing problem about graphs.

---

E.g.: for the above instance of the problem, there are two solutions:

Is this related to some "well known" problem? If the problem has been solved, is there an algorithm?

I can think only about a backtracking algorithm, which perhaps is not the most efficient way to solve this problem.

---

TL;DR:

This problem arises from the following computational music theory problem:

Given some observed musical notes (e.g. the keys being pressed on a piano), what notes do they represent?

There is an ambiguity about how a musical pitch maps to multiple notes (see enharmonicity), e.g. C5, D5 and B♯4 are equivalent notes, but spelled differently; however which spelling should be used depends on context (which musical scale we are in, but we can't know this) and on some common constraints:

• there can't be both flat (♭) and sharp (♯) notes in a musical key, so in the example above we only consider flat and natural notes (the problem would be symmetrical for natural and sharp notes);
• there can't be a tone (e.g. D) that appears twice with different accidentals, e.g. in the example above, although both D♭5 and D5 are possible, both cannot be part of the same solution, as we cannot mention D twice.

So the example above is: we observed notes 60, 61 and 63, we have to assign each a distinct tone (C, D, E, F, G, A or B); additionally the note 60 could be a C5 or D5, note 61 could only be a D♭5, and note 63 could be either E♭5 or F5.

Answer 1

Your algorithm could be as follows. First equip every vertex with its in-degree. Then start at a red vertex, and for the next vertex in the loop, use the lowest in-degree green vertex which hasn't been used so far by a different red vertex. (And of course look only at the green vertices that the current red vertex goes to) Do the same for green with blue, with the added condition that the blue vertex should also go to the original red vertex. This is your first loop. Repeat for the rest of the red vertices.

This will give you a set of disjoint loops, if you want to find all such sets, its probably better to first find all loops for all the red vertices, and then you can construct another n-partite graph, where your vertex sets correspond to the starting vertex of a loop. Connect the loops with arrows if they are disjoint as loops, then use the same algorithm above to find all the loops in this graph, except don't check if a vertex has been used before, since here we don't care about disjointedness anymore. then every loop in this graph corresponds to a disjoint set of loops in the original tripartite graph. And so you can find all such sets.

The reason I think this approach is useful is because you can use the same algorithm twice, if carefully implemented, but I don't know (doubt) its the most efficient, and I also can't prove its correctness

Answer 2

Turns out that graph is very closely related to a constraint satisfaction graph.

E.g. by setting that up as a constraint satisfaction problem, I can find the same solutions.

E.g. in Prolog:

tone(c5, c).
tone(dbb5, d).
tone(db5, d).
tone(eb5, e).
tone(fbb5, f).

note(60, c5).
note(60, dbb5).
note(61, db5).
note(63, eb5).
note(63, fbb5).

solve(Vars) :-
    Vars = [60=N1, 61=N2, 63=N3],
    note(60, N1), tone(N1, T1),
    note(61, N2), tone(N2, T2),
    note(63, N3), tone(N3, T3),
    T1 \= T2, T1 \= T3, T2 \= T3.

?- solve(X).

X = [60=c5, 61=db5, 63=eb5] ;

X = [60=c5, 61=db5, 63=fbb5] ;

false.

 

In Python:

from constraint import *
p = Problem()
p.addVariable('60', ['C5','Dbb5'])
p.addVariable('61', ['Db5'])
p.addVariable('63', ['Eb5','Fbb5'])
# next is a bit of a hack: two notes cannot have same tone:
p.addConstraint(lambda a,b: a[0]!=b[0], ['60','61'])
p.addConstraint(lambda a,b: a[0]!=b[0], ['60','63'])
p.addConstraint(lambda a,b: a[0]!=b[0], ['61','63'])
for solution in p.getSolutions():
    print(solution)

 

{'61': 'Db5', '60': 'C5', '63': 'Fbb5'}

{'61': 'Db5', '60': 'C5', '63': 'Eb5'}