# ADS B - Abeceda

## Rozbor
Abeceda je lineární uspořádání, takže se jednotlivá písmena dají převést na vrcholy maximálního DAGu (tzn. z $A$ vede hrana do $B,C...$, z $B$ do $C...$ atd.)
Pokud by každá kniha měla jen jedno písmeno, pak lze úlohu vyřešit následujícím způsobem:

$A1$
$1.$ Procházím postupně všechny knihy; neexistuje-li ještě dané písmeno, přidám jej do např.pole
$2.$ Zavedu všechny hrany z dosavadních písmen do nového
$3.$ Výsledek:

- existuje-li smyčka, pak jsou knihy se stejným počátečním písmenem za sebou

- existuje-li cyklus, pak knihy nemohou být v abecedním pořadí

- není-li žádný cyklus, pak knihy mohou být v abecedním pořadí

Správnost algoritmu vychází z toho, že se prvky v poli/množině vyskytují jen jednou; směřuje-li hrana z $b$ do dřívějšího prvku $a$ pak to znamená, že prvek $b$ se nachází v abecedě před prvkem $a$, jenže v některém předchozím kroku jsem již předpokládal, že prvek $a$ je před prvkem $b$, což je spor.

U jednopísmenných názvů se dá tak zjistit pořadí všech písmen, která se v názvech knih vyskytují (pokud neexistuje cyklus). U vícepísmenných názvů toto nemusí být úplně jednoznačné, jak je vidět z následujícího algoritmu:

$1.$ $A1$
$2.$ Existuje-li smyčka, proveď $A1$ na všechny knihy začínající tímto písmenem (nazvěme výsledek podgraf $H$), a pokračuj na další smyčku
$3.$ Zjisti, zdali hrany v $H$ jsou totožné s hranami v $G$ obsahující pouze tyto vrcholy.
$4.$ Pokračuj rekurzivně, dokud jsou v $H$ nějaké smyčky.

3.krok opět může skončit chybou, pokud dané vrcholy existují v $G$, ale podgraf tvořenými těmito vrcholy obsahuje jiné hrany. Může však nastat i jiná situace, a to, když daný vrchol není v $G$. Pak je potřeba zjistit jeho "těsné sousedy" a zkoumat, zdali se tito v grafu nachází. Pokud ano, pak lze pořadí opět aktualizovat.
Např. znám-li vrcholy $u,v$ a objevím-li sekvenci $u,x,g,v$, pak mohu tvrdit, že abeceda je v pořadí $u,x,g,v$.
Pokud však v dané hloubce není levý nebo pravý hraniční vrchol v prvotní abecedě, pak se mohu jen domýšlet. Pokud bych znal pouze pořadí $u,x,g$, pak vím, že daná písmena leží za $u$, ale nic více. To mi naštěstí nebrání v tom, zavést toto pořadí do výsledného grafu. Jakmile totiž později zjistím druhou hranici (např. $x,v$), budu již znát výsledné pořadí.
Tedy oprava výsledku: abeceda je jednoznačná v případě, že existuje jednoznačné topologické uspořádání.

Jelikož by smyčky a částečné grafy byly nepřehledné, vytvořím si graf, do kterého budu zapisovat jen jednoznačnosti.
Tento postup může být poněkud zdlouhavý, například v případě knih "Aaaaaa" a "Aaaaab".Také závisí na délce slov. Například pokud by knihy pokrývaly celou abecedu a "nadbytečné" knihy by se lišily až $z$-tým písmenem, pak by složitost byla řádově $k+z(k-n)$. Samozřejmě mohu předpokládat, že $z$ je konstanta

## Celkový algoritmus:

$1.$ Mám prázdný graf o $n$ vrcholech (pro zjednodušení budu předpokládat, že znaky písmen známe) a jména knih (slova) ve frontě a jednu prázdnou frontu (budu je střídat, šla by i cyklická fronta). Ukazatel $z$ na písmeno je roven $0$
$2.$ $z = z+1$;
$3.$ Nastavím proměnou $p$ na žádnou.
$4.$ zjistím $z$-té písmeno ve slově, označím $t$ a porovnám ho s písmenem v následujícím slově $q$ (jsem-li na konci, pak neporovnávám)
$5a.$ Shoduje-li se alespoň s jedním, pošlu slovo na konec fronty.
$5b.$ Pokud $t$ neexistuje (krátké slovo) nebo se liší od písmen v předchozím i následujícím slově, vyhodím slovo pryč z fronty.
$6.$ Je-li $t\neq q$, pak přidám hranu $t\to q$. Obdobně $p \to t$.
$7.$ $p = t$.
$7.$ Jakmile je fronta prázdná, vyměním prvky ve frontách a jdu na $2$.
$8.$ Jakmile jsou obě fronty prázdné, pokusím se o nalezení topologického uspořádání grafu. Existuje-li alespoň jedno, pak tato knihovna může být uspořádána podle abecedy (permutací může být tolik, kolik je těchto uspořádání).

Výstupem tak může být graf s cyklem, graf s více zdroji, nebo nesouvislý graf.
Důležité je, že abeceda bude jednoznačná, pokud je podgrafem na všech vrcholech orientovaná cesta. Ostatní hrany, pokud nebudou tvořit cyklus, jsou tak přebytečné.

Složitost - časová: závisí na celkovém počtu znaků, z kterých se skládají jména všech knih, přičemž každý znak je potřeba projít nejhůře jednou.

Složitost - prostorová: v grafu je potřeba tolik paměti, kolik je znaků v abecedě, a počet hran mezi nimi (což je O(n^2)).