Letný semester, prednáška č. 6

Oznamy

• Počas najbližších cvičení, čiže v stredu 23. marca od 13:10 do 14:40 bude prebiehať druhý test. Bude pozostávať z troch úloh zameraných na látku z prvých piatich týždňov, s dôrazom na látku zo štvrtého a piateho týždňa. Po dobu riešenia testu je potrebná účasť na cvičeniach.
• Druhú bonusovú úlohu je potrebné odovzdať do stredy 23. marca, 13:10 (čiže do začiatku stredajších cvičení).
• Druhú domácu úlohu je potrebné odovzdať do stredy 30. marca, 13:10 (čiže do začiatku siedmych cvičení).

Tvorba dokumentácie: Javadoc

Systém Javadoc umožňuje automatické generovanie dokumentácie k balíku, triede a pod. v štandardnom formáte, aký používa aj dokumentácia k Java API. Program javadoc je štandardnou súčasťou Javy a možno ho nájsť v rovnakom priečinku ako kompilátor javac a interpreter java. Javadoc dokumentáciu generuje na základe komentárov pri jednotlivých triedach, metódach, premenných, atď. Tieto komentáre musia byť v nasledujúcom špeciálnom formáte:

• Komentár musí byť ohraničený značkami /** a */ (na začiatku sú teda dve hviezdičky namiesto bežnej jednej) a každý riadok komentára sa tiež musí začínať hviezdičkou.
• Obsahom komentára je HTML kód – napr. rôzne špeciálne symboly tak vkladáme rovnako ako v HTML – často však ide len o „obyčajný” text.
• Musí byť umiestnený bezprostredne pred triedou, metódou a pod., ku ktorej sa vzťahuje.
• Časť textu komentára končiaca prvou bodkou sa považuje za stručné zhrnutie, ktoré sa uvádza aj v prehľadoch metód, tried, atď.; v samotnej dokumentácii danej triedy resp. metódy sa potom uvádza kompletný text komentára.
• Ako súčasť Javadoc komentára možno (nepovinne) použiť niekoľko špecializovaných značiek – napríklad @param pre opis parametra metódy, @return pre opis výstupu metódy, @throws pre opis vyhadzovaných výnimiek, atď.

Príklad:

/**
 * Trieda obsahujuca velmi dolezite a zmysluplne metody na pracu s celymi cislami. Napriklad druhu mocninu a v buducich
 * verziach mozno aj scitanie.
 */
public class Trieda {

    /**
     * Metoda pocitacuja druhu mocninu celociselneho vstupneho parametra. Vypocet je implementovany prenasobenim
     * vstupneho cisla so sebou samym.
     *
     * @param n Celociselny vstup.
     * @return  Druha mocnina cisla n.
     */
    public int sqr(int n) {
        return n * n;
    }

    /**
     * Metoda na scitanie dvojice celociselnych vstupov. Je implementovana ako vyhodenie vynimky typu Exception.
     *
     * @param n Prvy vstupny parameter.
     * @param m Druhy vstupny parameter.
     * @return  Nepodstatne...
     * @throws Exception V pripade nespravneho pouzitia vyhodi vynimku typu Exception.
     */
    public int add(int n, int m) throws Exception {
        throw new Exception();
    }

}

Pre triedu alebo balík tried s komentármi vo formáte Javadoc možno pomocou programu javadoc vygenerovať samotnú dokumentáciu vo formáte HTML.

• Z príkazového riadku sa tak dá urobiť volaním programu javadoc s vhodnými parametrami (treba sa nastaviť do adresára obsahujúceho priečinok s daným balíkom resp. danú triedu):

javadoc balik
javadoc Trieda.java

Toto volanie programu javadoc často vygeneruje pomerne veľké množstvo súborov. Je preto užitočné nastaviť priečinok, do ktorého sa má dokumentácia vygenerovať, pomocou možnosti -d.

javadoc -d doc balik
javadoc -d doc Trieda.java

• Z IntelliJ cez Tools --> Generate JavaDoc...

Pri východzích nastaveniach sa dokumentácia vytvára iba pre položky s modifikátorom prístupu public alebo protected, pretože predovšetkým tieto tvoria API pre ostatné triedy. V prípade potreby možno toto správanie zmeniť:

• Z príkazového riadku použitím jedného z prepínačov -private, -package, -protected (ekvivalentné nepoužitiu žiadneho prepínača), alebo -public. V takom prípade sa dokumentácia vygeneruje ku všetkým položkám s príslušným alebo „verejnejším” modifikátorom prístupu.
• V IntelliJ možno tieto nastavenia meniť v dialógovom okne, ktoré sa zobrazí pred vygenerovaním dokumentácie.

Testovanie programov

Pod testovaním sa rozumie systematický spôsob hľadania chýb v programe spočívajúci vo vytvorení niekoľkých testov pozostávajúcich zo vstupov a očakávaných výstupov na týchto vstupoch; program je následne (podobne ako na testovači) spustený na každom zo vstupov a jeho výstupy sú konfrontované s očakávanými.

• Cieľom testovania je teda preukázať, že program nepracuje podľa špecifikácie (aby sme potom vedeli chybu nájsť a opraviť).
• Ak program prejde všetkými testmi, nejde v žiadnom prípade o dôkaz toho, že program pracuje správne. Dokázať správnosť programu možno iba pomocou metód formálnej verifikácie, ktoré značne presahujú rámec tohto predmetu (a pre ich výpočtovú náročnosť sa v súčasnosti uplatňujú zvyčajne iba pri tvorbe kritických aplikácií).
• Už aj dobre navrhnutými testmi ale možno početnosť chýb podstatne znížiť.

