De 9 ori repetasem execuția programului constituit în [1], găsind mereu (dar după sute sau chiar mii de încadrări cu 7, 8 sau 9 profesori) o aceeași încadrare de 6 profesori — încât am și formulat concluzia că "repetarea execuției programului respectiv este inutilă". Totuși această "concluzie" nostimă este surprinzătoare (că înainte de fiecare colorare "greedy" din rularea curentă, vârfurile sunt reordonate aleatoriu, deci parcă și în finalul ei ar cam fi trebuit să obținem colorări diferite de la o execuție la alta). Peste ceva timp (cu două evenimente nebanale: Zverev a ajuns pe locul 1 și s-a mai întâmplat un cutremur, scurt dar de aproape 5 grade), am repetat iarăși, de vreo două ori, ajungând să constat (nostim) că m-am păcălit (probabil, ca și în privința evenimentelor "nebanale"): obținem și încadrări cu 6 profesori diferite de cele găsite anterior, anume:

    $Mt1  "8A 11D 12D 12A 10C"      # 24 ore  (la fel cu MT6)
    $Mt2  "11C 7A 10G 11B 9G 11F"   # 20  (la fel cu MT5)
    $Mt3  "9B 11A 10H 11E 10A"      # 19  ($MT4 "10A 10F 11A 11E 9B")
    $Mt4  "10E 12F 12C 6B 12B 5B"   # 24  (la fel cu MT1)
    $Mt5  "10F 9A 10B 9D 12E"       # 19  ($MT3 "10B 10H 12E 9A 9D")
    $Mt6  "8B 6A 5A 9F 9E 10D 9C"   # 24  (la fel cu MT2)

încadrare care coincide cu aceea din fișierele PDF inițiale (pentru care indexasem profesorii prin "MT", v. [1]) — dacă doar schimbăm între Mt3 și Mt5 clasele 10H și 10F; acestea au câte două ore și nu sunt adiacente în graful G cu celelalte clase ale celor doi profesori (fiind adiacente între ele, nu pot figura la un același profesor, dar fiecare poate fi pusă și unuia și celuilalt, încât le putem interschimba între cei doi, rezultând chiar încadrarea existentă pentru "Matematică" în "Orar general profesori").

Între timp (pe lângă meciurile de la turneele de tenis din China și buletinele Meteo), am descoperit pachetul Python GCol, specializat pe colorarea grafurilor; de fapt, consultasem deja, mai demult, cartea lui R. Lewis "A Guide to Graph Colouring" (ediția din 2016, găsită gratuit prin 2023) referită în [2] și mai folosisem pachetul Python NetworkX. Reluăm deci chestiunea din [1], folosind acum aceste pachete Python.

Pe scurt, chestiunea era următoarea: avem un "Orarul general clase", adus deja la forma normală a datelor, cls|obj|zl|ora (specificând pe câte o linie de date, clasele, disciplinele, zilele și orele când se desfășoară lecțiile în școala respectivă); lipsesc profesorii care fac lecțiile (adică valorile variabilei prof) și vrem să vedem care ar fi numărul minim de profesori pentru a acoperi lecțiile la o anumită disciplină conform orarului "pe clase" existent pentru acea disciplină.

Am selectat (v. [1]) lecțiile pe disciplina "Mate" (în total, 130 ore) și folosind pachetul R igraph, am constituit graful G având ca vârfuri valorile din câmpul cls, două vârfuri fiind adiacente în cazul în care clasele respective au vreo lecție de "Mate" într-o aceeași zi și oră (deci ar trebui să aibă profesori diferiți); G are 34 noduri și 202 muchii (este un graf mare pentru alde noi, dar încă mic pentru posibilitățile actuale de calcul).
Prin igraph::as_adj_list(G) obținem listele de adiacență care definesc graful G:

