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

Testovanie programov

• Cieľom testovania je nájsť chyby v programe, teda preukázať, že program nefunguje podľa špecifikácie (aby sme potom vedeli chybu nájsť a opraviť).
• Test pozostáva zo vstupu, správneho výstupu a popisu jeho významu.
• Program sa spustí na vstupe a jeho výstup sa porovná so správnou 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, potom sa programuje kód, ktorý ich dokáže splniť.

White-box testovanie

Pod white-box testovaním sa rozumie prístup, pri ktorom testy vytvárame na základe kódu; snažíme sa pritom preveriť všetky vetvy výpočtu.

• V cykle vyskúšame 0 iterácií, 1 iteráciu, maximálny počet iterácií.
• V podmienke vyskúšame vetvu true aj false.
• ...

Nevýhodou tohto prístupu však 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úci kód nespĺňa úplne špecifikáciu:

    /** 
     * Metoda zo vstupneho pola array vyhodi prvy vyskyt objektu rovneho x,
     * pricom rovnost sa testuje metodou equals.
     * Vsetky dalsie prvky posunie v poli o jednu poziciu dolava a na koniec
     * pola vlozi hodnotu null.
     * Ak vstupne pole neobsahuje x, metoda ho nijak nemodifikuje.
     * Metoda vrati true, ak bolo pole modifikovane; v opacnom pripade vrati false.
     * Ak je niektory zo vstupnych parametrov null, vyhodi java.lang.NullPointerException.
     */
    public static boolean remove(Object[] array, Object x) {
        int i;
        for (i = 0; i <= array.length - 1; i++) {
            if (array[i].equals(x)) {
                break;
            }
        }
        if (i == array.length) {
            return false;
        }
        while (i <= array.length - 2) {
            array[i] = array[i + 1];
            i++;
        }
        array[i] = null;
        return true;
    }

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 nasledujúcu neformálnu špecifikáciu metódy remove:

    /** 
     * Metoda zo vstupneho pola array vyhodi prvy vyskyt objektu rovneho x,
     * pricom rovnost sa testuje metodou equals.
     * Vsetky dalsie prvky posunie v poli o jednu poziciu dolava a na koniec
     * pola vlozi hodnotu null.
     * Ak vstupne pole neobsahuje x, metoda ho nijak nemodifikuje.
     * Metoda vrati true, ak bolo pole modifikovane; v opacnom pripade vrati false.
     * Ak je niektory zo vstupnych parametrov null, vyhodi java.lang.NullPointerException.
     */
    public static boolean remove(Object[] array, Object x);

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

• Prázdne pole array.
• Pole obsahujúce iba x.
• Pole obsahujúce x na začiatku.
• Pole obsahujúce x na konci.
• Pole obsahujúce x niekde v strede.
• Pole obsahujúce viacero kópií objektu x.
• Pole neobsahujúce x.
• Pole obsahujúce prvky null.
• Pole obsahujúce objekty rôznych typov.
• Veľmi dlhé pole.
• Prípad, keď array je rovné null.
• Prípad, keď x je rovné null.

Podrobnejšie rozpísanie jedného z testov:

• Vstup: array = {1,2,3}, x = 1.
• Výstup: array = {2,3,null}, návratová hodnota true.
• Význam testu: testovanie prípadu, keď pole array obsahuje x na začiatku.

JUnit

• Systém JUnit umožňuje vytvárať špeciálne triedy obsahujúce testy iných tried.
• Sadu testov môžeme ľahko automaticky spustiť a vyhodnotiť, vidíme všetky výsledky.
• Krátky návod: [1].
• Bezproblémová podpora v Netbeans 8.
• V Netbeans 11.2 je deklarovaná podpora najnovšej verzie JUnit 5, ale táto nemusí fungovať. Dá sa však použiť aj staršia verzia JUnit 4:
  • Po vytvorení projektu je potrebné vo File -> Project Properties -> Libraries -> Compile -> Classpath zvoliť knižnice JUnit 4.12 (alebo iná verzia 4.x) a Hamcrest 1.3.
  • Ak sa tak urobí ešte pred vytvorením prvej testovacej triedy, NetBeans bude generovať kostry testovacích tried pre verziu JUnit 4.
• Viac o práci s JUnit v Netbeans (návod je trochu zastaralý, ale okrem problému popísaného vyššie zostali podstatné veci nezmenené).

Príklad niekoľkých testov pre funkciu remove vyššie:

package prog;

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

public class ProgTest {

    @Test
    public void testEmpty() { 
        // hladame x v poli dlzky nula
        Object[] array = new Object[0];                  // vstupne pole
        Object x = new Object();
        
        Object[] expected = new Object[0];               // ocakavana spravna odpoved

        boolean result = Prog.remove(array, x);          // spustime testovanu metodu
        assertEquals(false, result);                     // testujeme navratovu hodnotu
        assertTrue(Arrays.equals(expected, array));      // testujeme obsah pola po vykonani metody remove
    }

    @Test
    public void testXOnly() {
        // hladame x v poli obsahujucom iba x
        Object[] array = {7};
        Object x = 7;
  
        Object[] expected = {null};
        
        boolean result = Prog.remove(array, x);
        assertEquals(true, result);
        assertTrue(Arrays.equals(expected, array));
    }

    @Test(expected = NullPointerException.class)
    public void testArrayNull() {
        // Testujeme, ci hodi vynimku ked je pole null
        Object[] array = null;
        Object x = 7;

        boolean result = Prog.remove(array, x);        
    }

    @Test(expected = NullPointerException.class)
    public void testXNull() {
        // Testujeme, ci hodi vynimku ked je x null
        Object[] array = {1, 2, 3, 4, 5};
        Object x = null;

        boolean result = Prog.remove(array, x);        
    }
}

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 pridať výpisy výsledkov, aby sme v prípade chyby videli, čo sa stalo.
• Môžeme triede ProgTest pridať 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 zvyšok semestra 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.