Typický proces testovania programu alebo jeho časti možno zhrnúť nasledovne:

• Vytvorí sa niekoľko testov pozostávajúcich zo vstupu, očakávaného správneho výstupu a obyčajne aj opisu daného testu (aby bolo jasné, čo sa chce daným testom preveriť).
• Program (resp. napríklad testovaná metóda) sa pre každý z testov spustí na príslušnom vstupe a takto získaný výstup sa porovná s očakávanou odpoveďou.
• Tradičný prístup: najprv sa napíše kód, potom sa vytvárajú testy.
• Test-driven development: najprv sa napíšu testy a až následne sa programuje kód, ktorý ich dokáže splniť.

„White-box” testovanie

Pod „white-box” testovaním sa rozumie prístup, pri ktorom sa testy vytvárajú na základe kódu; cieľom je pritom preveriť všetky významné vetvy výpočtu.

• Pri cykloch napríklad možno preveriť prípady, keď sa vykoná 0 iterácií, 1 iterácia, 2 iterácie, nejaký väčší pevný počet iterácií a prípadne maximálny počet iterácií (ak niečo také dáva zmysel).
• Pri podmienkach sa preverí ako prípad, keď je táto podmienka splnená, tak aj prípad, keď je nesplnená.
• ...

Nevýhodou tohto prístupu je, že sústredením sa na kód môžeme pozabudnúť na prípady, na ktoré sa v kóde nemyslelo. Napríklad nasledujúca metóda úplne nespĺňa svoju špecifikáciu:

import java.util.*;

public class Trieda {

    /**
     * Metoda pocitajuca pocet retazcov vo vstupnom zozname retazcov, ktore obsahuju dany podretazec. Vstupny 
     * zoznam aj hladany podretazec musia byt rozne od null. Vstupny zoznam ostane po vykonani metody nezmeneny.
     *
     * @param list      Vstupny zoznam retazcov, ktorym moze byt lubovolna instancia typu List<String>.
     * @param substring Podretazec, ktoreho vyskyty v retazcoch sa pocitaju.
     * @return          Pocet retazcov zo zoznamu list, ktore obsahuju podretazec substring.
     * @throws IllegalArgumentException V pripade, ze je niektory z argumentov rovny null, vznikne vynimka typu
     * IllegalArgumentException.
     */
    public static int numberOfSubstringContainingStrings(List<String> list, String substring) {
        if (list == null || substring == null) {
            throw new IllegalArgumentException();
        }
        int count = 0;
        for (String s : list) {
            if (s.contains(substring)) {
                count++;
            }
        }
        return count;
    }

}

„Black-box” testovanie

Pod „black-box” testovaním sa naopak rozumie prístup, pri ktorom sa sada testov vytvorí len na základe špecifikácie programu. V testoch sa pritom snažíme zachytiť okrajové aj typické prípady.

Uvažujme napríklad neformálnu špecifikáciu metódy remove rovnakú ako vyššie:

    /**
     * Metoda pocitajuca pocet retazcov vo vstupnom zozname retazcov, ktore obsahuju dany podretazec. Vstupny 
     * zoznam aj hladany podretazec musia byt rozne od null. Vstupny zoznam ostane po vykonani metody nezmeneny.
     * 
     * @param list      Vstupny zoznam retazcov, ktorym moze byt lubovolna instancia typu List<String>.
     * @param substring Podretazec, ktoreho vyskyty v retazcoch sa pocitaju.
     * @return          Pocet retazcov zo zoznamu list, ktore obsahuju podretazec substring.
     * @throws IllegalArgumentException V pripade, ze je niektory z argumentov rovny null, vznikne vynimka typu
     * IllegalArgumentException.
     */
    public static int numberOfSubstringContainingStrings(List<String> list, String substring) {
        // ...
    }

K nej môžeme zhotoviť napríklad nasledujúcu sadu testovacích vstupov:

1. Prázdny zoznam list, ľubovoľný reťazec substring.
2. Jednoprvkový zoznam list obsahujúci iba reťazec rovný reťazcu substring.
3. Jednoprvkový zoznam list, ktorého jediný reťazec neobsahuje podreťazec substring.
4. Dlhší zoznam obsahujúci niekoľko reťazcov s výskytmi podreťazca substring a niekoľko reťazcov bez výskytu tohto podreťazca. Medzi reťazcami zoznamu obsahujúcimi podreťazec substring by mali byť také, ktoré tento podreťazec obsahujú na začiatku, v strede, na konci a viackrát.
5. Reťazec substring prázdny, zoznam list ľubovoľný.
6. Reťazec substring rovný null, zoznam list ľubovoľný.
7. Zoznam list rovný null, reťazec substring ľubovoľný.
8. Zoznam obsahujúci prázdne reťazce, reťazec substring ľubovoľný.
9. Zoznam obsahujúci výskyty null, reťazec substring ľubovoľný.
10. Veľmi dlhý zoznam náhodne vygenerovaných reťazcov, reťazec substring ľubovoľný.
11. Zoznam veľmi dlhých náhodne vygenerovaných reťazcov, dlhý náhodne vygenerovaný reťazec substring.
12. ...