# fișierul "list_adj.txt" (pe rând, clasele adiacente celeia de pe primul loc)
5A 6B  7A  8A  9D  12A 12C 12D 12F 11A 11B 11C 11D 11E 11F 10A 10B
5B 7A  8A  9A  9B  9D  12D 12E 11A 11C 10A 10B 10C 10D 10G
6A 6B  7A  8A  9B  9D  9G  12A 12C 12F 11D 11E 10B 10C
6B 5A  6A  7A  9C  9D  9F  9G  12D 11A 11D 11E 10A 10B
7A 5A  5B  6A  6B  8A  9A  9D  12C 12D 12E 10A 10C 10D
8A 5A  5B  6A  7A  8B  9A  9B  12B 12C 11C 11E 10B 10F
8B 8A  9A  12B 12C 12D 12E 11A 11B 11C 11E 11F
9A 5B  7A  8A  8B  9B  9F  9G  12B 12C 12D 11B 11C 11D 11E 10A
9B 5B  6A  8A  9A  9D  9F  9G  12A 12B 12C 12F 11C 11D 10B 10C
9C 6B  12A 12B 11A 11B 11C 11D 10B 10E 10F 10H
9D 5A  5B  6A  6B  7A  9B  12C 12D 11D 11E 11F 10A 10C 10D 10G
9E 12A 12E 11B 11D 10A 10E
9F 6B  9A  9B  9G  12B 11D
9G 6A  6B  9A  9B  9F  12B 11D 11E
12A 5A  6A  9B  9C  9E  12B 12E 12F 11A 11B 10A 10B 10E 10H
12B 8A  8B  9A  9B  9C  9F  9G  12A 12E 11A 11B 11C 11D 11E 11F 10F
12C 5A  6A  7A  8A  8B  9A  9B  9D  12D 11B 11C 11D 11E 11F 10B 10C
12D 5A  5B  6B  7A  8B  9A  9D  12C 11B 10A 10D 10G
12E 5B  7A  8B  9E  12A 12B 11A 11B 11E 11F 10A 10C 10D 10E 10G
12F 5A  6A  9B  12A 11A 11B 10B
11A 5A  5B  6B  8B  9C  12A 12B 12E 12F 11B 11D 11F 10B 10C 10G
11B 5A  8B  9A  9C  9E  12A 12B 12C 12D 12E 12F 11A 10A 10E 10H
11C 5A  5B  8A  8B  9A  9B  9C  12B 12C 11E 10B 10F 10H
11D 5A  6A  6B  9A  9B  9C  9D  9E  9F  9G  12B 12C 11A 11E 11F 10B 10E
11E 5A  6A  6B  8A  8B  9A  9D  9G  12B 12C 12E 11C 11D 11F
11F 5A  8B  9D  12B 12C 12E 11A 11D 11E
10A 5A  5B  6B  7A  9A  9D  9E  12A 12D 12E 11B 10C 10D 10E
10B 5A  5B  6A  6B  8A  9B  9C  12A 12C 12F 11A 11C 11D
10C 5B  6A  7A  9B  9D  12C 12E 11A 10A 10D 10G
10D 5B  7A  9D  12D 12E 10A 10C 10G
10E 9C  9E  12A 12E 11B 11D 10A 10H
10F 8A  9C  12B 11C 10H
10G 5B  9D  12D 12E 11A 10C 10D
10H 9C  12A 11B 11C 10E 10F

(se poate verifica acum că 10F și 10H sunt adiacente și nu sunt adiacente vreuneia dintre clasele lui Mt3 sau Mt5 pomeniți mai sus)

Să încercăm câte ceva folosind numai networkx (și deocamdată doar gcol.partition(), pentru a afișa partiția rezultată prin colorarea vârfurilor):

import networkx as nx
import gcol
with open("/home/vb/26oct/list_adj.txt", "rb") as fh:
    H = nx.read_adjlist(fh)
