[QGHG-it-dev-list] Zadatak 11 - rekonstrukcija suseda na osnovu podataka o verteksima

[Marko Vojinovic]

Implementirati f-ju koja rekonstruise tabelu suseda datog k-simpleksa:

    bool KSimplex::reconstruct_neighbors_from_vertices( SimpComp *G );

    Input: pointer na simplicijalni kompleks.
    Output: true ako je uspesno izvrsena rekonstrukcija, false ako je doslo do neke greske.

F-ja ima zadatak da popuni tabelu neighbors datog simpleksa, pod pretpostavkom da su vec ispravno popunjeni svi verteksi, neighbors[0], kako za dati simpleks (zvacu ga "simp" u nastavku) tako i za sve ostale k-simplekse u kompleksu G. Algoritam ide otprilike ovako:

(1) Prvo proveriti da li simp pripada kompleksu G --- ako mu ne pripada, prijaviti error pomocu log_report() i vratiti false.

(1) Proci kroz sve k-simplekse u kompleksu G, za svako k>0 (k=0 ne treba jer su verteksi vec popunjeni po pretpostavci). Za svaki k-simpleks "current" uraditi sledece:

(2) Ako je nivo k od current manji od nivoa simp, current->k < simp->k, onda je on potencijalan pod-sused za simp. Ukoliko se svi njegovi verteksi (current->neighbors->elements[0]) sadrze na spisku verteksa za simp (simp->neighbors->elements[0]), povezati ga kao suseda sa simp-om, pomocu f-je add_neighbor(). Ako neki njegov verteks nije istovremeno i verteks od simp, onda nisu susedi.

(3) Ako je nivo k od current jednak nivou simp, current->k = simp->k, onda nisu susedi.

(4) Ako je nivo k od current veci od nivoa simp, current->k > simp->k, onda je on potencijalan nad-sused za simp. Ukoliko se svi verteksi od simp sadrze na spisku verteksa od current, povezati ih kao susede pomocu add_neighbor(). Ako neki verteks od simp nije istovremeno i verteks od current, onda nisu susedi.

F-ja moze da se testira na sledeci nacin. Najpre instanciramo neki kompleks nekom elementarnom seed f-jom (tj. nekom koja se ne oslanja na gornju f-ju). Zatim se verteksi tog kompleksa oboje sa UniqueID bojom, i ispise neighbor tablica nekog izabranog simpleksa u kompleksu pomocu print_compact(). Zatim se rucno obrisu svi k-susedi koji nisu verteksi (k>0) iz neighbor tablice za taj simpleks, pa se ti isti susedi rekonstruisu gornjom f-jom, i nakon toga se ponovo ispise neighbor tablica pomocu print_compact(). Ako se nova tablica poklapa sa starom, f-ja radi kako treba.


:-)
Marko


Dr. Marko Vojinovic
Group for Gravitation, Particles and Fields
Institute of Physics
University of Belgrade
======================
home page: www.markovojinovic.com
e-mail:    vmarko at ipb.ac.rs