Popri tom je žiadúce v rôznych testoch použiť zoznamy rôznych typov, napr. aspoň ArrayList, LinkedList a nemodifikovateľný zoznam.

JUnit

Systém JUnit umožňuje vytvárať špeciálne triedy obsahujúce testy iných tried.

• Sadu testov možno ľahko automaticky spustiť a vyhodnotiť ich výsledky.
• Podporované väčšinou IDE pre Javu.

JUnit nie je priamo súčasťou Javy, ale jeho verziu JUnit 4 možno nájsť napríklad aj v typickej inštalácii IntelliJ. Prostredie IntelliJ má aj dobrú podporu najnovšej verzie JUnit 5, tú je ale potrebné stiahnuť pomocou nástroja Maven. V nasledujúcom používame (stále hojne rozšírenú) verziu JUnit 4. O použití JUnit z príkazového riadku sa možno dočítať napríklad tu.

• Dokumentácia k JUnit.

V prostredí IntelliJ je pred prácou s JUnit potrebné vykonať nasledujúce úkony:

• Cez File --> Project Structure... -> Libraries -> + -> Java pridať do projektu ako knižnicu balík junit4.jar, ktorý by mal byť umiestnený v podpriečinku lib koreňového priečinka inštalácie IntelliJ.
• Vytvoriť nový priečinok (napríklad tests) na rovnakej úrovni ako src. Tento adresár je následne potrebné označiť ako koreňový pre testy pomocou možnosti Mark Directory as --> Test Sources Root z kontextovej ponuky, ktorá sa zjaví po kliknutí na adresár pravou myšou.

Samotný test pre triedu Trieda potom vytvoríme takto:

• V zdrojovom kóde klikneme na názov triedy Trieda a použijeme klávesovú skratku Alt+Enter.
• Zvolíme možnosť Create Test.
• V dialógovom okne vyberieme verziu JUnit 4 a ako názov triedy zvolíme napríklad TriedaTest.
• Po potvrdení vznikne nová trieda TriedaTest.java, ktorá bude namiesto pod priečinkom src umiestnená pod priečinkom tests.
• (Alternatívne možno namiesto predchádzajúcich štyroch krokov jednoducho vytvoriť novú triedu pod priečinkom tests.)
• Vo vytvorenej triede môžeme napísať niekoľko testov podobných ako v ukážke nižšie.
• Po spustení triedy TriedaTest sa spustia všetky testy a v okne Run sa zobrazia ich výsledky.

Príklad niekoľkých testov pre metódu numberOfSubstringContainingStrings opísanú vyššie (statický import statických metód z triedy – pri použití * ide o všetky takéto metódy – znamená, že sa tieto metódy budú dať volať iba ich názvom, bez potreby uvedenia názvu triedy):

import org.junit.*;
import static org.junit.Assert.*;
import java.util.*;

public class TriedaTest {

    @Test
    public void testEmpty() {
        List<String> list = new ArrayList<>();
        String substring = "retazec";

        int expectedResult = 0;
        List<String> expectedList = new ArrayList<>();

        int result = Trieda.numberOfSubstringContainingStrings(list, substring);

        assertEquals(result, expectedResult);
        assertTrue(expectedList.equals(list));  // To iste sa da napisat aj cez assertEquals.
    }