print(H)  # Graph with 34 nodes and 202 edges
q = nx.coloring.greedy_color(H)
print(gcol.partition(q))
# [['10F', '11B', '11D', '5B'], ['10D', '10E', '12B', '5A', '6A'], ['10A', '10H', '11A', '12C', '9G'], ['10B', '12E', '9A', '9D'], ['10G', '11E', '7A', '9B', '9C', '9E'], ['10C', '11F', '12A', '6B', '8A'], ['11C', '12D', '12F', '9F'], ['8B']]

Repetând de oricâte ori, obținem mereu colorarea indicată mai sus, reprezentând o încadrare pe clase, anume cu 8 profesori. Putem folosi în nx.coloring.greedy_color() parametrul "strategy" cu diverse valori; cu 'random_sequential', obținem la fiecare execuție câte o altă colorare, dar în general cu 8, 9 sau 10 culori și probabil că trebuie să repetăm (cum am modelat în [1]) de sute sau mii de ori, ca să ajungem poate și la o colorare optimă (cu 6 profesori).

Să încercăm acum unele dintre funcțiile de colorare ale pachetului specializat gcol.
Mai întâi, gcol.node_coloring(H) dă mereu o aceeași colorare, anume cu 8 profesori. Însă adăugând parametrii posibili:

q = gcol.node_coloring(H, strategy = "dsatur", opt_alg = 2, it_limit = 100)
print(gcol.partition(q))

și repetând de numai două sau trei ori execuția programului rezultat:

(GCOL) vb@Home:~/GCOL$ python ~/26oct/gc1.py 
[['10C', '10F', '11D', '12A', '8B'], ['10D', '10E', '5A', '6A', '9A'], ['10H', '12B', '12C', '12F', '5B', '6B'], ['11C', '12E', '9D'], ['10A', '10G', '11E', '9B', '9C'], ['10B', '11B', '11F', '7A', '9F'], ['11A', '12D', '8A', '9E', '9G']]  # 7 profesori
(GCOL) vb@Home:~/GCOL$ python ~/26oct/gc1.py 
[['10C', '11F', '12A', '12D', '8A', '9G'], ['10B', '10H', '12E', '9A', '9D'], ['10E', '12B', '12C', '12F', '5B', '6B'], ['10D', '5A', '6A', '8B', '9C', '9E', '9F'], ['10A', '10F', '11A', '11E', '9B'], ['10G', '11B', '11C', '11D', '7A']]  # 6 profesori
(GCOL) vb@Home:~/GCOL$

obținem și o colorare cu 6 profesori (diferită sensibil, de cea redată la început pentru "Mt"), iar mărind întâi numărul de iterații it_limit=1000, rezultă imediat o încadrare cu 6 profesori, care aproape coincide cu aceea de mai sus pentru "Mt". Pe de altă parte, gcol.chromatic_number(H) confirmă imediat că 6 este într-adevăr, numărul minim necesar de profesori pentru a acoperi față de orarul indicat, lecțiile respective.

Precizăm că prefixul "(GCOL)" din cele două linii de comandă redate mai sus indică "mediul virtual" în care am instalat pachetul gcol și din care, după "activare", am lansat programul "gc1.py" constituit în folder-ul indicat în comandă.

Încercăm acum să folosim metoda equitable_node_k_coloring(), care ar asigura o colorare cu număr dat de culori (vrem 6 culori) astfel încât pentru fiecare culoare, suma ponderilor asociate prin intermediul parametrului 'weight', vârfurilor de acea culoare, să fie cam aceeași (cu alte cuvinte, căutăm o încadrare pe clase în care profesorii să aibă, dacă se poate, cam același număr total de ore).

În [1] constituisem un "vector cu nume" CNT, care ne indica pentru fiecare clasă, numărul de ore de "Mate"; preluăm de-acolo vectorii names(CNT) și as.integer(CNT) și constituim din aceștia un dicționar Python (cum așteaptă parametrul 'weight'):

