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 x Nejaky text pre opis parametra x 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”.
• Ď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 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.
• V neorientovanom grafe 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.

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ď z 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)}:

  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 susedov (angl. adjacency lists)

• Pre každý vrchol u si pamätáme zoznam vrcholov, do ktorých vedie z vrcholu u hrana (pole, ArrayList, LinkedList, ...). 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é hrany obsahuje každý zo zoznamov práve všetkých susedov daného vrcholu.

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

• Skôr, než si ukážeme konkrétne implementácie grafu pomocou matíc susednosti aj zoznamov susedov, potrebujeme vedieť, aké operácie by mal graf poskytovať.
• Napíšeme preto jednoduché rozhranie pre (orientovaný alebo neorientovaný) graf definujúce metódy na pridávanie hrán, testovanie existencie hrán a prechádzanie cez všetkých susedov určitého vrcholu:

/* Rozhranie pre reprezentaciu grafu o vrcholoch 0, 1, ..., n-1 pre nejake
   prirodzene cislo n: */
interface Graph {
    int getNumberOfVertices(); // Vrati pocet vrcholov grafu.
    int getNumberOfEdges();    // Vrati pocet hran grafu.
    
    /* Prida hranu z vrcholu from do vrcholu to
       a vrati true, ak sa ju podarilo pridat: */
    boolean addEdge(int from, int to);
    
    /* Vrati true, ak existuje hrana z vrcholu from do vrcholu to: */
    boolean existsEdge(int from, int to);
    
    /* Vrati iterovatelnu skupinu pozostavajucu z prave vsetkych vrcholov,
       do ktorych vedie hrana z vrcholu vertex. Pre neorientovane grafy ide
       o prave vsetkych susedov vrcholu vertex: */
    Iterable<Integer> adjVertices(int vertex); 
}

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

/* Vypise orientovany graf g do vystupneho prudu out. */
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.adjVertices(u)) {
            out.println(u + " " + v);
        }
    }
}

Orientované grafy pomocou zoznamov susedov: trieda AdjListsGraph

• Pre každý vrchol u budeme udržiavať ArrayList vrcholov, do ktorých vedie z vrcholu u hrana.
• V metóde adjVertices jednoducho vrátime tento ArrayList; „obalíme” ho však tak, aby sa nedal meniť.

import java.util.*;

// ...

/* Trieda reprezentujuca orientovany graf pomocou zoznamov (ArrayList-ov) susedov: */
class AdjListsGraph implements Graph {
    /* Pre kazdy vrchol zoznam vrcholov, do ktorych z daneho vrcholu vedie hrana: */
    private ArrayList<ArrayList<Integer>> adjLists;
 
    /* Pocet hran v grafe: */
    private int numEdges;
    
    /* Konstruktor, ktory ako parameter dostane prirodzene cislo numVertices 
       a vytvori graf o numVertices vrcholoch a bez jedinej hrany: */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<>());
        }
        numEdges = 0;
    }
    
    @Override
    public int getNumberOfVertices() {
        return adjLists.size();
    }
    
    @Override 
    public int getNumberOfEdges() {
        return numEdges;
    }
    
    @Override
    public boolean addEdge(int from, int to) {
        if (existsEdge(from, to)) {
            return false;
        } else {
            adjLists.get(from).add(to);
            numEdges++;
            return true;
        }
    }
    
    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to);
    }
    
    @Override
    public Iterable<Integer> adjVertices(int from) {
        // Zoznam adjLists.get(from) "obalime" tak, aby sa nedal menit: 
        return Collections.unmodifiableList(adjLists.get(from)); 
    }
}

Orientované grafy pomocou matice susednosti: trieda AdjMatrixGraph

/* Trieda reprezentujuca orientovany graf pomocou matice susednosti: */
class AdjMatrixGraph implements Graph {
    /* Matica susednosti: */
    private boolean[][] adjMatrix;
    
    /* Pocet hran v grafe: */
    private int numEdges;
    
    /* Konstruktor, ktory ako parameter dostane prirodzene cislo numVertices 
       a vytvori graf o numVertices vrcholoch a bez jedinej hrany: */
    public AdjMatrixGraph(int numVertices) {
        adjMatrix = new boolean[numVertices][numVertices];
        for (int i = 0; i <= numVertices - 1; i++) {
            for (int j = 0; j <= numVertices - 1; j++) {
                adjMatrix[i][j] = false;
            }
        }
        numEdges = 0;
    }
    
    @Override
    public int getNumberOfVertices() {
        return adjMatrix.length;
    }
    
    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }
    
    @Override
    public boolean addEdge(int from, int to) {
        if (existsEdge(from, to)) {
            return false;
        } else {
            adjMatrix[from][to] = true;
            numEdges++;
            return true;
        }
    }
    
    @Override
    public boolean existsEdge(int from, int to) {
        return adjMatrix[from][to];
    }
    
    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        // Vytvorime pomocny zoznam susedov a vratime ho "obaleny" tak, aby sa nedal menit:
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i <= adjMatrix[vertex].length - 1; i++) {
            if (adjMatrix[vertex][i]) {
                a.add(i);
            }
        }
        return Collections.unmodifiableList(a);
    }
}

Neorientované grafy: triedy AdjListsUndirectedGraph a AdjMatrixUndirectedGraph

Pri implementácii neorientovaných grafov môžeme využiť dedenie od prislúchajúcich tried reprezentujúcich orientované grafy. Narážame tu len na dva rozdiely: pridanie neorientovanej hrany metódou addEdge v skutočnosti zodpovedá pridaniu dvojice protichodných orientovaných hrán (s výnimkou slučiek, kde sa pridáva jediná orientovaná hrana) a metóda getNumberOfEdges by nemala vracať počet orientovaných hrán, ale počet neorientovaných hrán.

interface UndirectedGraph extends Graph {
    
}

/* Trieda reprezentujuca neorientovany graf pomocou zoznamov susedov reprezentovanych
   v podobe ArrayList-ov. */
class AdjListsUndirectedGraph extends AdjListsGraph implements UndirectedGraph {
    /* Pocet neorientovanych hran v grafe: */
    private int numUndirectedEdges;
    
    public AdjListsUndirectedGraph(int numVertices) {
        super(numVertices);
        numUndirectedEdges = 0;
    }
    
    @Override
    public int getNumberOfEdges() {
        return numUndirectedEdges;
    }    
    
    @Override
    public boolean addEdge(int from, int to) {
        boolean r = super.addEdge(from, to);
        super.addEdge(to, from);
        if (r) {
            numUndirectedEdges++;
        }
        return r;
    }
}

/* Trieda reprezentujuca neorientovany graf pomocou matice susednosti: */
class AdjMatrixUndirectedGraph extends AdjMatrixGraph implements UndirectedGraph {
    /* Pocet neorientovanych hran v grafe: */
    private int numUndirectedEdges;
    
    public AdjMatrixUndirectedGraph(int numVertices) {
        super(numVertices);
        numUndirectedEdges = 0;
    }
    
    @Override
    public int getNumberOfEdges() {
        return numUndirectedEdges;
    }    
    
    @Override
    public boolean addEdge(int from, int to) {
        boolean r = super.addEdge(from, to);
        super.addEdge(to, from);
        if (r) {
            numUndirectedEdges++;
        }
        return r;
    }
}

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.