    @Test
    public void testSubstringOnly() {
        List<String> list = new LinkedList<>();
        list.add("retazec");
        String substring = "retazec";

        int expectedResult = 1;
        List<String> expectedList = new LinkedList<>(list);

        int result = Trieda.numberOfSubstringContainingStrings(list, substring);

        assertEquals(result, expectedResult);
        assertTrue(list.equals(expectedList));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testSubstringNull() {
        List<String> list = new ArrayList<>();
        list.add("retazec1");
        list.add("retazec2");
        String substring = null;

        Trieda.numberOfSubstringContainingStrings(list, substring);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testListNull() {
        List<String> list = null;
        String substring = "retazec";

        Trieda.numberOfSubstringContainingStrings(list, substring);
    }

    @Test
    public void testListContainsNull() {
        List<String> list = new LinkedList<>();
        list.add("retazec1");
        list.add(null);
        list.add("retazec2");
        list.add("cokolvek");
        list.add(null); 
        String substring = "retazec";

        int expectedResult = 2;
        List<String> expectedList = new LinkedList<>(list);

        int result = Trieda.numberOfSubstringContainingStrings(list, substring);

        assertEquals(result, expectedResult);
        assertTrue(list.equals(expectedList));
    }

}

Tento príklad je možné rôzne vylepšovať:

• Opakujúce sa časti kódu môžeme dať do pomocných metód.
• Môžeme v triede TriedaTest definovať premenné, konštruktor, ako aj špeciálne metódy, ktoré sa vykonajú pred každým testom, prípadne po každom teste.
• ...

Grafy: úvod

Počas nasledujúcich niekoľkých týždňov sa budeme venovať práci s grafmi a implementácii jednoduchých grafových algoritmov.

• Na tomto predmete nebudeme grafy definovať matematicky – to je náplň predmetu „Úvod do kombinatoriky a teórie grafov”. Namiesto toho si vystačíme s intuitívnym chápaním vysvetleným nižšie.
• Viac sa o grafových algoritmoch možno dočítať napríklad v nasledujúcej literatúre, ktorá svojím záberom prudko presahuje rámec tohto predmetu:
  • R. Sedgewick, K. Wayne: Algorithms, 4th ed. Upper Saddle River : Addison-Wesley, 2011. (Grafmi sa zaoberá štvrtá kapitola, používa sa Java.)
  • J. Demel: Grafy a jejich aplikace. Praha : Academia, 2002. (Algoritmy opisované pomocou prirodzeného/matematického jazyka.)
  • T. H. Cormen et al. Introduction to Algorithms, 3rd ed. Cambridge, Massachusetts : MIT Press, 2009. (Algoritmy opisované pomocou pseudokódu.)
• Ďalšie predmety, na ktorých sa robí s grafmi:
  • „Tvorba efektívnych algoritmov” (pokročilejšie grafové algoritmy).
  • „Teória grafov” (teoretické aspekty grafov, niektoré grafové algoritmy).
  • „Neštruktúrované rozpravy o štruktúrach: kapitoly z matematiky pre informatikov (1)” (prevažne súvis grafov s maticami).

Orientované a neorientované grafy

Orientovaný graf (angl. directed graph) je daný:

• Konečnou množinou vrcholov (na tomto predmete zvyčajne {0,1,...,n-1} pre nejaké kladné prirodzené číslo n).
• Množinou hrán medzi vrcholmi: z každého vrcholu grafu môže do každého vrcholu viesť najviac jedna orientovaná hrana.

Vrcholy (angl. vertices) znázorňujeme bodmi resp. krúžkami, orientované hrany (angl. edges) šípkami. Nezaujímajú nás pritom geometrické vlastnosti diagramu grafu, ale iba to, či dané vrcholy sú alebo nie sú spojené hranou. Špeciálnym prípadom hrany je tzv. slučka – hrana s rovnakým počiatočným a koncovým vrcholom. Príklad diagramu orientovaného grafu je na obrázku nižšie.

V neorientovanom grafe (angl. undirected graph) nerozlišujeme orientáciu hrán; hrany tak namiesto šípok kreslíme „obyčajnými čiarami”. Medzi každou neusporiadanou dvojicou vrcholov pritom môže viesť najviac jedna neorientovaná hrana a v každom vrchole môže graf obsahovať najviac jednu slučku. Príklad diagramu neorientovaného grafu je na obrázku nižšie.

Neorientovaný graf budeme pre účely tohto predmetu stotožňovať s orientovaným grafom, v ktorom existencia hrany z vrcholu u do vrcholu v implikuje existenciu hrany z v do u – jedna neorientovaná hrana rôzna od slučky tak zodpovedá dvom protichodným orientovaným hranám a neorientovaná slučka zodpovedá orientovanej slučke. To znamená, že neorientované grafy budeme chápať ako špeciálny prípad orientovaných grafov.

Pod grafom (bez ďalšieho prívlastku) budeme mať – na rozdiel od väčšiny odborníkov na teóriu grafov – obyčajne na mysli orientovaný graf.

Dôležité pojmy:

• Následník vrcholu u v grafe G je ľubovoľný vrchol v taký, že v G vedie hrana z vrcholu u do vrcholu v.
• Predchodca vrcholu u v grafe G je ľubovoľný vrchol v taký, že u je v grafe G následníkom v.
• Sused vrcholu u je ľubovoľný vrchol v, ktorý je následníkom alebo predchodcom vrcholu u.
• V neorientovaných grafoch sú množiny následníkov, predchodcov a susedov každého vrcholu totožné. Hovoríme tak typicky iba o susedoch.

Vybrané aplikácie grafov

• Grafy cestnej (resp. železničnej, leteckej, elektrickej, potrubnej, počítačovej...) siete.
• Modely zložitých sietí (napr. internet, interakcie proteínov, ľudský mozog...).
• Grafy molekúl (vrcholmi sú atómy a hranami väzby medzi nimi).
• Časové závislosti medzi činnosťami (ak činnosť u treba vykonať pred činnosťou v, vedie z u do v orientovaná hrana).
• Preferencie (napríklad pri tvorbe rozvrhov môžu byť hranami pospájané predmety s časmi, v ktorých sa musia vyučovať).
• Všeobecnejšie možno grafom zadať akúkoľvek konečnú binárnu reláciu.
• Niektoré modely výpočtov (booleovské obvody, konečné automaty...).
• Každý strom je súčasne aj grafom...
• ...

Reprezentácia grafov

Na dnešnej prednáške sa budeme zaoberať orientovanými a neorientovanými grafmi na množine vrcholov {0,1,...,n-1} pre kladné prirodzené n. Najužitočnejšími spôsobmi reprezentácie grafu v pamäti počítača sú nasledujúce dva:

Matica susednosti (angl. adjacency matrix)

• Hrany grafu reprezentujeme pomocou štvorcovej booleovskej matice a typu n × n. Pritom a[i][j] == true práve vtedy, keď v grafe vedie hrana z vrcholu i do vrcholu j.
• Napríklad pre graf s vrcholmi V = {0,1,2,3,4} a hranami E = {(0,1),(1,2),(1,3),(2,3),(3,0),(3,3)} dostávame nasledujúcu štvorcovú maticu rádu 5 (kde namiesto true píšeme 1 a namiesto false píšeme 0):

0 1 0 0 0
0 0 1 1 0
0 0 0 1 0
1 0 0 1 0
0 0 0 0 0

• Matica susednosti neorientovaného grafu je vždy symetrická.

Zoznamy následníkov (angl. successor lists)

• Pre každý vrchol u si pamätáme zoznam (ArrayList, LinkedList, prípadne aj obyčajné pole) následníkov – čiže vrcholov, do ktorých vedie z vrcholu u hrana. Tieto vrcholy si môžeme pamätať v ľubovoľnom poradí, napríklad od najmenšieho po najväčší.
• Napríklad pre graf s vrcholmi V = {0,1,2,3,4} a hranami E = {(0,1),(1,2),(1,3),(2,3),(3,0),(3,3)}:

0: 1
1: 2, 3
2: 3
3: 0, 3
4:

• Pre neorientované grafy obsahuje každý zo zoznamov práve všetkých susedov daného vrcholu. Ide tak o tzv. zoznamy susedov (angl. adjacency lists).

Implementácia tried reprezentujúcich grafy

Na prácu s grafom v princípe stačí pamätať si jeho maticu susednosti alebo zoznam následníkov. Keďže ale v nasledujúcich týždňoch budeme pracovať s grafmi častejšie, vytvoríme teraz menšiu knižnicu tried reprezentujúcich nemodifikovateľné grafy. S triedami z dnešnej prednášky sa budeme stretávať aj na nasledujúcich prednáškach a cvičeniach.

Graf ako abstraktný dátový typ: rozhranie DirectedGraph

• Skôr, než si ukážeme konkrétne implementácie grafov pomocou matíc susednosti aj zoznamov následníkov, mali by sme si ujasniť, aké metódy by mali poskytovať všetky triedy reprezentujúce grafy.
• Tieto metódy deklarujeme v nasledujúcom rozhraní DirectedGraph pre orientované grafy – keďže neorientované grafy považujeme za špeciálny prípad orientovaných grafov, bude toto rozhranie implementované aj triedami reprezentujúcimi neorientované grafy.
• Budeme prevažne pracovať s nemodifikovateľnými grafmi – nasledujúce rozhranie preto nebude deklarovať metódy meniace počet vrcholov alebo množinu hrán.

package graphs;

/**
 *  Rozhranie implementovane reprezentaciami orientovanych grafov o vrcholoch 0, 1, ..., n-1 pre nejake prirodzene n.
 *  Aj neorientovane grafy budu povazovane za specialny pripad orientovanych grafov; toto rozhranie tak bude
 *  implementovane vsetkymi triedami reprezentujucimi grafy.
 */
public interface DirectedGraph {
    /**
     * Metoda, ktora vrati pocet vrcholov reprezentovaneho grafu.
     *
     * @return Pocet vrcholov grafu.
     */
    int getVertexCount();

    /**
     * Metoda, ktora zisti, ci graf obsahuje vrchol s cislom vertex.
     * @param vertex Vrchol, ktoreho existencia sa ma zistit.
     * @return       Vrati true prave vtedy, ked graf obsahuje vrchol s cislom vertex.
     */
    boolean hasVertex(int vertex);

    /**
     * Metoda, ktora vrati pocet orientovanych hran reprezentovaneho grafu.
     *
     * @return Pocet orientovanych hran grafu.
     */
    int getDirectedEdgeCount();

    /**
     * Metoda, ktora zisti, ci v grafe existuje hrana medzi danou dvojicou vrcholov.
     *
     * @param from Pociatocny vrchol.
     * @param to   Koncovy vrchol.
     * @return     Vrati true prave vtedy, ked v grafe existuje hrana z vrcholu from do vrcholu to.
     */
    boolean hasEdge(int from, int to);

    /**
     * Metoda, ktora vrati vsetkych naslednikov daneho vrcholu -- cize vsetky vrcholy, do ktorych vedie z daneho vrcholu
     * orientovana hrana. Pre neorientovane grafy tak tato metoda vzdy vrati vsetkych susedov daneho vrcholu.
     *
     * @param vertex Lubovolny vrchol grafu.
     * @return       Naslednici vrcholu vertex ako instancia typu Iterable<Integer>.
     */
    Iterable<Integer> outgoingEdgesDestinations(int vertex);
}

Výstupom metódy outgoingEdgesDestinations je inštancia triedy implementujúcej rozhranie Iterable<Integer>. Pripomeňme si, že je v tomto rozhraní predpísaná jediná metóda iterator(), ktorá vráti iterátor (v našom prípade cez prvky typu Integer) a že inštancie inst tried implementujúcich Iterable<Integer> sa dajú použiť v cykle for each. Napríklad:

package graphs;

import java.io.*;

public class Trieda {
    /**
     * Metoda vypise do daneho vystupneho prudu pocet vrcholov a hran orientovaneho grafu, ako aj vsetky dvojice
     * vrcholov tvoriace orientovane hrany grafu.
     *
     * @param g   Graf, pre ktory sa vypis realizuje.
     * @param out Vystupny prud, do ktoreho sa vypis realizuje.
     */
    public static void printDirectedGraph(DirectedGraph g, PrintStream out) {
        int n = g.getVertexCount();
        out.println(n + " " + g.getDirectedEdgeCount());
        for (int u = 0; u <= n - 1; u++) {
            for (int v : g.outgoingEdgesDestinations(u)) {
                out.println(u + " " + v);
            }
        }
    }
}

Orientované grafy pomocou zoznamov následníkov: trieda SuccessorListsDirectedGraph

• Pre každý vrchol u si budeme udržiavať ArrayList jeho následníkov.
• V metóde outgoingEdgesDestinations jednoducho pre daný vrchol vrátime tento zoznam. Obalíme ho ale tak, aby sa nedal meniť (alternatívne by sme namiesto zoznamu samotného mohli vracať jeho kópiu, čo by ale bolo pri častom volaní tejto metódy o niečo menej efektívne).
• Konštruktor dostane počet vrcholov grafu a všetky jeho hrany v nejakom zoskupení typu Collection<DirectedEdge>, kde DirectedEdge je pomocná trieda reprezentujúca orientovanú hranu a slúžiaca hlavne na tento účel.

package graphs;

public class DirectedEdge {
    private int from, to;

    public DirectedEdge(int from, int to) {
        this.from = from;
        this.to = to;
    }

    public int getFrom() {
        return from;
    }

    public int getTo() {
        return to;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return this.getClass() == o.getClass() && from == ((DirectedEdge) o).from && to == ((DirectedEdge) o).to;
    }

    @Override
    public int hashCode() {
        return Integer.valueOf(from).hashCode() + 31 * Integer.valueOf(to).hashCode();
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca orientovany graf pomocou zoznamov naslednikov jednotlivych jeho vrcholov.
 */
public class SuccessorListsDirectedGraph implements DirectedGraph {
    /**
     * Pre kazdy vrchol si pamatame zoznam jeho naslednikov.
     */
    private ArrayList<ArrayList<Integer>> successorLists;

    /**
     * Pocet orientovanych hran v grafe (velkost grafu).
     */
    private int directedEdgeCount;

    /**
     * Konstruktor, ktory dostane ako argumenty pocet vrcholov grafu (t. j. jeho rad), ako aj vsetky hrany grafu.
     *
     * @param vertexCount   Rad grafu, cize pocet jeho vrcholov.
     * @param directedEdges Zoskupenie pozostavajuce zo vsetkych orientovanych hran grafu.
     */
    public SuccessorListsDirectedGraph(int vertexCount, Collection<? extends DirectedEdge> directedEdges) {
        if (vertexCount <= 0) {
            throw new IllegalArgumentException("Nonpositive vertex count.");
        }
        successorLists = new ArrayList<>();
        for (int i = 0; i <= vertexCount - 1; i++) {
            successorLists.add(new ArrayList<>());
        }
        directedEdgeCount = 0;
        for (DirectedEdge e : directedEdges) {
            if (!hasVertex(e.getFrom()) || !hasVertex(e.getTo())) {
                throw new IllegalArgumentException("Edge incident to a nonexistent vertex.");
            }
            if (!hasEdge(e.getFrom(), e.getTo())) {
                successorLists.get(e.getFrom()).add(e.getTo());
                directedEdgeCount++;
            } else {
                throw new IllegalArgumentException("Multiple edges connecting the same pair of vertices.");
            }
        }
    }

    @Override
    public int getVertexCount() {
        return successorLists.size();
    }

    @Override
    public boolean hasVertex(int v) {
        return v >= 0 && v <= getVertexCount() - 1;
    }

    @Override
    public int getDirectedEdgeCount() {
        return directedEdgeCount;
    }

    @Override
    public boolean hasEdge(int from, int to) {
        if (!hasVertex(from) || !hasVertex(to)) {
            throw new IllegalArgumentException("Nonexistent vertex.");
        }
        return successorLists.get(from).contains(to);
    }

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int vertex) {
        if (!hasVertex(vertex)) {
            throw new IllegalArgumentException("Nonexistent vertex.");
        }
        // Nasledujucim prikazom vratime nemodifikovatelny pohlad na zoznam naslednikov vrcholu vertex
        return Collections.unmodifiableList(successorLists.get(vertex));
    }
}

Orientované grafy pomocou matice susednosti: trieda AdjacencyMatrixDirectedGraph

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca orientovany graf pomocou matice susednosti.
 */
public class AdjacencyMatrixDirectedGraph implements DirectedGraph {
    /**
     * Matica susednosti.
     */
    private boolean[][] adjacencyMatrix;

    /**
     * Pocet orientovanych hran v grafe (velkost grafu).
     */
    private int directedEdgeCount;

    /**
     * Konstruktor, ktory dostane ako argumenty pocet vrcholov grafu (t. j. jeho rad), ako aj vsetky hrany grafu.
     *
     * @param vertexCount   Rad grafu, cize pocet jeho vrcholov.
     * @param directedEdges Zoskupenie pozostavajuce zo vsetkych orientovanych hran grafu.
     */
    public AdjacencyMatrixDirectedGraph(int vertexCount, Collection<? extends DirectedEdge> directedEdges) {
        if (vertexCount <= 0) {
            throw new IllegalArgumentException("Nonpositive vertex count.");
        }
        adjacencyMatrix = new boolean[vertexCount][vertexCount];
        directedEdgeCount = 0;
        for (DirectedEdge e : directedEdges) {
            if (!hasVertex(e.getFrom()) || !hasVertex(e.getTo())) {
                throw new IllegalArgumentException("Edge incident to a nonexistent vertex.");
            }
            if (!hasEdge(e.getFrom(), e.getTo())) {
                adjacencyMatrix[e.getFrom()][e.getTo()] = true;
                directedEdgeCount++;
            } else {
                throw new IllegalArgumentException("Multiple edges connecting the same pair of vertices.");
            }
        }
    }

    @Override
    public int getVertexCount() {
        return adjacencyMatrix.length;
    }

    @Override
    public boolean hasVertex(int v) {
        return v >= 0 && v <= getVertexCount() - 1;
    }

    @Override
    public int getDirectedEdgeCount() {
        return directedEdgeCount;
    }

    @Override
    public boolean hasEdge(int from, int to) {
        if (!hasVertex(from) || !hasVertex(to)) {
            throw new IllegalArgumentException("Nonexistent vertex.");
        }
        return adjacencyMatrix[from][to];
    }

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int vertex) {
        if (!hasVertex(vertex)) {
            throw new IllegalArgumentException("Nonexistent vertex.");
        }
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i <= getVertexCount() - 1; i++) {
            if (adjacencyMatrix[vertex][i]) {
                a.add(i);
            }
        }
        return Collections.unmodifiableList(a);
    }
}

Neorientované grafy: triedy AdjacencyListsUndirectedGraph a AdjacencyMatrixUndirectedGraph

Pri implementácii neorientovaných grafov môžeme využiť dedenie od prislušných tried pre orientované grafy. Narážame tu len na pár rozdielov:

• Konštruktor by mal ako argument dostať namiesto zoskupenia orientovaných hrán zoskupenie neorientovaných hrán. Reprezentáciou neorientovaných hrán budú inštancie pomocnej triedy UndirectedEdge.
• Pri volaní konštruktora nadtriedy tak bude potrebné vyrobiť príslušný zoznam orientovaných hrán, ktorý pre každú neorientovanú hranu rôznu od slučky obsahuje dve protichodné orientované hrany a pre každú neorientovanú slučku obsahuje orientovanú slučku. Túto úlohu bude realizovať statická metóda undirectedToDirectedEdges pomocnej triedy Edges.
• Popri metóde getDirectedEdgeCount vracajúcej počet orientovaných hrán by triedy pre neorientované grafy mali poskytovať aj metódu getUndirectedEdgeCount vracajúcu počet neorientovaných hrán.

package graphs;

/**
 *  Rozhranie implementovane reprezentaciami neorientovanych grafov o vrcholoch 0, 1, ..., n-1 pre nejake prirodzene n.
 */
public interface UndirectedGraph extends DirectedGraph {
    /**
     * Metoda, ktora vrati pocet neorientovanych hran reprezentovaneho grafu.
     *
     * @return Pocet neorientovanych hran grafu.
     */
    int getUndirectedEdgeCount();

}

package graphs;

import java.util.*;

public class UndirectedEdge {
    private Set<Integer> incidentVertices;