Kls = ["10F", "10G", "10H", "11F", "12F", "9E", "9F", "9G", "10A", "10B", "10C",
"10D", "10E", "11E", "5A", "5B", "6A", "6B", "7A", "8B", "9A", "9B", "9C", 
"9D", "11A", "11B", "11C", "11D", "12A", "12B", "12C", "12D", "12E", "8A"]
Ore = [2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
5, 5, 5, 5, 5, 5, 5, 5, 5, 5]  # clasele au 2, 4, sau 5 ore
Wgh = dict(zip(Kls, Ore))  # dicționar {clasă: număr de ore}
# {'5A': 4, '6B': 4, '7A': 4, '8A': 5, '9D': 4, '12A': 5, '12C': 5, '12D': 5, '12F': 2, 
'11A': 5, '11B': 5, '11C': 5, '11D': 5, '11E': 4, '11F': 2, '10A': 4, '10B': 4, '5B': 4, 
'9A': 4, '9B': 4, '12E': 5, '10C': 4, '10D': 4, '10G': 2, '6A': 4, '9G': 2, '9C': 4, 
'9F': 2, '8B': 4, '12B': 5, '10F': 2, '10E': 4, '10H': 2, '9E': 2}

Însumând valorile asociate de Wgh claselor din încadrarea unui profesor dat, vom obține totalul de ore ale acestuia; probabil că un asemenea calcul va trebui repetat intern, de exemplu până la echilibrarea totalurilor de ore. Pentru a evita apelarea repetată la dicționarul Wgh, aflat în exteriorul grafului H, putem internaliza în prealabil, valorile respective: cheile Kls ale dicționarului sunt chiar vârfurile grafului și n-avem decât să adăugăm vârfurilor valorile Ore ale dicționarului,

nx.set_node_attributes(H, values = Wgh, name = "Ore")

Prin intermediul atributului numit "Ore", al grafului H, funcțiile de colorare vor putea vedea direct (fără a apela la dicționarul extern Wgh) numărul de ore al fiecărei clase. La fel, putem seta pe vârfuri și alte atribute, iar parametrul 'weight' servește pentru a specifica atributul de folosit în cadrul funcției respective:

q = gcol.equitable_node_k_coloring(H, 6, weight = "Ore", 
        opt_alg = 4, it_limit = 1000, verbose = 1)
# O funcție care afișează colorarea și totalurile pe un atribut numeric al vârfurilor
def view_partition(G, q, attr):
    Wgh = nx.get_node_attributes(G, attr)
    Pt = {tuple(L): sum([Wgh[C] for C in L]) 
             for L in gcol.partition(q)}
    for k,v in Pt.items():
        print(k,v)
view_partition(H, q, "Ore")  # afișăm încadrările și totalurile de ore

Pentru afișarea rezultatului, în funcția view.partition() am înființat dicționarul Pt, având drept chei încadrările — transformând însă tipul list al acestora, în tuple fiindcă obiectele de tip "list", fiind editabile (spre deosebire de "tuple"), nu pot fi chei în vreun dicționar Python — și drept valori, totalurile de ore.
Până se se afișeze rezultatul, datorită folosirii parametrului 'verbose', sunt furnizate pe ecran unele informații de lucru intern:

(GCOL) vb@Home:~/GCOL$ python ~/26oct/gc1.py
Running local search algorithm:
    Found solution with 8 colors. Total local search iterations = 0 / 1000
    Found solution with 7 colors. Total local search iterations = 16 / 1000
    Found solution with 6 colors. Total local search iterations = 227 / 1000
Ending local search at iteration 227 - optimal solution achieved.
Running equitable local search algorithm using 6 colors:
    Found solution with cost (std. dev.) 2.3570226039551585
    Found solution with cost (std. dev.) 2.1343747458109497
Ending equitable local search algorithm - local optimum achieved.
# rezultatul execuției
('10G', '11B', '11C', '11D', '7A') 21
('10B', '10H', '12E', '9A', '9D') 19
('10E', '12B', '12C', '12F', '5B', '6B') 24
('10D', '5A', '6A', '8B', '9C', '9E', '9F') 24
('10A', '10F', '11A', '11E', '9B') 19
('10C', '11F', '12A', '12D', '8A', '9G') 23

