Se știe că R oferă (mai ales ca mediu de lucru interactiv) numeroase metode de sinteză și vizualizare grafică a datelor statistice, iar unele pachete R excelează în a oferi vizualizări grafice sofisticate pentru structuri de date mai complicate, de exemplu pentru cele din teoria grafurilor (și rețelelor); iar uneori… așa sunt modelate lucrurile în ansamblul lor, de parcă scopul ar fi acela de a le vizualiza.

Bineînțeles că un "algoritm de colorare" nu vizează colorarea fizică (prin vectorul returnat de funcția colors(), cu 657 de nume uzuale de culori), a nodurilor grafului…
Să vedem prototipul funcției greedy_vertex_coloring() din pachetul igraph:

> str(greedy_vertex_coloring)
function (graph, heuristic = c("colored_neighbors", "dsatur"))

Dacă la apelare se specifică numai graful, atunci se folosește (implicit) algoritmul indicat prin numele "colored_neighbors", despre care documentația spune că este bazat "on a simple greedy algorithm": la fiecare pas se alege vârful cu cel mai mare număr de adiacenți deja colorați. Dar (cum arată experimentul următor) nu prea este vorba de algoritmul clasic de colorare (cel într-adevăr simplu, sau elementar), în care colorarea decurge în ordinea dată explicit a vârfurilor.

Considerăm un graf bipartit, deci un graf în care muchiile unesc vârfurile unei submulțimi (prima parte) cu vârfuri din complementara acesteia (a doua parte); vârfurile dintr-o aceeași parte sunt neadiacente între ele și pot fi colorate la fel, deci un graf bipartit este 2-colorabil. Dar prin algoritmul de colorare "clasic" (realmente, cel mai simplu) pot rezulta mai mult de două culori, depinzând de ordinea fixată din exterior pentru abordarea vârfurilor grafului respectiv.

De exemplu, graful cu muchiile 1--4 1--6 2--3 2--5 3--6 4--5 este un graf bipartit (cu părțile {1,3,5} și {2,4,6}). Să-i aplicăm pas cu pas, algoritmul de colorare "clasic", în ordinea naturală a vârfurilor: colorăm vârful 1, rezultând o primă clasă a colorării C1 = {1}; trecem la vârful 2 și observăm că acesta nu este adiacent cu cel înscris în C1 (lipsește o muchie "1--2"), deci îl putem adăuga în C1 (C1 = {1, 2}); trecând la vârful 3, observăm că acesta este adiacent cu vârful 2, existent în C1 — prin urmare trebuie pus într-o nouă clasă de colorare C2 = {3}; vârful 4 nu poate fi adăugat în C1 (fiindcă există o muchie 1--4), dar poate fi adăugat în C2 fiindcă nu este adiacent cu 3, deci C2 = {3, 4}; pentru vârful 5, avem și muchia 2--5 și muchia 4--5, deci el nu merge nici în C1 și nici în C2 — prin urmare trebuie pus într-o nouă clasă C3 = {5} (în care la pasul următor avem de adăugat și vârful 6). Deci în loc de două culori, cum știm noi (nu și algoritmul) că trebuie să fie, graful fiind bipartit — ne-au rezultat trei culori.

Dar dacă treceam de la un vârf la altul în ordinea (1,3,5, 2,4,6), atunci vârfurile 1, 3 și 5 primeau o aceeași culoare (fiind neadiacente unul cu altul) și abia la pasul 4, ajungând la vârful 2, trebuie să înființăm o nouă clasă de colorare (în care la pașii următori vin și nodurile 4 și 6); adică așa, prin același algoritm, rezultă două culori.

Algoritmului "clasic" operat mai sus poate avea o formulare foarte simplă:

greedy_coloring <- function(G, perm) {
    colors <- rep(0L, gorder(G))  # inițializează atâtea culori câte vârfuri
    for(v in perm) {  # colorează în ordinea dată de 'perm'
        col <- 1  # caută de la 1, clasa de colorare a nodului curent
        Ncol <- colors[neighbors(G, v)]  # culorile adiacenților
        while(col %in% Ncol[Ncol > 0]) 
            col <- col + 1    
        colors[v] <- col  # culoarea cea mai mică diferită de a adiacenților
    }
    colors
}

