====== Cvičení 10: Grafy ======
===== Quick test 1 - data =====
{{ :courses:b3b33alp:cviceni:slovnik.txt | slovnik.txt}}
==== Reprezentace grafu ====
* Graf lze reprezentovat maticí sousednosti, seznamem hran nebo seznamem odchozích hran
* Budeme používat seznam odchozích hran.
{{courses:b3b33alp:cviceni:graph5forbfs0000.png?200|}}
* Pro graf na obrázku bude reprezentace vypadat takto:
* G je proměnná typu dictionary, indexujeme ji jménem (číslem) uzlu, hodnota je pole, které obsahuje seznam uzlů, které jsou dosažitelné
G = {}
G [0] = [1 ,2 ,5]
G [1] = [0 ,2]
G [2] = [0 ,1 ,3]
G [3] = [2]
==== Načtení grafu ze souboru ====
Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány v souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:
* první číslo je číslo uzlu ze kterého vede hrana
* druhé číslo je číslo uzlu do kterého vede tato hrana
Napište program ''path.py'', který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.
Program otestujte na tomto souboru:
1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1
Výsledek pro cestu z uzlu 2 do uzlu 5 je:
2 6 9 5
===== Domácí úkol: Lehká varianta Kobylka (Hive) =====
* Úkolem je napsat program, který určí možné pohyby "kobylky" v hexagonálním hnízdě (inspirováno hrou HIVE).
* **Vstup:**
* Jméno textového souboru na příkazové řádce (''sys.argv[1]'')
* Soubor obsahuje na každé řádce tři celá čísla ''p q v'', kde ''(p, q)'' jsou souřadnice buňky v hexagonálním gridu a ''v'' je její hodnota. Hodnota buňky kóduje následující:
* ''v = 0'': buňka je prázdná,
* ''v = 1'': buňka je obsazená, a
* ''v = 2'': na buňce je umístěna kobylka.
* Vstupní soubor obsahuje definici tzv. hrací desky.
* Je zaručeno, že vstupní soubor existuje a obsahuje validní definici problému.
* Kobylka je na desce pouze jedna.
* **Výstup:**
* Program určí souřadnice všech buněk, kam se kobylka z výchozí pozice může dostat, a vypíše je na standardní výstup.
* Souřadnice jsou vypsány ve formátu ''[ [p1, q1], [p2, q2], ... , [pn, qn] ]'', přičemž platí, že výstup je seřazen vzestupně nejdříve dle ''p'' a následně dle ''q''.
* Pokud se kobylka nikam nemůže dostat, je výstup programu ''[]''
* **Odevzdání:** program **grasshopper.py** nahrajte do Brute, úloha HW09.
* **Pohyb kobylky**
* Z výchozí pozice se kobylka může pohnout na nejbližší neobsazené místo ve všech šesti směrech a musí platit, že mezi aktuální pozicí a novou pozicí musí být alespoň jedna obsazená buňka.
* Kobylka se nesmí pohnout, pokud by při jejím skoku došlo k rozpojení hnízda - všechny neprázdé buňky (hnízdo) tvoří jednu [[ https://en.wikipedia.org/wiki/Component_(graph_theory) | komponentu souvislosti]].
==== Tipy ====
* Pro správný výpis řešení doporučujeme uložit výsledek (tj. seznam buňek, kam se kobylka může dostat) do pole, přičemž každá buňka bude souřadnice '' [p, q]''.
* Je potřeba zajistit, aby kobylka neskákala mimo herní desku.
* Pole seřadíme a vypíšeme takto:
solution = [ [1, 2], [1, -1], [-1, 4] ] # priklad reseni
solution.sort()
print(solution) # takto vypsane reseni bude akceptovano Brutem
* Informace k práci s [[ https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/faq/hexagrid | hexagonálním gridem]].
==== Příklad 1 ====
* Modře jsou obsazené buňky, červeně je výchozí pozice kobylky, zeleně jsou místa, kam se kobylka může dostat.
* Výstupem vašich programů bude seznam zelených buněk.
Vstup:
/** 1228 **/
-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 1
3 4 1
3 5 2
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 1
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0
Výstup:
[[3, 2], [3, 7], [5, 3], [5, 5]]
Komentář: z výchozí pozice (červeně) je možné doskočit na čtyři zelené pozice.
{{ :courses:b3b33alp:cviceni:hive-gh-1228.png?400 |}}
==== Příklad 2 ====
Vstup:
/** 3320 **/
-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 1
0 7 1
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 0
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 0
2 8 0
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 0
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 1
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 1
6 3 1
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 1
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0
Výstup:
[]
Komentář: kobylka nemůže nikam skočit, neboť by došlo k rozpojení hnízda na dvě oddělené části:
{{ :courses:b3b33alp:cviceni:hive-gh-3320.png?400 |}}
==== Příklad 3 ====
Vstup:
/** 3788 **/
-2 4 0
-1 2 1
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 2
0 4 0
1 0 0
1 1 0
1 2 1
1 3 1
1 4 1
2 0 0
2 1 0
2 2 0
2 3 1
2 4 0
3 0 0
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0
Výstup:
[[0, 1], [2, 1], [3, 3]]
Komentář: kobylka (výchozí pozice je červeně) může skočit na tři zelené buňky:
{{ :courses:b3b33alp:cviceni:hive-gh-3788.png?400 |}}
===== Domácí úloha, Těžká varianta: Mravenec (Hive) =====
* Úkolem je napsat program, který určí možné pohyby "mravence" kolem hnízda, přičemž se jedná o pohyb na hexagonální mřížce (inspirováno hrou HIVE).
* **Vstup:**
* Jméno textového souboru na příkazové řádce (''sys.argv[1]'')
* Soubor obsahuje na každé řádce tři celá čísla ''p q v'', kde ''(p, q)'' jsou souřadnice buňky v hexagonálním gridu a ''v'' je její hodnota. Hodnota buňky kóduje následující:
* ''v = 0'': buňka je prázdná,
* ''v = 1'': buňka je obsazená, a
* ''v = 2'': na buňce je umístěn mravenec.
* Vstupní soubor obsahuje definici tzv. hrací desky.
* Je zaručeno, že vstupní soubor existuje a obsahuje validní definici problému.
* Mravenec je na desce pouze jeden.
* **Výstup:**
* Program určí souřadnice všech buněk, kam se mravenec z výchozí pozice může dostat, a vypíše je na standardní výstup
* Souřadnice jsou vypsány ve formátu ''[ [p1, q1], [p2, q2], ... , [pn, qn] ]'', přičemž platí, že výstup je seřazen vzestupně nejdříve dle ''p'' a následně dle ''q''.
* Pokud se mravenec nemůže nikam pohnout, je výsledek ''[]''
* **Odevzdání:** program **ant.py** nahrajte do Brute, úloha HW09.
* **Pohyb mravence**
* Mravenec se smí pohybovat podél hnízda o jedno či více navazujících polí najednou, avšak platí, že pohyb musí splňovat pravidla níže.
* Mravenec se může pohybovat jen po volných buňkách.
* Mravenec se vždy musí dotýkat nějakého souseda.
* Mravenec se nemůže pohnout místami, kudy se hexagonální buňka mravence nevejde (fyzicky):
* Mravenec se nemůže posunout skrze úzkou mezeru (viz. Příklad 2).
* Mravenec se nemůže pohybovat na krajích hrací desky (vně desky lze chápat jako překážky).
* Mravenec může vykonávat pouze pohyb dopředu a nemůže se vracet.
* Pohyb mravence je vykonán tzv. posunem, tj., do neobsazeného souseda ''[ps, qs]'' se může dostat z aktuální pozice ''[pa, qa]'' pouze pokud buňky ''[ps, qs]'' a ''[pa, qa]'' sdílí ještě jednoho volného souseda.
* Mravenec může opustit svoji pozici pouze pokud všechny neprázdé buňky (hnízdo) tvoří jednu [[https://en.wikipedia.org/wiki/Component_(graph_theory) | komponentu souvislosti]].
=== Příklady pohybu mravence ===
* Modře jsou obsazené buňky, červeně je výchozí pozice mravence, zeleně jsou místa, kam se mravenec může dostat
* Výstupem vašich programů bude seznam zelených buněk
* Zde se mravenec nemůže pohybovat, neboť by došlo k rozpojení hnízda (vznikly by dvě komponenty souvislosti)
{{ :courses:b3b33alp:cviceni:hive-ant1.png?400 |}}
* Mravenec může navštívit dva sousedy (buňku (-2,4) nelze navštívit posunem)
{{ :courses:b3b33alp:cviceni:hive-ant2.png?400 |}}
* Mravenec může navšívit většinu hnízda, ale nemůže se posunou skrz buňḱy (7,5) a (3,9)
{{ :courses:b3b33alp:cviceni:hive-ant3.png?400 |}}
* Z výchozí pozice (2,4) se nelze nikam dostat
{{ :courses:b3b33alp:cviceni:hive-ant4.png?400 |}}
* Zde lze navštívit celé hnízdo
{{ :courses:b3b33alp:cviceni:hive-ant5.png?400 |}}
==== Tipy ====
* Pro správný výpis řešení doporučujeme uložit výsledek (tj. seznam buňek, kam se mravenec může dostat) do pole, přičemž každá buňka bude souřadnice '' [p, q]''.
* Je potřeba zajistit, aby se mravenec neposunul mimo herní desku.
* Pole seřadíme a vypíšeme takto:
solution = [ [1, 2], [1, -1], [-1, 4] ] # priklad reseni
solution.sort()
print(solution) # takto vypsane reseni bude akceptovano Brutem
* Informace k práci s [[ https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/faq/hexagrid | hexagonálním gridem]].
==== Příklad 1 ====
Vstup:
/** 1801 **/
-2 4 0
-1 2 0
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 0
0 4 1
1 0 0
1 1 1
1 2 1
1 3 1
1 4 1
2 0 2
2 1 1
2 2 1
2 3 1
2 4 1
3 0 1
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0
Výstup:
[]
Komentář: mravenec se posunem nemůže nikam dostat
{{ :courses:b3b33alp:cviceni:hive-ant-1801.png?400 |}}
==== Příklad 2 ====
Vstup:
/** 2017 **/
-7 14 0
-6 12 0
-6 13 0
-6 14 0
-5 10 0
-5 11 0
-5 12 0
-5 13 0
-5 14 0
-4 8 0
-4 9 0
-4 10 0
-4 11 0
-4 12 0
-4 13 0
-4 14 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-3 10 0
-3 11 0
-3 12 0
-3 13 0
-3 14 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-2 10 0
-2 11 0
-2 12 0
-2 13 0
-2 14 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
-1 10 0
-1 11 0
-1 12 0
-1 13 0
-1 14 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
0 10 0
0 11 0
0 12 0
0 13 0
0 14 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
1 11 0
1 12 0
1 13 0
1 14 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 0
2 8 0
2 9 0
2 10 0
2 11 0
2 12 0
2 13 0
2 14 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 0
3 5 0
3 6 0
3 7 1
3 8 1
3 9 0
3 10 0
3 11 0
3 12 0
3 13 0
3 14 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 0
4 5 0
4 6 1
4 7 0
4 8 1
4 9 1
4 10 0
4 11 0
4 12 0
4 13 0
4 14 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 1
5 7 0
5 8 1
5 9 0
5 10 0
5 11 0
5 12 0
5 13 0
5 14 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 1
6 6 0
6 7 1
6 8 0
6 9 0
6 10 0
6 11 0
6 12 0
6 13 0
6 14 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
7 6 2
7 7 0
7 8 0
7 9 0
7 10 0
7 11 0
7 12 0
7 13 0
7 14 0
8 0 0
8 1 0
8 2 0
8 3 0
8 4 0
8 5 0
8 6 0
8 7 0
8 8 0
8 9 0
8 10 0
8 11 0
8 12 0
8 13 0
9 0 0
9 1 0
9 2 0
9 3 0
9 4 0
9 5 0
9 6 0
9 7 0
9 8 0
9 9 0
9 10 0
9 11 0
10 0 0
10 1 0
10 2 0
10 3 0
10 4 0
10 5 0
10 6 0
10 7 0
10 8 0
10 9 0
11 0 0
11 1 0
11 2 0
11 3 0
11 4 0
11 5 0
11 6 0
11 7 0
12 0 0
12 1 0
12 2 0
12 3 0
12 4 0
12 5 0
13 0 0
13 1 0
13 2 0
13 3 0
14 0 0
14 1 0
Výstup:
[[2, 7], [2, 8], [2, 9], [3, 6], [3, 9], [3, 10], [4, 5], [4, 10], [5, 5], [5, 9], [6, 4], [6, 6], [6, 8], [7, 4], [7, 5], [7, 7]]
Komentář: Mravenec může navštívit následující místa (všimněte si, že do středu hnízda se nedá posunem dostat)
{{ :courses:b3b33alp:cviceni:hive-ant-2017.png?400 |}}
==== Příklad 3 ====
Vstup:
/** 2383 **/
-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 1
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 1
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 1
0 9 1
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 1
4 3 1
4 4 0
4 5 0
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0
Výstup:
[[-2, 5], [-1, 5], [0, 5], [0, 6], [0, 7], [1, 7], [2, 4], [2, 5], [2, 9], [3, 2], [3, 3], [3, 7], [3, 8], [4, 1], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3]]
Komentář: Mravenec může navštívit následující místa
{{ :courses:b3b33alp:cviceni:hive-ant-2383.png?400 |}}