SMILES

SMILES je jednoduchý textový formát na ruční zadávání grafů do počítače. Původně je vymyšlený pro molekuly, ale koncept jde jednoduše generalizovat na libovolné grafy. Přesný popis a nějaké příklady jsou na wikipedii.

Volně přeloženo, SMILES v chemii popisuje anotovaný graf (a.k.a. molekulu), kde všechny vrcholy (a.k.a atomy) mají jméno (a.k.a. prvek) a všechny hrany (a.k.a. chemické vazby) mají přiřazený typ (např. násobnost).

My budeme pracovat se zjednodušeným SMILES systémem, který popisuje jen obyčejný, chemií nezatížený graf, pouze s anotovanými vrcholy. Anotace vrcholu je string začínající jedním velkým písmenem a pokračující libovolným množstvím malých písmen. Budeme uvažovat jen spojité grafy.

Jednoduché rovné grafy (cesty) se zapisují následovně:

A je graf obsahující jediný vrchol s anotací (jménem) “A”
AA je graf obsahující 2 vrcholy se jmény “A” a “A”, spojené hranou. Graficky asi takhle: (A)—(A)
ABA je graf s jednou cestou na které jsou postupně vrcholy “A”, “B” a “A”: (A)—(B)—(A)
AhojAhoj obsahuje 2 spojené vrcholy anotované “Ahoj”: (Ahoj)—(Ahoj)

Když chcete udělat na grafu odbočku (tj. vyrobit strom), otevřete závorku:

AB(C)D je graf ve kterém je cesta z A, B a D, a na B je ještě navíc připojené C.
Uprostred(Kolem)(Kolem)(Kolem)(Kolem) je graf který má na vrchol se jménem “Uprostřed” připojené 4 vrcholy se jménem “Kolem”.
Závorky jde samozřejmě libovolně zahnizďovat do sebe. Třeba tahle super molekula se zapíše jako HOC(H)(C(H)(H)H)C(H)(H)H (v obrázku na wiki je černě uhlík©, červeně kyslík (O) a bíle vodík (H)).

Graficky: například SMILES АAA(B)(C)(DE(F)G)F popisuje tenhle graf:

          (B)   (C)    (F)
             \ /        |
   (A)--(A)--(A)--(D)--(E)--(G)
              |
             (F)

Když chcete v grafu udělat cyklus (tj. vyrobit kolečko), můžete 2 libovolné molekuly ve vytvářeném stromě spojit pomocí číselné zpětné reference — nějaký vrchol označíte libovolným číslem, a to samé číslo pak můžete použít kdekoliv znova pro vyrobení hrany vedoucí k původnímu vrcholu.

V grafu A1AAA1 je první A označené jedničkou, a poslední A je s ním spojené. Ve výsledku z toho je čtvercový graf s vrcholy označenými A.
Graf K4 se zapíše jako X1X2X1X(1)2
Graf K3,3 se dá zapsat jako X10Y20X11Y21(10)X12(20)Y22(10)11.

Grafický příklad — SMILES A123B(C123)(E)D123 vypadá jako graf takhle:

      (C)
     /   \
   (A)---(B)--(E)
     \   /
      (D)

Zadání

Vyrobte predikát smiles_graph(+SmilesString, -Graf), který ze stringu ve formátu SMILES vyrobí nějaký pěkný, strojově zpracovatelný popis grafu. Pěkný popis je například seznam označení vrcholů a seznam hran s indexy sousedících vrcholů.

Příklad

Na dotaz

?-  smiles_graph("Aaa555BbbCcc555", graph(V,E)).

by prolog mohl odpovědět např. takhle:

V = ['Aaa', 'Bbb', 'Ccc']
E = [edge(0,1), edge(1,2), edge(2,0)]

Ideálně do řešení zahrňte predikát demo, který bude obsahovat nějaký návod, jak vaši formu predikátu správně spustit. V tomhle případě třeba takhle:

demo :-
  smiles_graph("AaAaAa", graph(V,E)),
  write("Vrcholy: "), writeln(V),
  write("Hrany: "), writeln(E).

Na neplatný SMILES vzorec by Prolog měl odpovědět false.

Pomůcky

Můžou se hodit následující věci ze standardní knihovny Prologu:

?- string_chars("aSd('1",X).
X = [a, 'S', d, '(', '\'', '1'].
?- atom_number('1',N).
Y = 1.
?- string_to_list("aSd('1",ASCII).
ASCII = [97, 83, 100, 40, 39, 49].
?- atom_concat(ka,kao,X).
X = kakao.
?- char_type('a', lower).
true.
?- char_type('a', upper).
false.
?- char_type('a', digit).
false.

Parsování SMILES určitě proveďte pomocí prologových gramatik, je to tak nejpohodlnější. Do seznamu cvičení (na hlavní stránce dole) jsem přidal nějakou formálnější definici, příklady přepisování gramatických pravidel na normální, a taky demo s parsováním aritmetiky. (SMILES bude mít podstatně jednodušší parser, ale s vyparsovaným obsahem bude potřeba dělat trochu složitější věci.)

DCG jsou kdyžtak na internetu dokumentované různě systematicky.