Putem construi graful de mai sus printr-o metodă obișnuită și putem vedea că prin greedy_coloring() obținem într-adevăr cele două colorări găsite manual mai sus:

> G <- make_graph(edges = c(1,4, 1,6, 2,3, 2,5, 3,6, 4,5), directed = FALSE)
> greedy_coloring(G, perm = 1:6)
    [1] 1 1 2 2 3 3
> greedy_coloring(G, perm = c(1,3,5, 2,4,6)) %>% setNames(V(G))
    1 2 3 4 5 6 
    1 2 1 2 1 2 

Dar pentru grafuri bipartite, igraph oferă constructorul make_bipartite_graph(); în parametrul types se cere un criteriu care să disocieze vârfurile după partea fiecăruia (în cazul nostru, cele pare și respectiv, impare), iar în edges se cer datele esențiale pentru construcția unui graf — în speță (ca și mai sus), capetele fiecărei muchii:

library(tidyverse)
library(igraph)
B1 <- make_bipartite_graph(
          types = sapply(1:6, function(i) i %% 2),  # părți: {1,3,5} și {2,4,6}
          edges = c(1,4, 1,6, 2,3, 2,5, 3,6, 4,5)
      )
print(B1)
#    IGRAPH 35eca6c U--B 6 6 --   # graf neorientat, bipartit, cu 6 vârfuri și 6 muchii
#    + attr: type (v/l)  # s-a înființat atributul 'type', cu valori logice
#    + edges from 35eca6c:
#    [1] 1--4 1--6 2--3 2--5 3--6 4--5

Pe baza argumentului types, grafului rezultat B1 i s-a montat un atribut numit "type", cu valori FALSE/TRUE, indicând pentru fiecare vârf partea care îl conține. Subliniem că acest parametru nu a fost folosit în construcția internă ca structură de date a grafului (fără atributul type, B1 ar coincide cu graful G construit mai sus), ci doar marchează (în scopuri ulterioare construcției) calitatea de graf bipartit; datorită acestui atribut, graful poate fi plotat separând nodurile pe două niveluri, corespunzător celor două părți (folosind funcția layout_as_bipartite()):

plot(B1, layout = layout_as_bipartite)

și tot datorită atributului type, vârfurile vor putea fi colorate fizic mai ușor, specificând sub plot(), vertex.color = V(B1)$type (și atunci, în mod tacit, drept culori fizice se vor folosi cele indicate pe primele două locuri din vectorul dat de colors()). Este clar că parametrul "types" a fost prevăzut în constructorul de grafuri bipartite cu scopul de a facilita vizualizarea grafică a acestora.

Am descris mai sus cum decurge colorarea prin algoritmul "clasic"; să vedem acum cam cum colorează greedy_vertex_coloring():

> print(greedy_vertex_coloring(B1))  # [1] 1 2 1 2 1 2

Conform documentației, la fiecare pas se alege vârful "with the largest number of already colored neighbors". După ce s-a colorat vârful 1, se constată că există două vârfuri care au "already colored neighbors", anume 4 și 6, adiacente ambele cu vârful deja colorat 1 — deci la pasul doi se alege vârful 4 (și nu 2, care în momentul respectiv are zero adiacenți deja colorați). Vârful ales 4 primește culoarea 2; dintre vârfurile rămase, 5 și 6 au adiacenți deja colorați, anume câte unul — se alege cel mai mic, 5 și acesta poate fi colorat cu 1; ș.a.m.d.

Deja putem înțelege că nu prea are importanță, "ordinea inițială" a vârfurilor; de fapt, într-o structură IGRAPH, vârfurile sunt fixate totdeauna în ordinea naturală, iar dacă este cazul, o altă "ordine inițială" ar putea fi dedusă văzând vectorul muchiilor. Pentru a schimba ordinea accesării vârfurilor, trebuie să creem un nou graf, în care vectorul muchiilor să reflecte noua ordine a vârfurilor (e ca și cum am permuta liniile și coloanele matricei de adiacență și am considera apoi graful definit "de la stânga spre dreapta și de sus în jos", de noua matrice); funcția permute() scurtează crearea acestui nou graf, modificând graful inițial (dar păstrând atributele acestuia):

