Letný semester, prednáška č. 6

Oznamy

• Počas najbližších cvičení, čiže v stredu 24. marca od 11:30 do 13:00 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 stretnutí „Cvičenia” v MS Teams.
• Druhú bonusovú úlohu je potrebné odovzdať do stredy 24. marca, 11:30 (čiže do začiatku stredajších cvičení).
• Druhú domácu úlohu je potrebné odovzdať do pondelka 29. marca, 11:30 (čiže do začiatku siedmej prednášky).

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.
• Musí byť umiestnený bezprostredne pred triedou, metódou a pod., ku ktorej sa vzťahuje.
• Časť textu komentára končiaca prvou bodkou je 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.
• 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:

    /**
     * Metoda pocitajuca pocet retazcov vo vstupnom zozname retazcov, ktore obsahuju dany podretazec. Hladany
     * podretazec musi byt rozny 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. Hladany
     * podretazec musi byt rozny 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 a LinkedList.

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á dobrú podporu aj pre najnovšiu verziu 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žnice balíky hamcrest-core-1.3.jar a junit-4.12.jar, ktoré by mali byť umiestnené v podpriečinku lib koreňového priečinka inštalácie IntelliJ (čísla verzií sa v závislosti od verzie IntelliJ môžu trochu líšiť, ale podstatné je, aby verzia JUnit začínala číslom 4).
• 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
• 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;

        List<String> expectedList = new ArrayList<>(list);

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

        assertTrue(expectedList.equals(list));
    }

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

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

    @Test
    public void testListContainsNull() {
        List<String> list = new LinkedList<>();
        list.add("retazec1");
        list.add(null);
        list.add("retazec2");
        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 ProgTest 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.
• Ď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

• Pod orientovaným grafom (angl. directed graph) budeme rozumieť konečnú množinu vrcholov (zvyčajne {0,1,...,n-1} pre nejaké kladné prirodzené číslo n), kde medzi každou dvojicou vrcholov môže 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”. Neorientovaný graf budeme stotožňovať s orientovaným grafom, v ktorom existencia hrany z vrcholu u do vrcholu v (rôzneho od u) implikuje existenciu hrany z v do u. Príklad diagramu neorientovaného grafu je na obrázku nižšie.

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é.

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 T je skratkou true a F pre false):

  0 1 2 3 4
0 F T F F F
1 F F T T F
2 F F F T F
3 T F F T F
4 F F F F F

• 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} 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).

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

• Skôr, než si ukážeme konkrétne implementácie grafov pomocou matíc susednosti aj zoznamov následníkov, potrebujeme vedieť, aké operácie by mal graf poskytovať.
• Napíšeme preto jednoduché rozhranie pre (orientovaný alebo neorientovaný) graf deklarujúce metódy, ktoré by mala poskytovať každá implementácia grafov.
• 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 pre reprezentacie grafov o vrcholoch 0, 1, ..., n-1 pre nejake
 *  prirodzene cislo n.
 */
public interface Graph {
    /**
     * Metoda, ktora vrati pocet vrcholov reprezentovaneho grafu.
     *
     * @return Pocet vrcholov grafu.
     */
    int getNumberOfVertices();

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