    public UndirectedEdge(int u, int v) {
        incidentVertices = new HashSet<>();
        incidentVertices.add(u);
        incidentVertices.add(v);
    }

    public Set<Integer> getIncidentVertices() {
        return Collections.unmodifiableSet(incidentVertices);
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return this.getClass() == o.getClass() && incidentVertices.equals(((UndirectedEdge) o).getIncidentVertices());
    }

    @Override
    public int hashCode() {
        return incidentVertices.hashCode();
    }
}

package graphs;

import java.util.*;

public class Edges {

    /**
     * Metoda, ktora prerobi zoskupenie neorientovanych hran na prislusny zoznam orientovanych hran.
     * @param undirectedEdges Zoznam neorientovanych hran.
     * @return                Prislusny zoznam orientovanych hran.
     */
    public static List<DirectedEdge> undirectedToDirectedEdges(Collection<? extends UndirectedEdge> undirectedEdges) {
        ArrayList<DirectedEdge> result = new ArrayList<>();
        for (UndirectedEdge e : undirectedEdges) {
            ArrayList<Integer> vertices = new ArrayList<>(e.getIncidentVertices());
            if (vertices.size() == 1) {
                result.add(new DirectedEdge(vertices.get(0), vertices.get(0)));
            } else {
                result.add(new DirectedEdge(vertices.get(0), vertices.get(1)));
                result.add(new DirectedEdge(vertices.get(1), vertices.get(0)));
            }
        }
        return Collections.unmodifiableList(result);
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca neorientovany graf pomocou zoznamov susedov jednotlivych jeho vrcholov.
 */
public class AdjacencyListsUndirectedGraph extends SuccessorListsDirectedGraph implements UndirectedGraph {
    private int undirectedEdgeCount;

    public AdjacencyListsUndirectedGraph(int vertexCount, Collection<? extends UndirectedEdge> undirectedEdges) {
        super(vertexCount, Edges.undirectedToDirectedEdges(undirectedEdges));
        undirectedEdgeCount = undirectedEdges.size();
    }

    @Override
    public int getUndirectedEdgeCount() {
        return undirectedEdgeCount;
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca neorientovany graf pomocou matice susednosti.
 */
public class AdjacencyMatrixUndirectedGraph extends AdjacencyMatrixDirectedGraph implements UndirectedGraph {
    private int undirectedEdgeCount;

    public AdjacencyMatrixUndirectedGraph(int vertexCount, Collection<? extends UndirectedEdge> undirectedEdges) {
        super(vertexCount, Edges.undirectedToDirectedEdges(undirectedEdges));
        undirectedEdgeCount = undirectedEdges.size();
    }

    @Override
    public int getUndirectedEdgeCount() {
        return undirectedEdgeCount;
    }
}

Vytvorenie grafu

Metódy readDirectedGraph resp. readUndirectedGraph triedy Trieda uvedenej nižšie prečítajú pomocou danej inštancie triedy Scanner reprezentáciu orientovaného resp. neorientovaného grafu a vytvoria podľa nej graf určenej implementácie (buď teda pôjde o graf implementovaný pomocou zoznamov následníkov resp. susedov, alebo o graf implementovaný pomocou matice susednosti). Argument pre implementáciu grafu je pritom vymenovaného typu GraphImplementation (o vymenovaných typoch sa možno dočítať viac tu).

package graphs;

public enum GraphImplementation {
    LISTS, MATRIX
}

package graphs;

import java.util.*;

public class Trieda {
    /**
     * Metoda, ktora precita textovu reprezentaciu orientovaneho grafu pozostavajucu z poctu vrcholov n, poctu hran m
     * a z m dvojic vrcholov udavajucich jednotlive orientovane hrany a vytvori podla nej graf urcenej implementacie.
     *
     * @param scanner        Skener, z ktoreho sa reprezentacia grafu cita.
     * @param implementation Implementacia vytvaraneho grafu (zoznamy naslednikov, alebo matica susednosti).
     * @return               Vytvoreny graf.
     */
    public static DirectedGraph readDirectedGraph(Scanner scanner, GraphImplementation implementation) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<DirectedEdge> edges = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            edges.add(new DirectedEdge(scanner.nextInt(), scanner.nextInt()));
        }
        DirectedGraph g = null;
        switch (implementation) {
            case LISTS:
                g = new SuccessorListsDirectedGraph(n, edges);
                break;
            case MATRIX:
                g = new AdjacencyMatrixDirectedGraph(n, edges);
                break;
        }
        return g;
    }

    /**
     * Metoda, ktora precita textovu reprezentaciu neorientovaneho grafu pozostavajucu z poctu vrcholov n, poctu hran m
     * a z m dvojic vrcholov udavajucich jednotlive neorientovane hrany a vytvori podla nej graf urcenej implementacie.
     *
     * @param scanner        Skener, z ktoreho sa reprezentacia grafu cita.
     * @param implementation Implementacia vytvaraneho grafu (zoznamy naslednikov, alebo matica susednosti).
     * @return               Vytvoreny graf.
     */
    public static UndirectedGraph readUndirectedGraph(Scanner scanner, GraphImplementation implementation) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<UndirectedEdge> edges = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            edges.add(new UndirectedEdge(scanner.nextInt(), scanner.nextInt()));
        }
        UndirectedGraph g = null;
        switch (implementation) {
            case LISTS:
                g = new AdjacencyListsUndirectedGraph(n, edges);
                break;
            case MATRIX:
                g = new AdjacencyMatrixUndirectedGraph(n, edges);
                break;
        }
        return g;
    }
}

Volanie týchto metód potom môže vyzerať napríklad nasledovne:

DirectedGraph g1 = readDirectedGraph(scanner, GraphImplementation.LISTS);
UndirectedGraph g2 = readUndirectedGraph(scanner, GraphImplementation.MATRIX);

Porovnanie reprezentácií grafov

Majme orientovaný graf s n vrcholmi a m hranami – počet hrán m teda môže byť od 0 po n². V závislosti od použitej reprezentácie grafu sa líši ako časová zložitosť jednotlivých operácií na grafoch, tak aj pamäťová zložitosť samotnej tejto reprezentácie. Napríklad:

• Pamäť potrebná na uloženie matice susednosti grafu je vždy rádovo veľkosti n². Pri reprezentácii pomocou zoznamov následníkov resp. susedov je veľkosť reprezentácie grafu rádovo n+m. Hlavne pre riedke grafy (s menším počtom hrán) je teda reprezentácia pomocou zoznamov pamäťovo efektívnejšia.
• Operácia hasEdge sa pre grafy reprezentované maticou susednosti vykoná v konštantnom čase. Pre grafy reprezentované zoznamami neusporiadaných následníkov resp. susedov môže byť zložitosť tejto operácie až lineárna v závislosti od počtu vrcholov grafu (je potrebné prejsť celý zoznam susedov jedného vrchola, ktorý môže obsahovať až n rôznych vrcholov).
• Naopak vytvorenie zoznamu následníkov resp. susedov grafu v metóde outgoingEdgesDestinations je efektívnejšie pri reprezentácii pomocou zoznamov.

Ďalšie varianty grafov

Grafy na tejto prednáške chápeme v relatívne obmedzenom slova zmysle. V praxi sa často zídu aj rôzne rozšírenia definície grafu:

• Grafy s násobnými hranami (niekde tiež multigrafy) umožňujú viesť medzi danou dvojicou vrcholov viacero paralelných hrán. To možno v pamäti počítača realizovať napríklad nahradením booleovskej matice maticou prirodzených čísel udávajúcich násobnosti jendotlivých hrán, prípadne pridaním informácie o multiplicite do zoznamov následníkov resp. susedov.
• Ohodnotené grafy obsahujú na hranách nejakú ďalšiu prídavnú informáciu (napríklad pri cestnej sieti si môžeme pamätať dĺžku jednotlivých úsekov, prípadne možno ohodnotené grafy využiť aj na reprezentáciu multigrafov). Možno ich reprezentovať nahradením booleovskej matice maticou ohodnotení, prípadne zakomponovaním informácie o ohodnotení hrán do zoznamov následníkov resp. susedov. S ohodnotenými grafmi sa okrajovo stretneme aj tento semester.
• Dynamické grafy podporujú aj pridávanie a mazanie vrcholov a/alebo hrán.