B2 <- permute(B1, match(V(B1), c(1, 3, 5, 2, 4, 6)))
print(E(B2))  # [1] 1--5 1--6 2--4 3--4 2--6 3--5
> as.matrix(B1, "adjacency")    > as.matrix(B2, "adjacency")
[1,] . . . 1 . 1                  [1,] . . . . 1 1
[2,] . . 1 . 1 .                  [2,] . . . 1 . 1
[3,] . 1 . . . 1                  [3,] . . . 1 1 .
[4,] 1 . . . 1 .                  [4,] . 1 1 . . .
[5,] . 1 . 1 . .                  [5,] 1 . 1 . . .
[6,] 1 . 1 . . .                  [6,] 1 1 . . . .

(am afișat și matricele de adiacență, evidențiind ce am spus mai sus, că "e ca și cum am permuta liniile și coloanele...")

match() a furnizat noua ordine de accesare:

> match(1:6, c(1, 3, 5, 2, 4, 6)) %>% setNames(1:6)
    1 2 3 4 5 6   # ordinea naturală a vârfurilor
    1 4 2 5 3 6   # "noua ordine": 2 devine 4, 3 devine 2, 4 devine 5, 5 devine 3

Vârful 2 este indicat lui match() pe a 4-a poziție, deci al patrulea nod în noua ordine este 2; vărful 3 a fost indicat pe poziția doi, deci al doilea nod în noua ordine este 3; ș.a.m.d. Muchia 1--4 din graful B1 devine 1--5 în graful B2, ș.a.m.d. (cele două grafuri sunt izomorfe, prin funcția de asociere definită de match(), iar a schimba ordinea vârfurilor revine la a "redefini" vectorul muchiilor). Pentru B2, corespunzător noii ordini, va rezulta ca mai sus, colorarea 1 1 1 2 2 2.
Desigur… dacă aveam inspirația de a fi definit niște etichete (prin atributul name) pe vârfurile lui B1, atunci noua ordine a vârfurilor se vedea imediat:

V(B1)$name <- LETTERS[1:6]  # vârfurile 1:6 sunt etichetate cu "A:F"
B2 <- permute(B1, match(V(B1), c(1, 3, 5, 2, 4, 6)))
print(V(B1))  # [1] A B C D E F
print(V(B2))  # [1] A C E B D F  (noua ordine a vârfurilor)
> greedy_vertex_coloring(B2) 
    A C E B D F 
    1 1 1 2 2 2 

Prin algoritmul clasic, parcurgând vârfurile în ordinea naturală (probabil și în vreo altă ordine) obținem trei culori; greedy_vertex_coloring() aplică un algoritm mai bun (putem poate spune cam același algoritm "simplu", dar citit și implementat mai bine) — fiindcă oricum am permuta vârfurile, ne rezultă mereu două culori (cum este corect). Pentru graful B1 (cu numai 6 vârfuri) putem verifica direct aceasta, considerând toate cele 720 de permutări posibile (avându-le într-un anumit fișier de permutări):

Perm <- readRDS("lstPerm47.RDS")[[3]]  # permutările de 6 elemente (pe coloane)
Lc <- list()  # va reține colorările, corespunzător fiecărei permutări
for(i in 1:720) {
    P <- Perm[, i]
    p <- paste0(P, collapse = "")
    H <- permute(B1, match(1:6, P))
    Lc[[p]] <- greedy_vertex_coloring(H, heuristic="colored_neighbors")
}
print(Lc[["162354"]])  # (exemplu)
#    A F B C E D 
#    1 2 2 1 1 2 
nc <- sapply(Lc, function(x) max(x))
print(all(nc == 2))  # [1] TRUE  (toate cele 720 colorări au câte două culori)

Obs. Poate ar fi de bănuit că de fapt, greedy_vertex_coloring() ține seama de atributul type specific grafurilor bipartite, știind deci de la început că trebuie să fie două culori; dar investigând chiar codul-sursă coloring.c, vedem că nu este așa; găsim însă o funcție C (neimportată în R, v. R igraph), anume igraph_is_bipartite_coloring(), care verifică dacă graful este bipartit și returnează 2-colorarea imediată a celor două părți indicate ei în argumentul "types".