Rendezés élszínek és távolságok alapján

Most vegyünk egy másik fajta, szintén lexikografikus jellegű rendezést M96 cikk alapján. A következő lépésekre van szükségünk:

1. Bevezetünk egy sorszámozást, ami minden adott kezdőpontú, összefüggő D-szimbólum csúcsainak sorszámát megadja.
2. Az előbbi sorszámozás alapján veszünk egy távolságot.
3. A csúcsok távolsága alapján veszünk egy rendezést adott kezdőpontú diagramok között.
4. Felsoroljuk az összes lehetséges diagramot növekvő sorrendben.
5. Eközben eldobáljuk a rosszakat.

Algoritmus 3.1   Legyen $(\Sigma_I,\mathcal{D}(D_1))$ egy D-szimbólum diagramja $D_1$ kezdőponttal. Számozzuk meg a csúcsokat $0,1,\ldots ,n$ sorszámokkal. $D_1$ sorszáma 1. Tegyük fel, hogy megsorszámoztuk a $D_1,\ldots,D_r$ csúcsokat. A következő csúcs:

• Vegyük sorban a $\sigma_0(D_r)$ és $\sigma_1(D_r)$ elmeket, az első, amelyiket még nem sorszámoztuk meg, lesz a következő csúcs.
• Ha már sorszámozottak, vegyük sorban $\sigma_0(D_{r-1}),\ldots,\sigma_0(D_1);\sigma_1(D_{r-1}),\ldots, \sigma_1(D_1)$ csúcsokat, az első sorszám nélküli a következő.
• Végül ha még mindig nincs meg a következő, vegyük az első sorszámozatlant a következők közül: $\sigma_2(D_r),\ldots,\sigma_2(D_1); \ldots\ldots; \sigma_d(D_r),\ldots,\sigma_d(D_1)$

A diagram összefüggő, ezért minden csúcsát megsorszámozza az algoritmus.

Bármely két elem távolságát meghatározhatjuk úgy, hogy az egyik elemmel indított sorszámozás szerint a második elemnek a sorszámát vesszük. $D_x$ és $D_y$ távolságának jelölése: $D_xD_y.$

Ez a távolság a következő rendezési algoritmushoz vezet:

Algoritmus 3.2   Legyenek $(\Sigma_I,\mathcal{D}(D_1))$ és $(\Sigma'_{I'},\mathcal{D}'(D_{1'}))$ két D-szimbólum diagramjai, kitüntetett kezdőponttal. Azt mondjuk, hogy $\mathcal{D}<\mathcal{D}'$ a következő tulajdonságok alapján:

1. $\vert I\vert<\vert I'\vert$ (dimenzió)
2. Ha megegyeznek: $\vert\mathcal{D}\vert<\vert\mathcal{D}'\vert$ (D-szimbólum elemszáma)
3. Ha egyenlőség áll: $\mathcal{D}$ és $\mathcal{D}'$ elemeinek távolságait hasonlítjuk össze:
   • $D_1\sigma_d D_1<D_{1'}\sigma_d D_{1'};$ ha egyenlőség áll, $D_2\sigma_d D_2<D_{2'}\sigma_d D_{2'};\ldots;$ ha egyenlőség áll, $D_n\sigma_d D_n<D_{n'}\sigma_d D_{n'}$ ($n-1$ -ig is elég menni;)
   • Egyenlőség esetén: $D_1\sigma_{d-1} D_1<D_{1'}\sigma_{d-1} D_{1'}; \ldots;D_n\sigma_{d-1} D_n<D_{n'}\sigma_{d-1} D_{n'};$

     $$\vdots$$

     
     

   • Egyenlőség esetén: $D_1\sigma_0 D_1<D_{1'}\sigma_0 D_{1'}; \ldots;D_n\sigma_0 D_n<D_{n'}\sigma_0 D_{n'}.$

Ha végig egyenlőség állt, a két diagram izomorf.

Most már meg tudjuk különböztetni a diagramokat, így fel is tudjuk sorolni a különbözőeket:

Algoritmus 3.3   Egy backtrack³ algoritmust használunk a felsorolásra. Minden lépésben megpróbáljuk a soron következő élt kihagyni, majd hozzáadni; és az élek sorának végére érve ellenőrizzük, hogy jó diagramot kaptunk-e. Ha igen, eltároljuk későbbi elemzésre, különben eldobjuk. Az éleket a forrás, a cél és az operáció sorszámával azonosítjuk, ahol a forrás mindig határozottan kisebb, mint a cél, ezzel tudjuk biztosítani az él és az azonosítás közötti egy-egy értelmű hozzárendelést.

Az algoritmus bemenete a $d$ dimenzió és a diagram csúcsainak $n$ száma. Minden állapotban a következő lépéseket tesszük meg:

• Ha a forrás sorszáma egyenlő a csúcsok számával, akkor megnézzük, hogy összefüggő-e a gráf (egyszerű szélességi bejárással, sec:kdim részben kicsit bővebben kifejtve), majd előállítjuk alg:sorsz algoritmus alapján az első csúcsot kezdőpontnak vett sorszámozást. Ha ez nem ugyanaz, mint a backtrack algoritmus által előállított sorszámozás, akkor eldobjuk, mert előállítja a backtrack algoritmus a jó sorszámozást is. Sorban előállítjuk a többi csúcs által generált sorszámozást is, és ha ezek közül bármelyik kisebb diagramot ad, akkor eldobjuk, mert a backtrack algoritmus a kisebbet is előállítja. Végül elkészítjük a diagram alapján az $\mathcal{R}$ mátrix-függvényt, és megvizsgáljuk, hogy a főátlótól legalább $2$ távolságra levő mezőkben 1-es vagy 2-es szerepel-e (csak így lehet az $\mathcal{M}$ mátrix-függvény megfelelő helyein 2-es), ha valamelyikben nem az szerepelne, akkor szintén eldobjuk. Ha idáig eljutottunk, beszúrjuk egy rendezett adatrendszerbe (az előbb definiált rendezés szerint.) Ha már szerepelne a rendszerben, akkor eldobjuk, mert ez azt jelenti, hogy szimmetrikus a diagram, és egyszer már szerepelt.
• Ha a forrás sorszáma kisebb, mint a csúcsok száma, akkor először meghívjuk rekurzívan az eljárást a következő élre. Végül, ha hozzá tudjuk adni a vizsgált élt a rendszerhez, akkor hozzáadjuk, meghívjuk rekurzívan az eljárást ugyanarra az élre, amit vizsgáltunk, majd töröljük a hozzáadott élt.
• Az éleket lexikografikus sorrendben vesszük: első a forrás sorszáma, második az operáció sorszáma és utolsó a cél sorszáma. A forrás és a cél $1$ és $\vert\mathcal{D}\vert=n$ között változik (figyelve, hogy a cél szigorúan nagyobb a forrásnál) és az operáció $I$ -beli.
• Egy apró heurisztikát használunk: ha a forrás csúcsnak nincs éle, akkor nem hívjuk meg a következő forrásra az eljárást él hozzáadás nélkül, mivel így nem lehet összefüggő a diagram.⁴

Lemma 3.4   Az $\vert I\vert$ dimenziós $\vert\mathcal{D}\vert$ elemű D-szimbólumok lehetséges diagramjai rendezetten szerepelnek alg:backtrack algoritmusbeli rendezett adatrendszerben. (De nem tartozik minden diagramhoz D-szimbólum, mert még nem vizsgáltuk meg az $\mathcal{M}$ mátrix-függvényeket.)

Mivel felsoroltuk az összes lehetséges diagramot, és csak az azonosakat, illetve az $\mathcal{R}$ mátrix-függvény alapján rosszakat hagytuk el, ezért az állítás triviális. Az adatrendszert nem részletezzük, mivel egy egyszerű láncolt lista is megteszi egyelőre, amíg nem túl nagy a jó diagramok száma. Legalább 9-10 elemű D-szimbólumok felsorolása esetén viszont már érdemes lenne AVL vagy piros-fekete fában tárolni a lehetséges diagramokat. (Magasabb szintű programozási nyelvekben halmazként.)