    /**
     * 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 existsEdge(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 grafu, ako aj vsetky dvojice vrcholov tvoriace
     * hrany grafu. 
     * 
     * @param g   Graf, pre ktory sa vypis realizuje.
     * @param out Vystupny prud, do ktoreho sa vypis realizuje.
     */
    public static void printGraph(Graph g, PrintStream out) {
        int n = g.getNumberOfVertices();
        out.println(n + " " + g.getNumberOfEdges());
        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 SuccessorListsGraph

• Pre každý vrchol u si budeme udržiavať ArrayList jeho následníkov.
• V metóde outgoingEdgesDestinations jednoducho pre daný vrchol vrátime kópiu tohto zoznamu. Obalíme ju navyše tak, aby sa nedala meniť (podstatné je ale hlavne vrátiť nejakú kópiu zoznamu a nie zoznam samotný).
• Konštruktor dostane počet vrcholov grafu a všetky jeho hrany v nejakom zoskupení typu Collection<Edge>, kde Edge je pomocná trieda reprezentujúca hranu a slúžiaca hlavne na tento účel.

package graphs;

public class Edge {
    private int from, to;

    public Edge(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 == ((Edge) o).from && to == ((Edge) 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 SuccessorListsGraph implements Graph {
    /**
     * Pre kazdy vrchol zoznam jeho naslednikov.
     */
    private ArrayList<ArrayList<Integer>> successorLists;

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

    /**
     * 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 edges       Zoskupenie pozostavajuce zo vsetkych hran grafu.
     */
    public SuccessorListsGraph(int vertexCount, Collection<Edge> edges) {
        successorLists = new ArrayList<>();
        for (int i = 0; i <= vertexCount - 1; i++) {
            successorLists.add(new ArrayList<>());
        }
        edgeCount = 0;
        for (Edge e : edges) {
            if (!existsEdge(e.getFrom(), e.getTo())) {
                successorLists.get(e.getFrom()).add(e.getTo());
                edgeCount++;
            }
        }
    }

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

    @Override
    public int getNumberOfEdges() {
        return edgeCount;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return successorLists.get(from).contains(to);
    }

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int from) {
        return Collections.unmodifiableList(successorLists.get(from));  // Vratime nemodifikovatelnu kopiu zoznamu.
    }
}

Orientované grafy pomocou matice susednosti: trieda AdjacencyMatrixGraph

package graphs;

import java.util.*;

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

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

    /**
     * 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 edges       Zoskupenie pozostavajuce zo vsetkych hran grafu.
     */
    public AdjacencyMatrixGraph(int vertexCount, Collection<Edge> edges) {
        adjacencyMatrix = new boolean[vertexCount][vertexCount];
        edgeCount = 0;
        for (Edge e : edges) {
            if (!existsEdge(e.getFrom(), e.getTo())) {
                adjacencyMatrix[e.getFrom()][e.getTo()] = true;
                edgeCount++;
            }
        }
    }

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

    @Override
    public int getNumberOfEdges() {
        return edgeCount;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjacencyMatrix[from][to];
    }

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int vertex) {
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i <= getNumberOfVertices() - 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 dva rozdiely:

• Konštruktor by mal pre každú požadovanú neorientovanú hranu pridať dvojicu protichodných orientovaných hrán (s výnimkou slučiek, kde sa pridáva jediná orientovaná hrana).
• Metóda getNumberOfEdges by nemala vracať počet orientovaných hrán, ale počet neorientovaných hrán.

package graphs;

public interface UndirectedGraph extends Graph {

}

package graphs;

import java.util.*;

/**
 * Pomocne metody na pracu so zoskupeniami hran.
 */
public class Edges {

    public static Collection<Edge> symmetricClosure(Collection<Edge> edges) {
        List<Edge> result = new ArrayList<>();
        for (Edge e : edges) {
            result.add(e);
            if (e.getFrom() != e.getTo()) {
                result.add(new Edge(e.getTo(), e.getFrom()));
            }
        }
        return result;
    }

    public static int distinctUndirectedEdges(Collection<Edge> edges) {
        HashSet<Edge> set = new HashSet<>();
        for (Edge e : edges) {
            if (!set.contains(e) && !set.contains(new Edge(e.getTo(), e.getFrom()))) {
                set.add(e);
            }
        }
        return set.size();
    }
}

package graphs;

import java.util.*;

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

    public AdjacencyListsUndirectedGraph(int vertexCount, Collection<Edge> edges) {
        super(vertexCount, Edges.symmetricClosure(edges));
        undirectedEdgeCount = Edges.distinctUndirectedEdges(edges);
    }

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

package graphs;

import java.util.*;

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

    public AdjacencyMatrixUndirectedGraph(int vertexCount, Collection<Edge> edges) {
        super(vertexCount, Edges.symmetricClosure(edges));
        undirectedEdgeCount = Edges.distinctUndirectedEdges(edges);
    }

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

Vytvorenie grafu

• Vytvoríme prázdny graf s určitým počtom vrcholov, následne po jednom pridávame hrany.

/* Metoda, ktora zo scannera s nacita graf vo formate: pocet vrcholov,
   pocet hran a zoznam hran zadanych dvojicami koncovych vrcholov.
   Ak undirected == true, vytvori neorientovany graf, inak orientovany.
   Ak matrix == true, vytvori graf reprezentovany maticou susednosti, 
   v opacnom pripade vytvori graf reprezentovany zoznamami susedov. */
static Graph readGraph(Scanner s, boolean undirected, boolean matrix) {
    int n = s.nextInt();
    int m = s.nextInt();
    Graph g;
    if (undirected) {
        if (matrix) {
            g = new AdjMatrixUndirectedGraph(n);
        } else {
            g = new AdjListsUndirectedGraph(n);
        }
    } else {
        if (matrix) {
            g = new AdjMatrixGraph(n);
        } else {
            g = new AdjListsGraph(n);
        }
    }
    for (int i = 0; i < m; i++) {
        int u = s.nextInt();
        int v = s.nextInt();
        g.addEdge(u, v);
    }
    return g;
}

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².
• Vyjadríme čas rôznych operácií v O-notácii:
  • O(1): robíme len konštantný počet operácií bez ohľadu na veľkosť grafu.
  • O(n): čas operácie rastie v najhoršom prípade lineárne s počtom vrcholov grafu.
  • O(m): čas operácie rastie v najhoršom prípade lineárne s počtom hrán grafu.
  • O(n²): čas operácie rastie v najhoršom prípade kvadraticky s počtom vrcholov grafu.
• Väčšinou máme viac hrán ako vrcholov, takže O(1) je lepšie ako O(n), to je lepšie ako O(m) a to je lepšie ako O(n²).

	Matica susednosti	Zoznamy susedov
Pamäť	O(n2)	O(n+m)
Vytvoriť graf bez hrán	O(n2)	O(n)
addEdge	O(1)	O(n)
existsEdge	O(1)	O(n)
Prejdenie susedov vrcholu	O(n)	O(stupeň vrcholu)
Výpis grafu pomocou adjVertices	O(n2)	O(n+m)

• Matica susednosti:
  • Rýchla operácia existsEdge.
  • Ak je graf riedky (málo hrán), zaberá zbytočne veľa pamäte a dlho trvá prejdenie susedov vrcholu.
  • Maticová reprezentácia sa však dá využiť pri niektorých algoritmoch (viac vo vyšších ročníkoch).
• Zoznamy susednosti
  • Vhodná reprezentácia aj pre riedke grafy.
  • Dlho trvá nájdenie konkrétnej hrany, ale všetkých susedov vrcholu vieme prejsť relatívne rýchlo.
  • Najvhodnejšia reprezentácia pre väčšinu algoritmov, ktoré uvidíme.

Ď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 nahradením zoznamov susedov zobrazeniami z množiny vrcholov do množiny prirodzených čísel.
• 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 ich možno využiť aj na reprezentáciu multigrafov). Možno ich reprezentovať nahradením booleovskej matice maticou ohodnotení, prípadne nahradením zoznamov susedov zobrazeniami z množiny vrcholov do množiny ohodnotení. S ohodnotenými grafmi sa okrajovo stretneme na budúcej prednáške.
• Dynamické grafy podporujú aj mazanie hrán a pridávanie a mazanie vrcholov.