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.
• 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:

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");
        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

• Pod orientovaným grafom (angl. directed graph) budeme rozumieť konečnú množinu vrcholov (na tomto predmete 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”. Medzi každou (neusporiadanou) dvojicou vrcholov pritom môže viesť najviac jedna hrana a v každom vrchole môže graf obsahovať najviac jednu slučku. Neorientovaný graf budeme stotožňovať s orientovaným grafom, v ktorom existencia hrany z vrcholu u do vrcholu v implikuje existenciu hrany z v do u. Príklad diagramu neorientovaného grafu je na obrázku nižšie.

Pod grafom (bez ďalšieho prívlastku) budeme mať – na rozdiel od väčšiny odborníkov na teóriu grafov – vždy 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).

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 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<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 nemodifikovatelny pohlad na zoznam successorLists.get(from).
    }
}

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

Metóda readGraph triedy Trieda uvedenej nižšie prečíta pomocou danej inštancie triedy Scanner reprezentáciu grafu a vytvorí z nej graf typu určeného nasledujúcim parametrom. Argument pre typ grafu je pritom vymenovaného typu GraphType (o vymenovaných typoch sa možno dočítať viac tu).

package graphs;

public enum GraphType {
    DIRECTED_SUCCESSOR_LISTS, DIRECTED_ADJACENCY_MATRIX, UNDIRECTED_ADJACENCY_LISTS, UNDIRECTED_ADJACENCY_MATRIX
}

package graphs;

import java.util.*;

public class Trieda {
    /**
     * Metoda, ktora precita textovu reprezentaciu grafu pozostavajucu z poctu vrcholov n, poctu hran m a z m dvojic
     * vrcholov udavajucich jednotlive hrany a vytvori z nej graf urceneho typu.
     *
     * @param scanner   Scanner, z ktoreho sa reprezentacia grafu cita.
     * @param graphType Typ vytvaraneho grafu.
     * @return          Vytvoreny graf.  
     */
    public static Graph readGraph(Scanner scanner, GraphType graphType) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge> edges = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            edges.add(new Edge(scanner.nextInt(), scanner.nextInt()));
        }
        Graph g = null;
        switch (graphType) {
            case DIRECTED_SUCCESSOR_LISTS:
                g = new SuccessorListsGraph(n, edges);
                break;
            case DIRECTED_ADJACENCY_MATRIX:
                g = new AdjacencyMatrixGraph(n, edges);
                break;
            case UNDIRECTED_ADJACENCY_LISTS:
                g = new AdjacencyListsUndirectedGraph(n, edges);
                break;
            case UNDIRECTED_ADJACENCY_MATRIX:
                g = new AdjacencyMatrixUndirectedGraph(n, edges);
                break;
        }
        return g;
    }
}

Volanie metódy readGraph potom môže vyzerať napríklad nasledovne:

Graph g = readGraph(scanner, GraphType.DIRECTED_SUCCESSOR_LISTS);

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 existsEdge sa pre grafy reprezentované maticou susednosti vykoná v konštantnom čase. Pre grafy reprezentované zoznamami 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 ich možno 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.