EÖTVÖS LORÁND TUDOMÁNYEGYETEM INFORMATIKAI KAR ALGORITMUSOK ÉS ALKALMAZÁSAIK TANSZÉK
Részstruktúrák keresése molekulagráfokban
Témavezetők:
Szerző:
Dr. Fekete István
Kendi János
egyetemi docens
nappali tagozat
ELTE Informatikai Kar
Programtervező informatikus (MSc)
Algoritmusok és Alkalmazásaik Tanszék
Kovács Péter programtervező matematikus ChemAxon Kft.
Budapest 2011
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg (a támogatás száma TÁMOP 4.2.1./B-09/1/KMR-2010-0003).
Tartalomjegyzék
Bevezetés
2
1. Körhalmazok molekulagráfokban
4
1.1. Alapfogalmak
4
1.2. Smallest Set of Smallest Rings (SSSR)
8
2. Körkereső algoritmusok
10
2.1. Egy gráf összes körének keresése 2.1.1. Gráf összeomlasztás
10 10
2.2. SSSR algoritmusok 2.2.1. Zamora SSSR algoritmusa 2.2.2. Doucet SSSR algoritmusa 2.2.3. Balducci és Pearlman üzenetküldés modellje 2.2.4. Figueras SSSR keresése szélességi bejárással
13 13 21 24 25
3. Tesztelés
29
3.1. Az összes kör keresése a gráf összeomlasztás módszerével
29
3.2. Zamora SSSR algoritmusa
31
3.4. Figueras SSSR algoritmusa
31
3.5. A mélységi keresésre és a szélességi keresésre alapuló algoritmusok összehasonlítása
32
4. Összefoglalás
33
Irodalomjegyzék
34
1
Bevezetés
A kémiai informatika egy viszonylag új tudományág. A gyógyszergyárak, olajipari, petrolkémiai és műanyagipari vállalatok kutatásai ma már elképzelhetetlenek lennének komoly informatikai támogatás nélkül. Az elsődleges feladat a különféle vegyületekkel kapcsolatos szerkezeti és egyéb információk tárolása, megjelenítése és hatékony keresése. Ezen kívül fontos célkitűzés az is, hogy a valós laboratóriumi kísérleteket összetett számításokkal, virtuális vizsgálatok elvégzésével támogassák, illetve prognózist adjanak a vegyületek aktivitására nézve a hatékonyabb labormunka érdekében. Az ilyen kutatások létjogosultságát az adja, hogy az informatikai számítások, előszűrések nagyságrendekkel olcsóbban és gyorsabban végezhetők el, mint a kísérletezés.
Az informatikában a molekulákat szerkezeti gráfokkal reprezentáljuk, amelyeknek csúcsai az egyes atomoknak, élei pedig a köztük lévő kötéseknek felelnek meg. A kémiai informatika legfontosabb feladati közé tartozik a különböző részstruktúrák keresése ezekben a molekulagráfokban. Ebben a dolgozatban is ezt a problémakört vizsgáljuk, speciálisan a molekulákban megtalálható körök és körredszerek keresésével foglalkozunk. Vizsgálataink középpontjában a kémiai értelemben releváns köröket tartalmazó minimális körbázis áll, az ún. Smallest Set of Smallest Rings (röviden SSSR). Ezek a körhalmazok – kémiai terminológia szerint gyűrűrendszerek – meghatározó szerepet töltenek be számos alkalmazásban. Használják őket a kémiai nevezéktanban (IUPAC név generálása), molekulaleírók (fingerprintek) készítéséhez, a struktúrák aromásságának felismeréséhez, a molekulák térbeli felépítésének vizsgálatához (sztereokémia), és még sok más területen.
A dolgozat célja a körök és körrendszerek keresésére adott néhány hatékony algoritmus tanulmányozása és implementálása, valamint az esetleges hibáik és hiányosságaik feltérképezése, a lehetséges javítások vizsgálata. Az implementációkat Java nyelven készítettük, és felhasználtuk egy magyar kémiai informatikai cég, a ChemAxon Kft. (www.chemaxon.com) publikus osztálykönyvtárának egyes komponenseit.
2
A tárgyalás során feltesszük, hogy az Olvasó rendelkezik gráfelméleti alapismeretekkel, tisztában van a szokásos jelölésekkel, és ismeri az alapvető gráfalgoritmusokat.
3
1. Körhalmazok molekulagráfokban A gráfelmélet alapfogalmait és jelöléseit ismertnek feltételezve, vizsgáljunk meg néhány, a körök és körrendszerek tanulmányozásához elengedhetetlen fogalmat. A következő definíciók és állítások megtalálhatóak Berger cikkében [2].
1.1. Alapfogalmak Legyen a továbbiakban G = (E, V) egy irányítatlan gráf. A G gráfban a köröket az élhalmazaikkal írjuk le. Ez a leírás ábrázolható egy karakterisztikus vertorral: ha a gráf adott éle szerepel a vizsgált körben, akkor 1 az érték, különben 0. A körrendszer olyan részgráf, amelynek minden éle egy kör része. Két kör vektoriális összege az élhalmazaik szimmetrikus differenciája, azaz: 𝐶 ′ 𝐶 ′′ = (𝐶 ′ ∪ 𝐶 ′′ ) ∖ (𝐶 ′ ∩ 𝐶 ′′ ). A G gráf körei által meghatározott tér legyen C(G). C(G) azon részhalmazát, amely elemeiből a művelet segítségével kifejezhetjük G összes körét, de ezen részhalmaz egyik eleme sem áll elő a többi elem -összegeként, a C(G) körbázisának (cycle basis) vagy röviden bázisának nevezzük, és B-vel jelöljük. C(G) tér dimenziója a körrendszer leírásához szükséges körök számának minimuma, vagyis a bázisokban lévő körök száma. Ez a szám megegyezik a G gráf ciklomatikus számával (cyclomatic number), amit a következőképpen határozunk meg: 𝜇(𝐺) = |𝐸| − |𝑉| + 𝑐(𝐺), ahol c(G) a G gráf összefüggő komponenseinek száma. A ciklomatikus szám azt mutatja meg, hogy legalább mennyi élt kell törölnünk a gráfból, hogy az körmentes legyen.
Egy C kört eleminek (elementary) nevezünk, ha összefüggő és minden benne szereplő csúcs C halmazra vonatkozó fokszáma pontosan 2. A szokásos kémiai terminológiában az ilyen köröket gyűrűknek nevezik. A dolgozat további fejezeteiben a kör illetve a gyűrű fogalmakat az elemi kör szinonimáiként használjuk. Ha a gráfban létezik olyan él, amely nem része a C körnek, de mindkét végpontja része C-nek, akkor az ilyen élt C húrjának nevezzük. Az olyan elemi kört, amelyhez a gráfban nem tartozik húr, egyszerű vagy húrmentes körnek (simple or chordless cycle) nevezzük. Azt az elemi kört, amelyikhez pontosan egy húrt tartozik, kötött 4
körnek nevezzük (tied cycle). Adott C kör hossza megegyezik a benne lévő élek számával. Egy B bázis hossza a benne szereplő körök hosszának összege: 𝑙(𝐵) = ∑|𝐶| 𝐶∈𝐵
A bázisok közül a minimális hosszúságúakat nevezzük minimális bázisnak (minimum cycle basis).
1.1. ábra
A fenti példán (1.1. ábra) látható gráf 3 elemi kört tartalmaz: C1 = {a, b, j, ,h, i}; C2 = {c, d, e, f, g, j}; C3 = {a, b, c, d, e, f, g, h, i}. A 3 kör közül csak C3-nak van a gráfban húrja (a j él), ezért C1 és C2 egyszerű körök, C3 pedig kötött kör. A három kör közül bármely kettő bázis. Könnyen látható, hogy a minimális bázis B = {C1, C2}.
A minimális bázis nem mindig egyértelmű. A következő példában (1.2. ábra) bármelyik 2 darab 6 hosszú kör minimális bázist alkot, így 3 különböző minimális bázis is létezik.
5
1.2. ábra
A következő példán (1.3. ábra) látható gráf elemi körei: C1 = {a, b, c, l, m, n}; C2 = {d, e, f, g, h, i}; C3 = {d, k, j, g, h, i}; C4 = {e, f, j, k}. Nem elemi körre példa: C5 = {a, b, c, d, e, f, g, h, i, l, m, n}. A C2 kör két csúcsát összekötő út nem húr, mert nem egy él alkotja (k és j élek). Példa bázisra: B1 = {C1, C2, C3}; B2 = {C1, C2, C4}; B3 = {C1, C3, C4}. B2 és B3 egyaránt minimális bázisok is.
1.3. ábra
Egy kör akkor releváns (relevant), ha nem írhatjuk le rövidebb körök -összegeként, azaz ha tartalmazza legalább egy minimális bázis [11] [12]. Egy G gráf releváns köreinek halmazát R(G)-vel jelöljük.
Egy e E élre legyen S(e) az e-t tartalmazó körök közül a legrövidebbek halmaza. Ekkor a G gráfra: 𝑆(𝐺) = ⋃𝑒∈𝐸 𝑆(𝑒). 6
S(G)-re és R(G)-re teljesül az alábbi összefüggés [13]. 1.1. Tétel: Minden G gráfra S(G) R(G), vagyis S(G) minden eleme releváns kör.
A későbbi kördefiníciókban fontos szerepe lesz a Kirchhoff-bázisoknak: Legyen T egy feszítőfája G-nek. Ekkor minden olyan e él, amelyre 𝑒 ∈ 𝐺 de 𝑒 ∉ 𝑇 pontosan egy kört képez a T {e} gráfban. Az így előállítható körök T-re nézve alapvető vagy fundamentális körök (fundamental cycle). Egy adott feszítőfához tartozó fundamentális körök egy fundamentális bázist alkotnak. Egy bázist, ami fundamentális egy T feszítőfára nézve, Kirchhoff-bázisnak nevezünk.
1.2. Tétel: A G gráf minden elemi köre megtalálható G valamely Kirchhoff-bázisában.
Bizonyítás: Minden C elemi kör felbontható egy P útra és egy e élre, amely „bezárja” a kört. A P út kiegészíthető G egy T feszítőfájává (ami nyilvánvalóan nem fogja tartalmazni e-t), így C része a T-ből származó Kirchhoff-bázisnak. A fundamentális kör kifejezés anélkül, hogy hivatkozna egy T feszítőfára tehát elemi kört jelent.
G gráf köreinek egy (G) darab körből álló kollekciója fundamentális, ha létezik a köröknek egy olyan rendezése, ami kielégíti az alábbi állítást (minden 2 j (G) esetén): 𝐶𝑗 \(𝐶1 ∪ 𝐶2 ∪ … ∪ 𝐶𝑗−1 ) ≠ *+ A B fundamentális kollekció egy fundamentális bázis. A B bázis szigorúan fundamentális (strictly fundamental), ha a fenti állítás a kollekció minden rendezésére igaz.
1.3. Tétel: Egy bázis akkor és csak akkor szigorúan fundamentális, ha Kirchhoff-bázis. Részletesebb magyarázat és bizonyítás a [9] cikkben található. 7
1.2. Smallest Set of Smallest Rings (SSSR) A kémiai informatikában gyakran használt fogalom a legkisebb gyűrűk legkisebb halmaza, azaz a Smallest Set of Smallest Rings (a továbbiakban SSSR). Az SSSR eredeti definíció szerint egy minimális hosszúságú Kirchhoff-bázist jelent [4]. Ennek megtalálása NP-nehéz feladat [3]. Ugyanakkor az elmúlt néhány évtized kémiai irodalmában az SSSR-t a minimális bázis szinonimájaként is használják [4]. Ez a kétértelműség azon a félreértésen alapul, miszerint minden bázis (vagy legalábbis minden minimális bázis) szigorúan fundamentális, azaz származtatható egy megfelelő feszítőfából (1.3. Tétel). Ez a definícióbeli váltás szükséges ahhoz, hogy olyan körhalmazokat is megkapjunk, amik az eredeti definíció szerint nem, de a kémiai intuíció szerint jogosan kapják az SSSR megnevezést. A két legfontosabb ok, amiért Kirchhoff-bázisok helyett általában minimális bázisokat keresnek SSSR címén, az hogy a Kirchhoff-bázis kiszámítása nehezebb, és mint azt később látni fogjuk, minimális hosszú Kirchhoff-bázis nem mindig létezik.
Nem minden bázis fundamentális, de egy síkba rajzolható gráf minden minimális bázisa fundamentális. Vannak azonban olyan síkba rajzolható gráfok, melyeknek nincs szigorúan fundamentális minimális bázisa.
1.4. ábra
Az 1.4. ábrán látható első gráf (a) minimális bázisa a 4 külső háromszögből (jelöljük őket C1, C2, C3, C4 -el), valamint a középső négyszögből (C5) áll. A (C1, C2, C3, C4, C5) rendezés nem elégíti ki a fundamentális bázis definíciójában szereplő feltételt, ugyanis 𝐶5 ⊆ 𝐶1 ∪ 𝐶2 ∪ 𝐶3 ∪ 𝐶4 = 𝐸, tehát a minimális bázis nem szigorúan fundamentális. A (b) ábrán egy kémiailag realisztikusabb szerkezeten figyelhetjük meg ugyan ezt a jelenséget. A bemutatott példákban tehát az eredeti SSSR definíció szerinti fogalom nem található meg, ezért is érdemes a másikat alkalmaznunk.
8
Nem síkba rajzolható gráfok esetében még élesebb az eltérés. Léteznek ugyanis gráfok, amelyek nem-fundamentális minimális bázisokkal rendelkeznek. Bővebb magyarázat Leydold cikkében [10]. Ezen okok miatt a dolgozat további részeiben az SSSR megnevezést a minimális bázis szinonimájaként használjuk.
9
2. Körkereső algoritmusok 2.1. Egy gráf összes körének keresése A körhalmazok vizsgálata kapcsán a legtermészetesebb kiindulás egy gráf összes elemi körének meghatározása. Első lépésként egy olyan algoritmus bemutatása következik, amely egy gráf összes körét határozza meg. Ez fontos lehet bizonyos alkalmazásokban.
2.1.1. Gráf összeomlasztás A gráf „összeomlasztás” módszert Hanser, Jauffret és Kaufmann [8] publikálták 1996-ban. Az algoritmus könnyen implementálható és hatékony megoldást kínál egy gráf összes körének megkeresésére. A megoldás első lépésében a molekulagráfot (M-gráf) átalakítjuk egy ún. útvonal-gráffá (path-graph, a továbbiakban P-gráf). Az átalakítás lényegében csak az élek felcímkézéséből áll: kezdetben minden xy él pxy címkéje [xy] (2.1. ábra). A második lépés a P-gráf ismételt redukcióján alapul. Az alapötlet az, hogy M-gárf egy axb sétája leírható egy éllel a P-gráfban ([a-x-b] címkével). Így anélkül törölhetünk csúcsokat, illetve éleket a P-gráfból, hogy bármilyen, a 2.1. ábra
körökre vonatkozó topológiai információt veszítenénk. Egy x csúcs törlési szabálya: minden rá illeszkedő ax, xb élpárhoz, melyre teljesül az alábbi feltétel, létre kell hoznunk egy új ab élt, melynek címkéje a pax és pxb élcímkék konkatenciója. Feltétel:
yz esetén : pxy pxz = {x} vagy
y=z esetén : pxy pxz = {x, y}, ahol a művelet az operandus utak közös csúcsait választja ki.
Erre a feltételre azért van szükség, hogy az algoritmus nem ismerjen fel körként olyan sétákat, amiben egy él többször szerepel. 10
Az algoritmus végrehajtása során a csúcsokat a fenti szabályok szerint egymás után töröljük. Ha hurokél keletkezik, akkor feljegyezzük az általa reprezentált körét az eredeti gráfnak. A törlés véges sokszori alkalmazása (véges gráfok esetén) a gráf „összeomlásához” vezet. Amire a redukció befejeződik (V = {}, E = {}), az összes kört megtaláltuk.
A 2.2. ábra egy egyszerű példán mutatja be az algoritmus futását.
2.2. ábra
11
Az algoritmus hatékonysága erősen függ a csúcsok törlésének sorrendjétől. A minimális számú "felesleges" konkatenáció elvégzése érdekében a csúcsokat fokszám szerinti növekvő sorrendben érdemes törölni.
Nyilvánvaló, hogy az algoritmus véges (véges számú csúcs törlése után terminál). A műveletigény erősen függ a gráfban található körök számától. Molekulagráfokban tipikusan kevés kör található (néhány kirívó esettől eltekintve). Az algoritmus lépésszámának, illetve futási idejének összehasonlítását a különböző csúcskiválasztási stratégiák szerint a tesztelés fejezetben tárgyaljuk.
12
2.2. SSSR algoritmusok
Az elmúlt néhány évtizedben számos algoritmus született az SSSR hatékony keresésére. Ebben a fejezetben néhány SSSR algoritmus kerül bemutatásra.
2.2.1. Zamora SSSR algoritmusa
Zamora 1976-ban megjelent cikkében [14] publikált algoritmusa egy gráf összes körének meghatározása nélkül találja meg az SSSR-t. Az algoritmus tárgyalásakor kizárólag körhalmazokkal foglalkozunk, eltekintünk a gráf olyan részeitől, melyek nem tartalmaznak kört. Az algoritmus működésének megértéséhez három különböző osztályba soroljuk a körrendszereket:
I.
SSSR, melynek nincs olyan valódi részhalmaza, amely minden csúcsot tartalmaz.
II.
SSSR, melynek van minden csúcsot, de nem minden élt tartalmazó valódi részhalmaza.
III.
SSSR, melynek van minden csúcsot és minden élt tartalmazó valódi részhalmaza.
A 2.3. ábrán a különböző SSSR típusokra látunk példát, szürkével jelölve az említett részhalmazokat.
13
2.3. ábra
Az SSSR meghatározása:
I. Fázis Az I. típusba tartozó körhalmazok SSSR-je meghatározható a következő módon: véletlenszerűen kiválasztunk egy új csúcsot és megkeresünk egy legkisebb kört, ami tartalmazza. Minden olyan csúcsot, melyet ez a kör tartalmaz, megtaláltként jelölünk meg. Ezt addig folytatjuk, amíg minden csúcs megtaláltként lesz megjelölve. A módszer alkalmazható minden I. típusba, illetve néhány II. típusba tartozó körrendszerre is. Utóbbihoz szükséges a kezdő csúcs megfelelő megválasztása, illetve ha több legkisebb kört találunk, akkor ezekből azt kell választanunk, amelyik kevesebb új csúcsot tartalmaz. A 2.4. ábrán megfigyelhető (a) esetben, ha a besatírozott köröket találjuk meg először, az összes csúcs megtaláltként lesz megjelölve mielőtt minden szükséges kört megtalálnánk. A (b) esetben figyelembe vesszük a körökben lévő új atomok számát, így az SSSR mindhárom körét megtaláljuk.
14
2.4. ábra
2.5. ábra
A 2.5. ábrán látható összekapcsolódó gyűrűk esetén az csúcsok és körök véletlenszerű kiválasztásával az algoritmus befejeződhet anélkül, hogy a belső kört megtalálná. Ennek a problémának a megoldásához bevezetjük az összekapcsoltság fogalmát: legyen Ki = 1, 8 vagy 64, attól függően, hogy az i. csúcsnak 2, 3, illetve 4 szomszédja van (4 szomszéd egy tetszőleges felső limit). Legyen Li az i. csúcs szomszédjai Ki értékeinek összege. Ekkor az i. csúcs összekapcsoltsági értéke Ci = 64(Ki) + Li. Látható, hogy a példában a belső hatszög csúcsai rendelkeznek a legnagyobb C értékekkel. Így a véletlenszerű csúcsválasztás helyett, ha mindig a legnagyobb C értékkel rendelkező csúcsot választjuk, helyes eredményt kapunk az ábrán szereplő gráfra is. Az algoritmus első fázisa megadja az SSSR-t az I. típusba tartozó körrendszerekre. Azokban az esetekben, amikor nem kapunk annyi kört, amennyit az SSSR-nek tartalmaznia kell (vagyis amennyi a gráf ciklomatikus száma), akkor a második, illetve harmadik fázis végrehajtása is szükségessé válik.
15
II. Fázis A II. típusba tartozó körrendszerek SSSR-jének megtalálásához bevezetünk egy számlálót minden élhez, ami számon tartja, hányszor használtuk (hány kiválasztott körben szerepel). Ha az első fázis végére marad olyan él, aminek a számlálója 0, akkor megkeressük azt a legkisebb kört, ami tartalmazza az élt, az SSSR halmazhoz adjuk, majd a kör minden élének számlálóját megnöveljük eggyel. Az első fázisban alkalmazott heurisztikához hasonlóan, az azonos méretű körök közül itt is azt részesítjük előnyben, amelyik a lehető legkevesebb új élt adja a rendszerhez (azaz amelyikben a legkevesebb 0 számlálójú él van).
III. Fázis Ha az összes csúcs és él „felhasználása” után sem találtuk meg a kívánt számú kört, akkor a következő lépés az összes nem használt lap keresése. A nem használt lap esetünkben egy olyan gyűrű, aminek minden csúcsának legalább 3 szomszédja van, továbbá az élei közül legfeljebb egynek lehet az előző fázisban bevezetett számlálója egynél nagyobb, az összes többinél egynek kell lenni ennek az értéknek.
A legkisebb kör algoritmus
A tárgyalt SSSR algoritmus eljárásként használ egy másik algoritmust: egy adott csúcsot vagy élt tartalmazó legkisebb kör megkeresésére. Az algoritmus útbejárásokon alapul. A köröket egy csúcsból kiinduló utak bejárásával találhatjuk meg. Az utak hosszára felső korlát az aktuálisan megtalált legkisebb kör (amit eltárolunk), így a bejárandó utak hossza folyamatosan csökken.
FIRST
a kiinduló csúcs
SM
a megtalált legkisebb kör mérete
SIZE
az aktuális úton lévő csúcsok száma
A[j]
a j. csúcs szomszédjainak száma
GRAPH[i,j]
gráfábrázolás, ahol i = 1, 2, …, A[j] a j. atom szomszédjai (j = 1, …, N, ahol N gráf csúcsainak száma)
X[j]
a j. csúcs éppen vizsgált szomszédja (1 ≤ X[j] ≤ A[j])
P[k]
az aktuális úton szereplő csúcsok, k = 1, …, SIZE
USE[j]
indikátor, USE[j] = 1, ha a j. atom szerepel P-ben, különben 0
BEST[k]
az aktuális legkisebb kör, k = 1, …, SM 16
BEGIN //Inicializáció SM := N + 1 X := 0 SIZE := 1 P[SIZE] := FIRST CURRENT := FIRST USE[FIRST] := 1 //Út felderítés Alpha: X[CURRENT] := X[CURRENT]+1 if X[CURRENT] > A[CURRENT] goto Scan ATTACHED := GRAPH[X[CURRENT], CURRENT] if SIZE > 1 & ATTACHED = P[SIZE-1] goto Alpha if USE[ATTACHED] = 1 goto Beta //Útkiterjesztés SIZE := SIZE + 1 P[SIZE] := ATTACHED USE[ATTACHED] := 1 CURRENT := ATTACHED if SIZE >SM goto Scan goto Alpha //Megerősítés Beta:
if ATTACHED FIRST goto Alpha
//Kört találtunk if SIZE < SM goto Better //Azonos méretű körök esetén a választási kritériummal kiegészíteni goto Scan Better: SM := SIZE BEST := P //Visszamegyünk az úton Scan:
X[CURRENT] := 0 USE[CURRENT] := 0 SIZE := SIZE – 1 CURRENT := P[SIZE] if SIZE = 1 &X[CURRENT] + 1 ≥ A[CURRENT] goto Done goto Alpha
Done: //a legkisebb kör BEST[1:SM]-ben END.
17
Ha egy adott csúcs helyett adott élre szeretnénk megtalálni a legkisebb tartalmazó kört, az inicializációs rész a következőképpen módosul: SM := N + 1 X := 0 P[1] := FIRST P[2] := SECOND X[FIRST] := A[FIRST] SIZE := 2 USE[FIRST] := 1 USE[SECOND] := 1 CURRENT := SECOND goto Alpha
A FIRST és SECOND változók a kiindulási él két végpontját jelölik. Az SSSR algoritmus leírása
I. fázis 1. Válasszuk ki a legnagyobb összekapcsoltsági értékkel rendelkező meg nem talált csúcsot. Ha nincs ilyen csúcs, akkor lépjünk a II. fázisra. 2. Alkalmazzuk a körkereső algoritmust, a következő módosításokkal: a. Az útkiterjesztés során összegezzük az úton lévő csúcsok összekapcsoltsági értékét és tartsuk számon a nem használt csúcsokat. b. Ha azonos méretű körök között kell választanunk, akkor válasszuk azt amelyik (i) a legkevesebb nem használt csúcsot, illetve (ii) a legkevesebb nem használt élt tartalmazza. Amennyiben ezek sem tudunk dönteni, válasszuk a (iii) legmagasabb összekapcsoltsági értékkel rendelkezőt. c. Az úton visszafelé haladva állítsuk vissza a fenti számlálókat. 3. A talált kör csúcsait jelöljük meg megtaláltként. 4. A talált kör éleinek növeljük meg a használati számlálóját eggyel. 5. Vissza az 1. lépésre. II. fázis 6. Jelöljük meg az összes csúcsot meg nem találtként. 7. Ha a megtalált körök száma megegyezik az SSSR meghatározott méretével, akkor END. 8. Válasszuk egy nem használt élt. ha nincs ilyen, lépjünk a III. fázisra. 18
9. Alkalmazzuk a körkereső algoritmust az I. fázisban használt módosításokkal. 10. A talált kör csúcsait jelöljük megtaláltként. 11. Növeljük a talált kör minden élének számlálóját eggyel. 12. Vissza a 7. lépésre. III. fázis 13. Válasszuk egy olyan élt, aminek a számlálója 1. Ha nincs ilyen, akkor lépjünk a 20-ra. 14. A választott él számlálója legyen 2. 15. Alkalmazzuk a körkereső algoritmust a következő módosításokkal: az útkiterjesztés csak akkor végzett, ha az él minkét végpontjának legalább 3 szomszédja van és ha az úton szereplő, kettő vagy annál nagyobb számlálóval rendelkező élek száma nem haladja meg az egyet. 16. Ha nem találtunk kört, lépjünk a 13-ra. 17. Ha kört találtunk tároljuk el. 18. Növeljük a körben szereplő élek számlálóját eggyel. 19. Vissza a 13. lépésre. 20. Rendezzük a köröket méretük szerinti növekvő sorrendbe. 21. A rendezett sorozat elejéről válasszunk le annyi kört, amennyi az SSSR várt száma. END. Vége az SSSR algoritmusnak. Az algoritmus lehetséges hibái A harmadik fázisban alkalmazott nem használt lap keresés kihasználja azt, hogy az első és második fázis körkeresése igyekszik maximalizálni az élek használati számlálóját, amikor azonos méretű körök között kell választania. Azt feltételezzük tehát, hogy a nem elemi körök, illetve a már megtalált körök legalább két olyan élt tartalmaznak, amelyek használati számlálója legalább kettő. Ez a feltételezés nem mindig helytálló, és kétfajta hibához is vezethet. Az első esetben az SSSR utolsó körének éleit kisebb körök is tartalmazzák, néhányat több is. Egy ilyen esetet láthatunk a 2.6. ábrán. Az (a) képén az első fázis utáni állapotot figyelhetjük meg (vékony szürke vonallal jelölve a nem megtalált éleket). Az első fázisban 6 kört találtunk meg (M-D-E, B-A-I, J-K-L, C-B-M-D, F-E-M-L, G-H-I-J körök). A gráf ciklomatikus száma, azaz az SSSR várt mérete 9. A második fázisban a két nem használt élre keressük meg a tartalmazó köröket (C-H-I-B és F-G-J-L). A harmadik fázisban a belső ötszöget (I-J-L-M-B) 19
kellene megtalálni ahhoz, hogy a bázis valóban minimális legyen. Ehelyett az algoritmus a külső hatszöget (C-D-E-F-G-H) választja az utolsó körnek. Ennek az az oka, hogy a belső ötszög nem elégíti ki az élek használati értékére vonatkozó feltételt. A (b) ábrán az élek használati számlálóját láthatjuk a második fázis után.
2.6. ábra
A másik esetben az algoritmus nem találja meg az utolsó kört. Ezt az esetet mutatja be a 2.7. ábra. A második fázis után a megjelölt élek két körben is szerepelnek. Az algoritmus emiatt nem képes megtalálni az utolsó kört (a nagy nyolcszöget), mert két darab egynél nagyobb számlálóval rendelkező élt tartalmaz.
2.7. ábra
20
Erre az esetre megoldás lehet, ha ilyen esetekben figyelmen kívül hagyjuk az élek használatát jelző számlálókat. Ez esetben fontos figyelnünk arra, hogy ne tároljunk el olyan kört, amit már egy korábbi fázisban megtaláltunk.
Az implementációnkban megoldásként egy kombinált módszert alkalmaztunk: ha az eredeti módszer a vártnál kevesebb számú körrel tér vissza, lefuttatjuk a számlálók figyelmen kívül hagyásával is. Ez a megoldás sem fedi le az összes lehetséges szerkezetet, de a valós kémiai molekulákra futtatott tesztek mindegyikében helyes eredményt adott.
2.2.2. Doucet SSSR algoritmusa
A 2.2.2. és a 2.2.3. szakaszban bemutatott algoritmusokat nem valósítottuk meg, de rövid tárgyalásuk a 2.2.4. szakaszban látható módszer megértését segíti elő. Doucet és szerzőtársai 1993-ban publikált módszerében [6] a kettő fokszámú csúcsok (a továbbiakban N2) játszanak kulcsszerepet. Az alapötlet a következő: 1. Keressük meg egy adott N2 csúcsot tartalmazó legkisebb kört (mélységi bejárással), és jegyezzük fel. 2. Töröljük ki a gráfból az imént talált kör egy N2 csúcsát, és azokat a csúcsokat, amelyek a törlés után már nincsenek körben (azaz a csúcshoz tartozó láncokat). 3. Ismételjük az előző két lépést, amíg van N2 csúcs. A törlendő csúcs kiválasztása számos kérdést vet fel, illetve az N2 csúcsokkal nem rendelkező struktúrák is speciális lépéseket igényelnek (lásd később). Amiért viszont érdemes alaposan megvizsgálni a módszert, az az, hogy a 2.5. ábrán látható „beágyazott” kört (a középső hatszöget) megfelelően kezeli. Ahogy azt Zamora algoritmusánál is megfigyelhettük, az ilyen körök nehézséget jelentenek a standard gráfbejáró algoritmusoknak, mert az összes csúcsot és élt „elfogyasztják”, mielőtt a középső, beágyazott kört detektálnák.
A legalább egy darab N2 csúcsot tartalmazó struktúrák esetében a fent vázolt eljárást alkalmazzuk. A körkereséshez egy mélységi bejárást alkalmaz az algoritmus. A körből egy kiválasztott N2 csúcs (és a hozzá tartozó lánc) törlése után újabb N2 csúcsok keletkeznek a gráfban. 21
Az algoritmus tehát a következő ciklusból áll:
Amíg a gráf tartalmaz N2 csúcsot: 1. Válasszunk egy N2 csúcsot 2. Alkalmazzuk a körkeresést a választott csúcsra, és jegyezzük fel a talált kört. 3. Válasszunk egy N2 csúcsot az imént talált körből (nem feltétlenül az 1. lépésben választottat), és töröljük a gráfból (a hozzá tartozó lánccal együtt). Ahogy azt már említettük, a megfelelő csúcsválasztás a 3. lépésben kritikus fontosságú, ugyanis bizonyos esetekben a nem megfelelő csúcs törlése nem megfelelő SSSR halmazt eredményez. A 2.8. ábrán látható I. gráf esetében, ha az (a) csúcsot választjuk ki az 1. lépésben, a jobb oldali, 5 hosszú kört találjuk meg, és jegyezzük fel. A 3. lépés csúcstörlését alkalmazhatjuk az (a), (b) vagy (c) csúcsra. Amennyiben az (a) csúcsot töröljük, egy 7 hosszú kör marad az utolsó lépésre, és így a kapott SSSR egy öt és egy hét hosszú gyűrűből áll, ami nyilvánvalóan hibás. Amennyiben a (b) vagy (c) csúcsokat töröljük, a megmaradt 6 hosszú kör alapján az algoritmus a megfelelő SSSR-t eredményezi (egy öt és egy hat hosszú gyűrű). A megoldást egy olyan eljárás jelenti, amelyik egy „próbatörlést” végez a szóba jövő csúcsokra.
A talált kör minden N2 csúcsára: 1. Töröljük ki az aktuális csúcsot. 2. A többi, törlésre esélyes csúcsra megkeressük a legkisebb tartalmazó kört, és eltároljuk (lánconként elég egy csúcsra elvégeznünk ezt a lépést). 3. Visszaállítjuk az 1. lépésben törölt csúcsot.
Véglegesen azt a csúcsot töröljük, aminek a törlésekor a legkisebb kört találtuk.
A példánkon alkalmazva az eljárást az (a) csúcsot törölve a (b) csúcsra egy 7 hosszú kört találunk, a (b) csúcsot törölve az (a) csúcsra pedig egy 6 hosszút. Véglegesen a (b) csúcsot törölve helyes SSSR-t kapunk.
Sajnos a módszer nem nyújt megoldást minden esetben. A 2.8. ábrán látható II. gráf esetében, ha az (a) csúcsot választjuk ki első lépésben, akkor nincs más lehetőség a csúcstörlésre, mint az (a) csúcs (a tartalmazó legkisebb kör nem tartalmaz más N2 csúcsot). Az (a) csúcs törlése 22
után a megtalált hibás SSSR [5, 5, 8] hosszú gyűrűkből áll. Az ilyen esetekben a csúcsok kiválasztásának sorrendjén múlik a helyes SSSR meghatározása. Doucet javaslatot tesz az N3 csúcsok között elhelyezkedő N2 csúcs kezelésére, de a II. gráfból levezethető olyan szerkezet, amire az ötlete nem működik. A problémára John Figueras próbál megoldást adni a később bemutatott algoritmusban [7] (lásd 2.2.4. szakasz).
2.8. ábra
Az N2 fokú csúcsokkal nem rendelkező gráfok vizsgálatára Doucet a következő módszert javasolja. Amennyiben az adott gráf nem tartalmaz N2 csúcsokat, az algoritmus kiválaszt egy alkalmas N3 csúcsot, aminek a törlésével N2 csúcsokat hoz létre. Az alkalmas csúcs kiválasztásának menete a következő: Minden N3 csúcsra: 1. Alkalmazzuk a legkisebb kör megkeresését, az eredményt feljegyezzük (forrás kör). 2. Egy N3 csúcsot a forrás körből ideiglenesen törlünk (ez által csökken a szomszédok fokszáma). 3. A keletkezett N2 csúcsokra alkalmazzuk a legkisebb kör keresését, és ha a legkisebb talált kör kisebb, mint az eddig eltárolt kör, akkor lecseréljük azt. 4. A törölt N3-at visszaállítjuk. Amelyik N3 csúcs törlésekor a legkisebb kört találtuk, azt véglegesen töröljük. Így már alkalmazhatjuk az eredeti módszert a keletkező N2 csúcsokra.
23
2.2.3. Balducci és Pearlman üzenetküldés modellje Egy másik megközelítést alkalmaz Renzo Balducci és Robert S. Pearlman 1994-ben megjelent cikkében [1]. A fő újdonság a módszerükben, hogy elhagyják az eddig alkalmazott heurisztikus módszereket, amelyek nem minden esetben adnak helyes megoldást, és egy minden lehetséges struktúrát lefedő algoritmust mutatnak be.
Az algoritmus a gráfot egy hálózatként modellezi, amelyben minden csúcs egy üzenet adóvevőként működik. Minden csúcshoz két buffert rendelünk, az egyik fogadja a bejövő üzeneteket (receive), a másik továbbítja azokat (send).
Az üzenetek tartalma:
a kezdőcsúcs, ahonnan indult az üzenet
az első él, amelyiken végighaladt
az utoljára érintett csúcs
az eddig bejárt élek listája
Az algoritmus a következő ciklust hajtja végre:
minden csúcs elküldi a send buffere tartalmát a közvetlen szomszédjainak (kivéve annak, amelyiktől kapta – ebben segít az utoljára érintett csúcs információ)
a kapott üzenetekben a csúcsok frissítik az információkat
minden csúcs megvizsgálja a saját és szomszédjai útinformációit az esetleges körlezárások miatt.
ha valamelyik csúcs kört detektál, megvizsgáljuk, hogy lineárisan független-e az eddigi SSSR halmaztól, és ha igen, hozzáadjuk.
A
lineáris
függetlenség-vizsgálat
fontos
lépés
az
algoritmusban, hiszen például egy ciklohexán molekula (2.9. ábra) esetén a szimultán indított üzenetek miatt 6-szor fogjuk megtalálni az egyetlen kört.
2.9. ábra
24
A szerzők bizonyítják, hogy az algoritmus egzakt megoldást ad, legrosszabb esetben O(d3N2logN) művelet elvégzésével, ahol N a csúcsok száma, d pedig a maximális fokszám a gráfban. Kémiai struktúrákban d konstansnak tekinthető (tipikusan 4), így kémiai alkalmazásokban műveletigény O(N2logN).
2.2.4. Figueras SSSR keresése szélességi bejárással
Doucet algoritmusát alapul véve John Figueras egy szélességi keresésre alapuló eljárást mutatott be 1996-ban megjelent cikkében [7]. Két fontos módosítást alkalmazott az eredeti algoritmusban. Elsőként egy adott csúcsot tartalmazó legkisebb kör keresésekor az eddig használt mélységi keresés helyett szélességi keresés alkalmazását javasolja. A másik módosítás a törlendő N2 csúcsok problémájára ad megoldást. Az alapvető probléma a csúcstörléssel az információvesztés. Ahogy a 2.6. ábra II. gráfja esetében láthattuk, bizonyos csúcsok törlésével az SSSR meghatározásában kulcsfontosságú köröket veszíthetünk el. A megoldás a problémára az lehet, ha késleltetjük az N2 csúcsok törlését mindaddig, amíg mindegyiküket hozzá nem rendeltük egy tartalmazó körhöz. A csúcsok ellenőrzése és törlése helyett egy új eljárást vezetünk be, ami az élekre fókuszál. Az új algoritmus tehát a következő modulokból áll:
1. getRing(n, ringSet, ringSize): szélességi bejárásra alapuló eljárás, amely visszaadja az n. csúcsot tartalmazó legkisebb kört (ringSet). 2. trim(n): eltávolítja a kapcsolati táblából az n. csúcshoz tartozó összes élt, 0-ra redukálva a fokszámát. 3. checkEdges(n, ringSet): meghatároz és kitöröl egy optimális élt az N2 csúcsokkal nem rendelkező gráfból. Az adott kör (ringSet) minden éle átesik egy „próbatörlésen”. Az él mindekét végpontjára lefuttatjuk a getRing eljárást, és a két visszakapott kör közül a nagyobbikat feljegyezzük. A próba után a törölt élt visszaállítjuk. Véglegesen azt az élt töröljük, amelyik a legkisebb kört adta vissza. Az él törlése után N2 csúcsok keletkeznek a gráfban, és alkalmazhatjuk az eredeti módszert.
25
fullSet := [1..N]; trimSet := [] repeat Add nodes of degree 0 to trimSet Add nodes of degree N2 in fullSet-trimSet to nodesN2 Find a node init in fullSet-trimSet having minimum degree if minimum degree = 1 then trim(init) and add init to trimSet else if minimum degree = 2 then begin for each node i in nodesN2 begin getRing(i, ringSet, ringSize); if ringSize > 0 then Check SSSR for a duplicate of ringSet if no duplicate is found add ringSet to the SSSR end for each chain of N2 nodes, isolate one N2 node and break one bond end else if minimum degree = 3 then begin getRing(init, ringSet, ringSize); if ringSize > 0 then save ringSet in SSSR checkEdges(init, ringSet); end until fullSet = trimSet
Az algoritmusban elsődleges prioritást kap az egy fokú csúcsok törlése. Ha a legkisebb fokszám 2, a getRing eljárást alkalmazzuk az N2 csúcsokra, és a kapott köröket elmentjük az SSSR halmazba (amennyiben az SSSR nem tartalmazza még a talált kört). A tényleges implementációban nem szükséges minden N2 csúcson alkalmazni a getRing eljárást, elég minden láncban egy csúcsra meghívnunk. A körkeresés után a nodesN2 halmaz minden N2 csúcsán elvégzünk egy éltörlést, így redukálva a fokszámukat egyre. Az egy fokú csúcsok törlésével újakat generálunk, így a következő lépésben az újonnan keletkezetteket töröljük. Amennyiben a minimum fokszám 3, a checkEdge metódus kiválaszt egy alkalmas élt és törli azt, ezzel redukálja a minimum fokszámot 2-re. Az algoritmus akkor végzett, ha minden csúcs a trimSet-ben van. 26
A szélességi bejárásra alapuló körkeresési algoritmus (breadth-first search /BFS/) A bemutatott módszerben kulcsfontosságú egy adott csúcsot tartalmazó egy legkisebb kör megkeresése. A 2.10. ábra (a) példáján meg szeretnénk határozni az 1. csúcsot tartalmazó kört. A gráf minden i csúcsához hozzárendelünk egy listát (path[i]) amely a kiindulási pontból az adott csúcsba talált utat tárolja. A listák kezdetben üresek.
2.10. ábra
Első lépésben a kiindulási csúcsból (1) közvetlenül elérhető csúcsokhoz rendelünk utakat. Ezek path[2] = [1,2] és path[5] = [1,5] lesznek. A következő lépésben a 2. csúcs szomszédjait vizsgáljuk (a szülő csúcsot minden csúcsra számon tartjuk, így nem indulunk el „visszafelé” az úton). Ahogy 2. csúcsból eljutunk a 3. csúcsba, megvizsgáljuk, hogy a path[3] üres-e. Amennyiben nem üres, összeérő utakat találtunk, ami lehet egy kör lezárása. Esetünkben a path[3] üres, így értékül adjuk neki az utat, amelyen elértük: path[3] = path[2] + [3] = [1,2,3]. Hasonlóképpen az 5. csúcsból is kiterjesztjük az utat a 4. csúcsra. Amikor a 3. csúcsból a 4. csúcsba terjesztjük ki az utat, a path[4] már nem üres. Az érvényes kör teszteléséhez ki kell számítanunk a megtalált két út metszetét: path[3]*path[4] = [1,2,3]*[1,5,4] = [1]. Akkor találunk érvényes (a kiindulási ponton átmenő) kört, ha a metszet egyelemű (ilyenkor ez a csúcs nyilván a kiindulási pont lesz). A kört a két út uniója határozza meg: path[3]+path[4] = [1,2,3,4,5]. Az, hogy az érvényes kör lezáráshoz a két út metszetének egyeleműnek kell lennie fontos szerepet játszik a közbenső körök ignorálásában. A 2.10. (b) ábrán látható gráf esetében megfigyelhetjük ezt a jelenséget. Kezdjük a keresést az 1. csúcstól. Első lépésben az algoritmus feltérképezi a 2. és 6. csúcsot: path[2] = [1,2] és path[6] = [1,6]. Második lépésben az 5. (path[5] = [1,6,5]), a 3. (path[3] = [1,2,3]) és a 4. csúcsokat (path[4] = [1,2,4]) érjük el. A 3. csúcs kiterjesztésekor azt tapasztaljuk, hogy a path[4] nem üres. 27
Kiszámítjuk a két útvonal metszetét, amely két csúcsot is tartalmaz (path[3]*path[4] = [1,2]). Mivel csak akkor tekintünk érvényesnek egy kört, ha az elérési utak metszete egyelemű, ezért a 3. csúcsból 4. csúcsba vezető élt ignoráljuk, és a 4. csúcs kiterjesztésével folytatjuk az algoritmust. A további lépések az előző példával analóg módon zajlanak. Az algoritmus végül megtalálja a kisebbik tartalmazó kört az 1. csúcsra: [1,2,4,5,6]. Egy másik fontos dolog, amire az implementációnál figyelnünk kell, hogy bizonyos esetekben nem a legkisebb kört találja meg az algoritmus. Ez akkor fordulhat elő, ha egy olyan csúcsra hívjuk meg az eljárást, amelyet két kör is tartalmaz (egy k és egy k+1 hosszú, ahol k páratlan). A 2.11. ábrán látható molekula esetén az 1. csúcsra meghívva a körkeresést az algoritmus előbb találja meg a 6 hosszú kört, mint az 5 hosszút (abban az esetben, ha a csúcsokat a sorszámuknak megfelelő sorrendben vizsgáljuk). A megoldás az lehet, hogy az aktuális szint vizsgálatát nem szakítjuk meg egy kör detektálásakor, csak feljegyezzük az eredményt. Ha ugyan abban az iterációban (azaz ugyan annak a szintnek a vizsgálatakor) másik kört is találunk, akkor összehasonlítjuk a hosszukat és a rövidebbet adjuk eredményül. Amennyiben nem találunk másik kört, visszatérhetünk az elsőnek megtalálttal.
2.11. ábra
28
3. Tesztelés A teszteléséhez a National Cancer Institute (NCI) publikus molekulagyűjteményét használtuk (250252 molekula). Az algoritmusokat Java nyelven implementáltuk, egy személyi számítógépen (AMD Athlon II X4 635 2,9 GHz processzor, 4 GB RAM) és 64 bites Windows 7 operációs rendszeren futtattuk.
3.1. Az összes kör keresése a gráf összeomlasztás módszerével Az algoritmusban az elemi műveletnek a legbelső ciklus magját tekintjük, ami élcímkék feltételes konkatenációjából áll. Ahogy az sejthető, a fokszám szerinti csúcskiválasztási stratégia lényegesen jobb eredményt mutat (futási időben és a végrehajtott elemi műveletek számában), mint a véletlen választás. Már kis molekulák esetén is érezhető különbség, nagyobb méretnél viszont nem ritka a több százszoros eltérés. A 3.1. ábrán látható molekula esetében például 153-szoros különbség van a futási időben (42 s és 0,27 s), és körülbelül 5-szörös az elvégzett műveletek számában. Jól látható, hogy a műveletszám és a futási idő között nem arányos a növekedés. A futási időben azért tapasztaltunk nagyobb gyorsulást, mert nem csak kevesebb műveletet (konkatenációt) kellett végrehajtania az algoritmusnak, hanem lényegesen rövidebb élcímkékkel dolgozott. A továbbiakban ez okból csak a fokszám szerinti csúcskiválasztást használó algoritmussal foglalkozunk.
3.1. ábra
29
A 3.2. táblázat a publikus NCI adatbázisból 1000 darab véletlenszerűen kiválasztott molekulára végzett futtatás eredményeit mutatja (fokszám szerinti csúcsválasztással).
Minimum
Maximum
Átlag
Atomok száma
3
202
22,384
Körök száma
0
232
4,4
Műveletek
1
1764202
6705,01
Futási idő
0
1,48 s
0,006 s
3.2. táblázat
A 3.3. táblázatban néhány nagy molekulára (158-252 atom) figyelhetjük meg az algoritmus futási eredményeit. A 3.4. ábrán ebből a csoportból láthatunk egy, a körök szempontjából érdekes molekulát.
Minimum
Maximum
Átlag
Atomok száma
158
252
192,9
Körök száma
0
544
40,44
Műveletek
682625
3434272
156855,9
Futási idő
0,51 s
19,42 s
1,6 s
3.3. táblázat
3.4. ábra
30
3.2. Zamora SSSR algoritmusa
Zamora SSSR algoritmusának teszteléséhez a már említett NCI adatbázisból készítettünk egy 38499 darab körrendszerből álló halmazt. Az eredeti molekulákból eltávolítottuk a körök szempontjából nem releváns részeket, és az így keletkezett körhalmazokból eltávolítottuk a duplikátumokat. Átlagos futási idő
0,45 ms
Teljes futási idő
17,49 s
Átlagos atomszám
19,38
Átlagos SSSR méret
4,05 3.5. táblázat
Mint láthatjuk az átlagos SSSR méret meglehetősen kicsi. Ezért az előző fejezetben használt nagy méretű molekulákból álló halmazon is elvégeztük a körmentes részek eltávolítását. A 47 darab molekulára végrehajtott futás eredményét a 3.6. táblázat tartalmazza. Átlagos futási idő
1,13 ms
Teljes futási idő
53 ms
Átlagos atomszám
83,26
Átlagos SSSR méret
14,98 3.6. táblázat
3.4. Figueras SSSR algoritmusa A teszteléshez az NCI adatbázisból a legfeljebb 3 fokú csúcsokat tartalmazó molekulákat válogattuk ki (167690 molekula). Az algoritmusban a csúcstörlésnél fellépő nem determinisztikusság miatt a helyes SSSR megtalálása az esetek 0,13%-ában nem sikerül. A teljes fájlra a futási idő 63 másodperc volt. Ez valamivel gyorsabb, mint a Zamora-féle megoldás, ahol a fenti futási időn kívül a molekulák körmentesítését is el kellett végeznünk.
31
3.5. A mélységi keresésre és a szélességi keresésre alapuló algoritmusok összehasonlítása
A dolgozatban bemutatott algoritmusok nagy része épít egy adott csúcsot tartalmazó legkisebb kör megkeresésére. Erre a feladatra kétféle módszert is láthattunk:
az első a Zamora által használt mélységi bejárás
a másik pedig a Figueras által alkalmazott szélességi keresés
Az intuíció az, hogy a legtöbb esetben az utóbbi megoldás a hatékonyabb. A gyakorlatban nagy szórást tapasztalhatunk a mélységi bejárás esetén, és viszonylag kiegyensúlyozott teljesítményt a szélességi keresésnél. A 3.7. ábrán látható fullerene vagy buckyball esetén (http://en.wikipedia.org/wiki/Fullerene#Other_buckyballs) Zamora algoritmusa órák alatt sem adott eredményt, míg a Balducci vagy Figueras módszere néhány másodperc alatt megadta a helyes SSSR-t. Ilyen összetett struktúrák esetében a mélységi bejárás tehát nem megfelelő stratégia.
3.7. ábra
32
4. Összefoglalás Az alábbiakban összefoglaljuk munkánk fontosabb eredményeit.
Egzakt matematikai definíciót adtunk az irodalomban sokszor pontatlanul használt fogalmakra.
Tisztáztuk az SSSR halmazzal kapcsolatos félreértéseket, és az eredeti definíció megváltoztatásának okát.
Megvizsgáltunk és implementáltunk egy hatékony algoritmust egy gráf összes elemi körének detektálására.
Megvizsgáltunk és elemeztünk néhány, különböző keresési stratégiára épülő SSSR algoritmust. Az esetleges hiányosságokra és korlátokra bizonyos esetekben sikerült heurisztikus megoldást találnunk, ezeket implementáltuk is.
A gyakorlatban a szélességi bejárásra alapuló SSSR keresési módszerek bizonyultak hatékonyabbnak (és néhány esetben pontatlanabbnak), illetve láthattuk, hogy speciális esetekben a visszalépéses keresés alkalmazása nem járható út.
33
Irodalomjegyzék [1]
Balducci, Renzo – Pearlman, Robert S. : Efficient exact solution of the ring perception problem. J. Chem. Inf. Comput. Sci. 1994, 34, 822-831.
[2]
Berger, Franziska – Flamm, Christoph – Gleiss, Petra M. – Leydold, Josef – Stadler, Peter F. : Counterexamples in Chemical Ring Perception. J. Chem. Inf. Comput. Sci. 2004, 44, 323-331.
[3]
Deo, N. – Prabhu, G. M. – Krishnamoorty, M. S. : Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Software 1982, 8, 26-42.
[4]
Downs, Geoffrey M. – Gillet, Valerie J. – Holliday, John D. – Lynch, Michael F. : Review of ring perception algorithms and development of the Extended Set of Smallest Rings concept. J. Chem. Inf. Comput. Sci. 1989, 29, 172-187.
[5]
Downs, Geoffrey M. – Gillet, Valerie J. – Holliday, John D. – Lynch, Michael F. : Theoretical Aspects of Ring Perception and Development of the Ectended Set of Smallest Rings Concept. J. Chem. Inf. Comput. Sci. 1989, 29, 187-206.
[6]
Fan, T. F. – Panaye, A. – Doucet, J.-P. – Barbu, A. : Ring Perception. A New Algorithm for Directly Finding the Smallest Set of Smallest Rings from a Connection Table. J. Chem. Inf. Comput. Sci. 1993, 33, 657-662.
[7]
Figueras, John : Ring Perception Using Breadth-First Search. J. Chem. Inf. Comput. Sci. 1996, 36, 986-991.
[8]
Hanser, Th. – Jauffret, Ph. – Kaufmann, G. : A New Algorithm for Exhaustive Ring Perception in a Molecular Graph. J. Chem. Inf. Comput. Sci. 1996, 36, 1146-1152.
[9]
Hartvigsen, D. – Mardon, R. : Cycle bases from orderings and coverings. Discr. Math. 1991, 94, 81-94. 34
[10]
Leydold, J. – Stadler, P. F. : Minimal cycle basis of outerplanar graphs. Elec. J. Comb. 1998, 98-01-011.
[11]
Plotkin, M. : Mathematical basis of ring-finding algoritms in CIDS. J. Chem. Doc. 1971, 11, 60-63.
[12]
Shiha, W.-K. – Hsub, W.-L. : A new planarity test. Theor. Comput. Sci. 1999, 223, 179-191.
[13]
Stepanec, G. F. : Basis systems of vector cycles with extremal properties in graphs. Uspekhi Mater. Nauk. 2 1964, 19, 171-175.
[14]
Zamora, Antonio : An Algorithm for Finding the Smallest Set of Smallest Rings. J. Chem. Inf. Comput. Sci. 1976, 16, 40-43.
35