Prin algoritmul ales prin parametrul 'opt_alg', s-a găsit întâi o colorare cu 8 culori, apoi una cu 7 și după încă un număr de iterații, o colorare optimă (cu 6 culori); pentru colorarea obținută s-a calculat costul acesteia, adică deviația ei față de o colorare "echitabilă" și apoi colorarea respectivă a fost perturbată cumva (interschimbând clase între încadrările profesorilor, când este posibil) pentru a vedea dacă se poate reduce costul respectiv. Colorarea afișată are "costul" cel mai mic, dar nu este garantat teoretic că este într-adevăr, cea mai bună; executând însă programul de mai multe ori (cu diverse alegeri pentru 'opt_alg'), am obținut același rezultat.

Dacă ar fi fost 132 de lecții și dacă structura existentă a claselor permite (câte sunt cu 2 ore, câte cu 4 respectiv 5 ore), atunci "echitabil" ar fi însemnat desigur ca acei 6 profesori să primească fiecare câte 22 de ore; în realitate sunt 130 de lecții, încât cei 6 profesori nu pot primi câte un același număr de ore — ce înseamnă "echitabil" în acest caz? Statistica ne oferă acest răspuns: acea încadrare cu profesori este echitabilă, pentru care abaterea de la media orară 130/6 a totalului de ore/profesor este minimă.

Să calculăm și noi (într-o consolă R) "abaterea medie pătratică", pentru cele două încadrări cu câte 6 profesori pe care le-am evidențiat până acum:

 Mat1 <- c(24, 24, 24, 19, 19, 20)  # totalurile încadrării notate în [1] cu "MT"
 Mat2 <- c(24, 24, 19, 19, 23, 21)  # totalurile încadrării "Mt"
 echi <- 130 / 6
 sqrt(sum((Mat1 - echi)^2) / 6)  #[1] 2.357023
 sqrt(sum((Mat2 - echi)^2) / 6)  #[1] 2.134375

Au rezultat tocmai valorile anunțate mai sus de equitable_node_k_coloring().

Pentru "perturbarea" încadrării găsite (ajungând la o altă încadrare, poate de cost mai mic) se folosesc lanțuri Kempe, generalizate astfel: se consideră un subset ordonat J, cu cel puțin două, dintre culorile setate pe vârfurile grafului H; se consideră subgraful lui H constituit de vârfurile a căror culoare figurează în J și se derivează din acest subgraf, digraful în care arcele unesc vârfuri care au culori consecutive în J (în ordine circulară: culoarea următoare ultimeia din J este prima din J). Interschimbând culorile de-a lungul unui lanț al acestui digraf (lanț care este un "lanț Kempe generalizat" al grafului H), rezultă o nouă colorare a grafului H (dacă J conține numai două culori, atunci avem noțiunea clasică de "lanț Kempe").

De exemplu, să vedem dacă (și cum) putem schimba profesorul căruia colorarea curentă i-a atribuit clasa "11D", cu unul ales la întâmplare dintre ceilalți profesori. Considerăm o colorare cu 6 culori a grafului H, alegem un vârf (anume, "11D") și vrem să vedem dacă schimbându-i culoarea curentă cu câte una dintre celelalte culori, obținem colorări distincte de cea curentă:

q = gcol.node_coloring(H, strategy = "dsatur", opt_alg = 2, it_limit = 1000)
view_partition(H, q, "Ore")
v = "11D"
c1 = q[v]  # culoarea atribuită clasei 
for c2 in [c for c in range(0, 6) if c != c1]:  # culorile sunt 0,1,...,5
    print(v, c1, c2)
    Q = gcol.kempe_chain(H, q, v, c1, c2)
    print(Q)  # lanțul Kempe prin 'v', al interschimbării de culori

Redăm o mostră de execuție a secvenței de mai sus:

(GCOL) vb@Home:~/GCOL$ python ~/26oct/gc1.py 
    ('5A', '5B', '6A', '8B', '9C', '9E', '9F')  24
    ('10G', '11B', '11C', '11D', '7A')  21
    ('10A', '10F', '11A', '11E', '9B')  19
    ('10C', '11F', '12A', '12D', '8A', '9G')  23
    ('10D', '10E', '12B', '12C', '12F', '6B')  24
    ('10B', '10H', '12E', '9A', '9D')  19
11D 1 0
{'5A', '6A', '9F', '7A', '8B', '5B', '10G', '9C', '9E', '11C', '11B', '11D'}
11D 1 2
{'11E', '10G', '10F', '7A', '10A', '11A', '11C', '11B', '9B', '11D'}
11D 1 3  # lanțul Kempe pentru a schimba '11D' de la al 2-lea la al 4-lea
{'9G', '11F', '11D'}
11D 1 4
{'7A', '10D', '10G', '12B', '10E', '12F', '11C', '11B', '12C', '6B', '11D'}
11D 1 5
{'7A', '10G', '10H', '9D', '10B', '11C', '9A', '11B', '12E', '11D'}

Într-un singur caz, cel boldat, se obține o nouă încadrare; în celelalte, fiindcă lanțul Kempe afișat coincide cu reuniunea claselor din două încadrări, doar se schimbă toate clasele profesorului al doilea cu toate ale altuia, rezultând doar o permutare a încadrării inițiale (și nu o "nouă" încadrare).
Din lanțul Kempe afișat în cazul "11D 1 3", deducem că putem schimba clasa 11D cu clasele 9G și 11F, între al doilea și al patrulea profesor și rezultă astfel o nouă încadrare (în care, cum am și detaliat în [1], al doilea ar avea 20 iar al 4-lea 24 de ore).
Recunoaștem ușor că încadrările respective sunt chiar cele pe care le notasem mai la început prin Mt și MT; deci acestea sunt "Kempe-echivalente", adică se pot deduce una din cealaltă folosind Kempe_chain(), iar această cale de obținere este cu siguranță mai rapidă, decât (cum am făcut anterior) executând repetat node_coloring() până ce obținem pe fiecare în parte.

Este de văzut dacă există încadrări care nu sunt "Kempe-echivalente"; în [2] este pomenit acest criteriu: dacă numărul de "degenerare" al grafului este mai mic decât n, atunci toate colorările cu n culori ale vârfurilor sunt Kempe-echivalente.
Numărul de degenerare al grafului G se definește ca fiind cel mai mare dintre gradele minime ale subgrafurilor lui G și poate fi determinat printr-un algoritm ușor de implementat: dgy = gradul minim al grafului curent; elimină un nod cu gradul dgy, împreună cu muchiile adiacente lui; dacă gradul minim al grafului rezultat este mai mare decât dgy, atunci actualizează dgy pe acest grad; repetă pașii indicați până ce graful curent devine vid. Valoarea finală din dgy este "numărul de degenerare" ("degeneracy") al grafului dat.
Dar și în NetworkX și în igraph, găsim funcțiile necesare pentru a afla direct numărul de degenerare; pentru graful H, găsim valoarea 9 — deci nu-i sigur că toate colorările posibile cu numai 6 culori sunt Kempe-echivalente; în schimb, după rezultatul pomenit mai sus, dacă n > 9, atunci toate încadrările cu n profesori sunt Kempe-echivalente.

Obs. În funcția move_cls() din pachetul refitgaps ne-am bazat deasemenea, pe lanțuri Kempe (cu două culori), pentru a reduce numărul ferestrelor dintr-un orar școlar dat: secvența de mutări succesive care sunt necesare pentru a aduce o clasă din coloana h1, în coloana h2 (păstrând unicitatea pe coloană pentru clase) este dată de unul dintre circuitele Kempe existente în graful orientat ale cărui arce unesc o valoare din coloana h1 (clasă sau loc liber '-') cu aceea de pe aceeași linie, din coloana h2.