Letný semester, prednáška č. 9

Oznamy

• Počas dnešných cvičení bude prebiehať tretí test. Po dobu jeho riešenia je potrebná fyzická účasť na cvičeniach v miestnosti I-H6.
• Tretiu domácu úlohu treba odovzdať najneskôr do stredy 12. apríla, 9:50.
• Po dnešnej prednáške bude na testovači zverejnené zadanie štvrtej domácej úlohy s termínom odovzdania do pondelka 24. apríla, 9:50, čiže do začiatku poslednej prednášky.

Prehľadávanie s návratom na grafoch: pokračovanie

Hľadanie najväčšej kliky v neorientovanom grafe

Uvažujme teraz neorientované grafy bez slučiek (slučky síce nebudeme zakazovať, ale v našich nasledujúcich úvahách ich budeme ignorovať; najvhodnejšia predstava teda je, že pracujeme s grafmi, ktoré žiadne slučky neobsahujú).

• Klikou (angl. clique) v neorientovanom grafe rozumieme jeho úplný podgraf, čiže podmnožinu K množiny vrcholov grafu takú, že každé dva rôzne vrcholy z K sú navzájom spojené hranou. Veľkosťou kliky rozumieme počet vrcholov kliku tvoriacich. Špeciálne každý vrchol sám o sebe tvorí kliku veľkosti jedna a ľubovoľné dva vrcholy spojené hranou tvoria kliku veľkosti dva.
• V grafoch na nasledujúcom obrázku sú vyznačené kliky veľkosti tri a štyri.

Budeme sa teraz zaoberať problémom nájdenia najväčšej kliky (angl. maximum clique) v neorientovanom grafe.

• Ide o nájdenie kliky s najväčšou veľkosťou spomedzi všetkých klík daného grafu (ak existuje viacero takýchto klík, stačí nájsť ľubovoľnú z nich).
• Pozor na terminológiu: maximálna klika (angl. maximal clique) je ľubovoľná klika, ktorú nemožno pridaním ďalšieho vrcholu rozšíriť na väčšiu kliku. Nie každá maximálna klika ale musí byť aj najväčšia. My sa budeme zaoberať prakticky užitočnejším problémom hľadania najväčších klík.
• Aj pre problém najväčšej kliky je dokázané, že v prípade platnosti určitých hypotéz z teoretickej informatiky preň neexistuje žiaden efektívny algoritmus. Použijeme teda prehľadávanie s návratom – nebudeme ním však teraz konštruovať cesty, ale množiny vrcholov grafu.
• Postupne budeme generovať všetky množiny vrcholov daného grafu ako utriedené spájané zoznamy. Zakaždým sa pokúsime daný vrchol do množiny pridať a rekurzívne pokračovať na ďalší vrchol, následne sa ho pokúsime vynechať a tiež rekurzívne pokračovať na ďalší vrchol. Po vygenerovaní kompletnej množiny zistíme, či ide o kliku; ak áno, porovnáme jej veľkosť s najväčšou doposiaľ nájdenou klikou, ktorú v prípade potreby aktualizujeme.

Trieda MaximumClique realizujúca nájdenie najväčšej kliky v neorientovanom grafe:

package graphs;

import java.util.*;

/**
 * Trieda realizujuca najdenie niektorej spomedzi najvacsich klik v danom neorientovanom grafe.
 */
public class MaximumClique {
    /**
     * Neorientovany graf, v ktorom sa hladanie najvacsej kliky realizuje.
     */
    private UndirectedGraph g;

    /**
     * Zoznam vrcholov najvacsej kliky neorientovaneho grafu g, resp. pocas prehladavania s navratom doposial najvacsej
     * najdenej kliky.
     */
    private LinkedList<Integer> maximumClique;

    /**
     * Zoznam, v ktorom sa pocas prehladavania s navratom budu postupne generovat vsetky (utriedene) mnoziny vrcholov
     * grafu g.
     */
    private LinkedList<Integer> currentVertices;

    /**
     * Konstruktor, ktory pomocou prehladavania s navratom najde najvacsiu kliku v danom neorientovanom grafe.
     * @param g Neorientovany graf, v ktorom sa hladanie najvacsej kliky realizuje.
     */
    public MaximumClique(UndirectedGraph g) {
        this.g = g;
        maximumClique = new LinkedList<>();
        currentVertices = new LinkedList<>();
        search(0);
    }

    /**
     * Rekurzivna metoda realizujuca samotne prehladavnie s navratom a v zozname currentVertices postupne generujuca
     * vsetky (utriedene) mnoziny vrcholov grafu g. Predpoklada sa, ze pred volanim metody reprezentuje zoznam
     * currentVertices nejaku utriedenu podmnozinu mnoziny vrcholov &lbrace;0,...,vertex-1&rbrace;. Metoda search
     * sa najprv pokusi pridat do zoznamu vrchol vertex a vygenerovat vsetky mnoziny obsahujuce vrcholy z tohto zoznamu;
     * nasledne sa pokusi vrchol vertex do zoznamu nepridat a taktiez vygeneruje vsetky taketo mnoziny.
     * Volanie metody pre vertex == 0 teda postupne vygeneruje vsetky utriedene mnoziny vrcholov grafu g. V pripade, ze
     * vertex == g.getVertexCount(), povazuje sa mnozina vrcholov za vygenerovanu a zisti sa, ci ide o najvacsiu
     * doposial najdenu kliku v grafe g.
     * @param vertex Vrchol neorientovaneho grafu g alebo hodnota g.getVertexCount().
     */
    private void search(int vertex) {
        if (vertex == g.getVertexCount()) {
            if (isClique(currentVertices) && currentVertices.size() > maximumClique.size()) {
                maximumClique = new LinkedList<>(currentVertices);
            }
        } else {
            currentVertices.addLast(vertex);
            search(vertex + 1);
            currentVertices.removeLast();
            search(vertex + 1);
        }
    }

    /**
     * Pomocna metoda, ktora zisti, ci dane zoskupenie vrcholov zodpoveda klike v neorientovanom grafe g.
     * @param vertices Zoskupenie vrcholov grafu g.
     * @return         Metoda vrati true prave vtedy, ked vrcholy zoskupenia vertices tvoria kliku v grafe g.
     */
    private boolean isClique(Collection<Integer> vertices) {
        for (int u : vertices) {
            for (int v : vertices) {
                if (u != v && !g.hasEdge(u, v)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Metoda, ktora vrati najdenu najvacsiu kliku v neorientovanom grafe g ako utriedeny zoznam jej vrcholov.
     * @return Nemodifikovatelny zoznam obsahujuci vo vzostupnom poradi vsetky vrcholy najdenej najvacsej kliky.
     */
    public List<Integer> getMaximumClique() {
        return Collections.unmodifiableList(maximumClique);
    }
}

Použitie triedy MaximumClique:

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Zadaj graf:");
    UndirectedGraph g = readUndirectedGraph(scanner, GraphImplementation.LISTS);

    MaximumClique maximumClique = new MaximumClique(g);
    System.out.println("Najvacsia klika v zadanom grafe: " + maximumClique.getMaximumClique());
}

Uvažujme napríklad graf na nasledujúcom obrázku.

Vyššie uvedený program preň vypíše nasledujúci výstup:

Najvacsia klika v zadanom grafe: [0, 1, 2, 4]

Mierne zrýchlenie hľadania najväčšej kliky

Pri hľadaní najväčšej kliky v neorientovanom grafe sme zakaždým prešli cez všetkých 2ⁿ podmnožín n-prvkovej množiny vrcholov grafu. Často je ale možné už behom prehľadávania rozoznať, že rozpracovanú množinu vrcholov nebude možné rozšíriť na najväčšiu kliku. Zapracujeme teda do prehľadávania s návratom v triede MaximumClique dve vylepšenia, ktoré síce nijak nezmenia časovú zložitosť algoritmu v najhoršom prípade, ale pre veľké množstvo grafov jeho vykonávanie podstatne urýchlia:

• Vrchol budeme pridávať do rozpracovanej množiny iba v prípade, že je spojený hranou so všetkými vrcholmi v tejto množine – v opačnom prípade už totiž z tejto množiny, ani po prípadnom pridaní ďalších vrcholov, kliku nikdy nevytvoríme. V takom prípade bude po vygenerovaní kompletnej množiny garantované, že ide o kliku a kontrolu metódou isClique môžeme vypustiť.
• Vrchol tiež budeme pridávať iba v prípade, že je počet jeho susedov – ktorý pre neorientované grafy bez slučiek možno nazvať aj stupňom vrcholu – väčší alebo rovný počtu vrcholov v doposiaľ najväčšej objavenej klike. Ak má totiž najväčšia doposiaľ objavená klika veľkosť k, má pridanie vrcholu do rozpracovanej množiny zmysel iba v prípade, že bude môcť byť súčasťou kliky veľkosti aspoň k+1; každý vrchol, ktorý je súčasťou takejto kliky, má evidentne aspoň k susedov.

Upravená trieda MaximumClique:

package graphs;

import java.util.*;

public class MaximumClique {
    private UndirectedGraph g;
    private LinkedList<Integer> maximumClique;
    private LinkedList<Integer> currentVertices;
    private ArrayList<Integer> neighbourCounts;

    public MaximumClique(UndirectedGraph g) {
        this.g = g;
        maximumClique = new LinkedList<>();
        currentVertices = new LinkedList<>();
        neighbourCounts = new ArrayList<>();
        for (int v = 0; v <= g.getVertexCount() - 1; v++) {
            int neighbourCount = 0;
            for (int u : g.outgoingEdgesDestinations(v)) {
                neighbourCount++;
            }
            neighbourCounts.add(neighbourCount);
        }
        search(0);
    }

    private void search(int vertex) {
        if (vertex == g.getVertexCount()) {
            if (currentVertices.size() > maximumClique.size()) {
                maximumClique = new LinkedList<>(currentVertices);
            }
        } else {
            if (neighbourCounts.get(vertex) >= maximumClique.size() && hasEdgeToEach(vertex, currentVertices)) {
                currentVertices.addLast(vertex);
                search(vertex + 1);
                currentVertices.removeLast();
            }
            search(vertex + 1);
        }
    }

    private boolean hasEdgeToEach(int vertex, Collection<Integer> vertices) {
        for (int v : vertices) {
            if (!g.hasEdge(vertex, v)) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> getMaximumClique() {
        return Collections.unmodifiableList(maximumClique);
    }
}

Cvičenie. Opíšte beh uvedeného programu na grafe obsahujúcom niekoľko vrcholov a žiadnu hranu.

Topologické triedenie grafov

Pod topologickým usporiadaním orientovaného grafu rozumieme úplné usporiadanie množiny jeho vrcholov také, že všetky hrany v grafe vedú „v smere tohto usporiadania”. V pamäti počítača môžeme takéto usporiadanie reprezentovať ako zoznam obsahujúci nejakú permutáciu vrcholov grafu – podmienka z definície topologického usporiadania potom hovorí, že počiatočný vrchol každej hrany grafu je v tomto zozname uvedený skôr, než jej koncový vrchol.

Príklad. Uvažujme orientovaný graf na nasledujúcom obrázku.

Existujú práve štyri topologické usporiadania tohto grafu:

[4, 6, 2, 1, 3, 5, 0]
[6, 4, 2, 1, 3, 5, 0]
[4, 6, 2, 1, 5, 3, 0]
[6, 4, 2, 1, 5, 3, 0]

Pod topologickým triedením grafu rozumieme hľadanie nejakého jeho topologického usporiadania. Z praktického hľadiska ide o relatívne užitočnú úlohu: orientovaný graf môže napríklad reprezentovať časové závislosti – alebo prerekvizity – medzi vykonávanými činnosťami; topologické usporiadanie potom určuje poradie, v ktorom možno vykonať jednotlivé činnosti tak, aby boli vždy splnené všetky prerekvizity vykonávanej činnosti.

Orientovaný graf nazveme acyklickým, ak v ňom neexistuje žiadna orientovaná kružnica, t. j. cyklus (alebo ekvivalentne žiaden uzavretý sled nenulovej dĺžky).

Veta. Topologické usporiadanie orientovaného grafu existuje práve vtedy, keď je tento graf acyklický.

Dôkaz. Uvažujme najprv orientovaný graf, ktorý nie je acyklický – obsahuje teda sled v₀,...,v_n taký, že n ≥ 1 a v_n = v₀. Za účelom sporu predpokladajme, že existuje topologické usporiadanie tohto grafu. Vrchol v₀ potom musí byť v zozname prislúchajúcom k tomuto usporiadaniu uvedený skôr, než každý z vrcholov v₁,...,v_n; a keďže v_n = v₀, musí tam byť uvedený aj skôr, než on sám: spor.

Indukciou vzhľadom na počet vrcholov teraz dokážeme, že každý orientovaný acyklický graf má aspoň jedno topologické usporiadanie. Graf o jedinom vrchole v bez slučky má evidentne topologické usporiadanie. Predpokladajme teraz, že tvrdenie platí pre všetky orientované acyklické grafy veľkosti n a uvažujme ľubovoľný orientovaný acyklický graf veľkosti n+1. Ten musí obsahovať najmenej jeden vrchol, z ktorého nevychádza žiadna hrana – v opačnom prípade by totiž každý sled bolo možné predĺžiť na dlhší, pričom v slede dĺžky n+1 by sa už podľa Dirichletovho princípu nutne musel niektorý z vrcholov zopakovať a dostali by sme tak uzavretý sled nenulovej dĺžky (spor). Nech má túto vlastnosť vrchol u: z vrcholu u teda nevychádza žiadna hrana. Podľa indukčného predpokladu potom existuje topologické usporiadanie grafu, ktorý z uvažovaného grafu získame odstránením vrcholu u a všetkých do neho vedúcich hrán (ten má totiž n vrcholov a zjavne musí byť tiež acyklický). Ak tomuto usporiadaniu zodpovedá postupnosť vrcholov v₁,...,v_n, zodpovedá postupnosť vrcholov v₁,...,v_n,u topologickému usporiadaniu uvažovaného grafu veľkosti n+1. □

Topologické triedenie teda môžeme chápať ako úlohu na orientovaných acyklických grafoch.

Poznámka: matematicky o niečo výstižnejšia ekvivalentná definícia topologického usporiadania využíva fakt, že orientované acyklické grafy sú práve tie orientované grafy bez slučiek, ktorých reflexívno-tranzitívny uzáver možno chápať ako čiastočné usporiadanie na množine vrcholov (neexistencia cyklu zodpovedá antisymetrii reflexívno-tranzitívneho uzáveru). V tomto zmysle teda každý orientovaný acyklický graf jednoznačne určuje čiastočné usporiadanie ⪯ na množine vrcholov grafu. Topologické usporiadanie je potom ľubovoľné úplné usporiadanie ≤ na tej istej množine vrcholov také, že ⪯ ⊆ ≤.

Algoritmus topologického triedenia

Napíšeme teraz statickú metódu topologicalSort, ktorá realizuje topologické triedenie daného orientovaného grafu.

• Vstupom metódy je orientovaný graf.
• V prípade, že je tento graf acyklický, vráti metóda na výstupe zoznam vrcholov zodpovedajúci nejakému jeho topologickému usporiadaniu.
• V opačnom prípade metóda vráti na výstupe referenciu null.

Samotný algoritmus si bude v zozname unprocessedPredecessors pre každý vrchol pamätať počet vrcholov, z ktorých do daného vrcholu vedie hrana a ktoré ešte neboli pridané do topologického usporiadania. Ak je tento počet pre nejaký vrchol nulový, možno ho pridať ako ďalší vrchol do topologického usporiadania. Vrcholy s touto vlastnosťou sa budú udržiavať v rade ready (rovnako dobre ako rad by sme mohli použiť aj inú dátovú štruktúru).

public static List<Integer> topologicalSort(DirectedGraph g) {
    /* Inicializacia: */
    int n = g.getVertexCount();
    List<Integer> unprocessedPredecessors = new ArrayList<>();
    for (int v = 0; v <= n - 1; v++) {
        unprocessedPredecessors.add(0);
    }
    for (int v = 0; v <= n - 1; v++) {
        for (int successor : g.outgoingEdgesDestinations(v)) {
            unprocessedPredecessors.set(successor, unprocessedPredecessors.get(successor) + 1);
        }
    }
    Queue<Integer> ready = new LinkedList<>();
    for (int v = 0; v <= n - 1; v++) {
        if (unprocessedPredecessors.get(v) == 0) {
            ready.add(v);
        }
    }
    List<Integer> result = new LinkedList<>();

    /* Samotne topologicke triedenie: */
    while (!ready.isEmpty()) {
        int vertex = ready.remove();
        result.add(vertex);
        for (int successor : g.outgoingEdgesDestinations(vertex)) {
            unprocessedPredecessors.set(successor, unprocessedPredecessors.get(successor) - 1);
            if (unprocessedPredecessors.get(successor) == 0) {
                ready.add(successor);
            }
        }
    }

    if (result.size() == n) {
        return result;
    } else {
        return null;
    }
}

Topologické triedenie na báze prehľadávania do hĺbky

Ukážme si ešte alternatívnu metódu topologického triedenia grafu, založenú na nasledujúcej úprave prehľadávania do hĺbky:

• Okrem zoznamu visited si budeme udržiavať aj zoznam finished, v ktorom si pre každý vrchol grafu budeme pamätať, či prehľadávanie v ňom započaté už skončilo.
• Pri objavení vrcholu teda nastavíme na true príslušnú položku zoznamu visited a po vykonaní všetkých rekurzívnych volaní metódy search pre susedov daného vrcholu nastavíme na true aj príslušnú položku zoznamu finished.

Takto upraveným prehľadávaním do hĺbky môžeme postupne prechádzať celý graf – zakaždým si zvolíme nenavštívený vrchol, pre ktorý spustíme rekurzívne prehľadávanie do hĺbky; ak po tomto prehľadávaní ostanú nenavštívené vrcholy, vyberieme si ďalší vrchol, pre ktorý urobíme to isté a takto pokračujeme, až kým prehľadáme všetky vrcholy grafu. V každom momente vykonávania tohto algoritmu pritom existujú tri množiny vrcholov:

• Už spracované vrcholy, pre ktoré sú rovné true príslušné položky v zozname visited aj v zozname finished.
• „Rozrobené” vrcholy, pre ktoré je príslušná položka v zozname visited rovná true, ale príslušná položka v zozname finished je rovná false.
• Ešte nenavštívené vrcholy, pre ktoré sú príslušné položky v zozname visited aj v zozname finished rovné false.

Orientovaný graf pritom obsahuje cyklus práve vtedy, keď pri opísanom algoritme v rámci rekurzívneho prehľadávania z niektorého vrcholu narazíme na „rozrobený” vrchol v.

• Ak totiž takáto situácia nastane, objavili sme vrchol v v rámci prehľadávania z neho samého. Príslušná vetva prehľadávania do hĺbky tak zodpovedá uzavretému sledu nenulovej dĺžky: graf obsahuje cyklus.
• Ak naopak graf obsahuje cyklus, nutne musí existovať nejaký vrchol v, ktorý spomedzi všetkých vrcholov tohto cyklu navštívime pri prehľadávaní ako prvý. V rámci rekurzívneho prehľadávania do hĺbky z vrcholu v potom nutne navštívime všetky vrcholy tohto cyklu, a teda aj nejaký vrchol u, z ktorého vedie hrana do vrcholu v. Vo vrchole u potom prehľadávame všetkých následníkov, medzi ktorými musí byť aj „rozrobený” vrchol v.

Ak teda uvedená situácia v rámci opísaného algoritmu nikdy nenastane, nutne musí ísť o orientovaný acyklický graf.

Uvažujme teraz situáciu, keď v orientovanom acyklickom grafe skončí prehľadávanie do hĺbky z vrcholu v skôr, než prehľadávanie do hĺbky z vrcholu u. Dokážeme, že v takom prípade v grafe nemôže viesť žiadna cesta z vrcholu v do vrcholu u.

• Na začiatku prehľadávania z vrcholu v môže byť vrchol u nenavštívený alebo „rozrobený”.
• V prípade, že je „rozrobený”, musí nutne viesť cesta z vrcholu u do vrcholu v; existencia cesty z v do u by tak odporovala predpokladu acyklickosti grafu.
• V prípade, že je vrchol u ešte nenavštívený a existuje cesta z v do u, musí táto cesta na začiatku prehľadávania z vrcholu v pozostávať (s výnimkou samotného vrcholu v) výhradne z nenavštívených vrcholov. Keby bol totiž niektorý z týchto vrcholov „rozrobený”, dostali by sme spor rovnako, ako v predchádzajúcom prípade. Cesta teda pozostáva (okrem vrcholu v na jej začiatku) iba z nenavštívených a spracovaných vrcholov a ľahko vidieť, že keby bol niektorý z vrcholov na ceste už spracovaný, museli by byť spracované aj všetky ďalšie vrcholy cesty – vrátane vrcholu u. Existencia cesty z v do u pozostávajúcej z nenavštívených vrcholov ale znamená, že vrchol u objavíme v rámci prehľadávania z vrcholu v a prehľadávanie z vrcholu u tak skončí skôr, než prehľadávanie z vrcholu v: spor s predpokladom.

Ak teda v orientovanom acyklickom grafe ukončíme prehľadávanie z nejakého vrcholu v, môžeme ho pridať na začiatok zoznamu reprezentujúceho topologické usporiadanie – všetky hrany z vrcholu v totiž musia viesť do vrcholov, ktoré už v tomto zozname sú. Nasledujúci algoritmus toto pozorovanie pre orientované acyklické grafy kombinuje s detekciou cyklov opísanou vyššie – vo výsledku ho teda možno použiť pre ľubovoľný orientovaný graf.

package graphs;

import java.util.*;

/**
 * Trieda realizujuca topologicke triedenie pomocou prehladavania do hlbky.
 */
public class TopologicalSort {
    /**
     * Orientovany graf, v ktorom sa topologicke triedenie realizuje.
     */
    private DirectedGraph g;

    /**
     * Vysledne topologicke usporiadanie alebo jeho cast.
     */
    private LinkedList<Integer> topologicalOrder;

    /**
     * Pole, v ktorom si pre kazdy vrchol pamatame, ci bol prehladavanim do hlbky navstiveny.
     */
    private ArrayList<Boolean> visited;

    /**
     * Pole, v ktorom si pre kazdy vrchol pamatame, ci bolo prehladavanie z neho ukoncene.
     */
    private ArrayList<Boolean> finished;

    /**
     * Po vykonani konstruktora bude true prave vtedy, ked je graf g acyklicky.
     */
    private boolean acyclic = true;

    /**
     * Konstruktor, ktory pomocou prehladavania do hlbky najde niektore z topologickych usporiadani daneho grafu, resp.
     * v pripade grafov obsahujucich cyklus nastavi premennu acyclic na false.
     * @param g Graf, v ktorom sa topologicke triedenie realizuje.
     */
    public TopologicalSort(DirectedGraph g) {
        this.g = g;
        int n = g.getVertexCount();
        topologicalOrder = new LinkedList<>();
        visited = new ArrayList<>();
        finished = new ArrayList<>();

        for (int v = 0; v <= n - 1; v++) {
            visited.add(false);
            finished.add(false);
        }

        for (int v = 0; v <= n - 1; v++) {
            if (!visited.get(v)) {
                search(v);
            }
        }
    }

    /**
     * Metoda realizujuca samotne prehladavanie do hlbky z vrcholu vertex.
     * @param vertex Vrchol, z ktoreho sa prehladavanie do hlbky spusta.
     */
    private void search(int vertex) {
        visited.set(vertex, true);
        for (int successor : g.outgoingEdgesDestinations(vertex)) {
            if (visited.get(successor) && !finished.get(successor)) {
                acyclic = false;
            }
            if (!visited.get(successor)) {
                search(successor);
            }
        }
        finished.set(vertex, true);
        topologicalOrder.addFirst(vertex);
    }

    /**
     * Metoda, ktora vrati najdene topologicke usporiadanie grafu.
     * @return Topologicke usporiadanie grafu ako nemodifikovatelny zoznam vrcholov. V pripade, ze graf nie je
     *         acyklicky, vrati sa na vystupe referencia null.
     */
    public List<Integer> getTopologicalOrder() {
        if (acyclic) {
            return Collections.unmodifiableList(topologicalOrder);
        } else {
            return null;
        }
    }

    /**
     * Metoda, ktora vrati informaciu o tom, ci je graf g acyklicky.
     * @return Vrati booleovsku hodnotu true prave vtedy, ked je graf g acyklicky.
     */
    public boolean isAcyclic() {
        return acyclic;
    }
}

Úlohy na ohodnotených grafoch

Po zvyšok tejto prednášky sa budeme zaoberať ohodnotenými grafmi. Pôjde o rozšírenie grafov, pri ktorom má každá hrana priradenú nejakú hodnotu – v našom prípade bude touto hodnotou reálne číslo. Pre orientované ohodnotené grafy napíšeme rozhranie WeightedDirectedGraph a triedu WeightedSuccessorListsDirectedGraph reprezentujúcu tieto grafy pomocou zoznamov následníkov (podobným spôsobom ako na minulých prednáškach by sme však mohli napísať aj triedy ako WeightedAdjacencyMatrixDirectedGraph, WeightedAdjacencyListsUndirectedGraph a podobne).

Rozhranie pre ohodnotené grafy (WeightedDirectedGraph)

package graphs;

/**
 * Trieda reprezentujuca ohodnotenu orientovanu hranu.
 */
public class WeightedDirectedEdge extends DirectedEdge {
    private double weight;

    public WeightedDirectedEdge(int from, int to, double weight) {
        super(from, to);
        this.weight = weight;
    }

    public double getWeight() {
        return weight;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return getClass() == o.getClass() &&
                getFrom() == ((WeightedDirectedEdge) o).getFrom() &&
                getTo() == ((WeightedDirectedEdge) o).getTo() &&
                getWeight() == ((WeightedDirectedEdge) o).getWeight();
    }

    @Override
    public int hashCode() {
        return Double.valueOf(weight).hashCode() + 31 * super.hashCode();
    }
}

package graphs;

public interface WeightedDirectedGraph extends DirectedGraph {
    /**
     * Metoda, ktora vrati vsetky ohodnotene hrany vychadzajuce z vrcholu vertex reprezentovaneho ohodnoteneho grafu.
     * @param vertex Vrchol ohodnoteneho grafu.
     * @return       Ohodnotene hrany vychadzajuce z vrcholu vertex.
     */
    Iterable<WeightedDirectedEdge> outgoingWeightedDirectedEdges(int vertex);
}

Orientované ohodnotené grafy pomocou zoznamov následníkov (WeightedSuccessorListsDirectedGraph)

Triedu WeightedSuccessorListsDirectedGraph reprezentujúcu ohodnotený orientovaný graf pomocou zoznamov následníkov napíšeme jednoduchým rozšírením príslušnej triedy SuccessorListsDirectedGraph pre neohodnotené grafy. Navyše si len pre každý vrchol budeme pamätať zoznam z neho vychádzajúcich ohodnotených hrán.

package graphs;

import java.util.*;

public class WeightedSuccessorListsDirectedGraph extends SuccessorListsDirectedGraph implements WeightedDirectedGraph {
    private ArrayList<ArrayList<WeightedDirectedEdge>> outgoingWeightedEdges;

    public WeightedSuccessorListsDirectedGraph(int vertexCount,
                                               Collection<? extends WeightedDirectedEdge> weightedDirectedEdges) {
        super(vertexCount, weightedDirectedEdges);
        outgoingWeightedEdges = new ArrayList<>();
        for (int v = 0; v <= vertexCount - 1; v++) {
            outgoingWeightedEdges.add(new ArrayList<>());
        }
        for (WeightedDirectedEdge weightedDirectedEdge : weightedDirectedEdges) {
            outgoingWeightedEdges.get(weightedDirectedEdge.getFrom()).add(weightedDirectedEdge);
        }
    }

    @Override
    public Iterable<WeightedDirectedEdge> outgoingWeightedDirectedEdges(int vertex) {
        if (!hasVertex(vertex)) {
            throw new IllegalArgumentException("Nonexistent vertex.");
        }
        return Collections.unmodifiableList(outgoingWeightedEdges.get(vertex));
    }
}

Hľadanie najdrahšej cesty v ohodnotenom grafe

Pod cenou cesty v ohodnotenom grafe budeme rozumieť súčet ohodnotení jej hrán. Podobne ako najdlhšiu cestu v neohodnotenom grafe potom možno najdrahšiu cestu medzi dvoma vrcholmi ohodnoteného grafu nájsť pomocou prehľadávania s návratom.

package graphs;

import java.util.*;

/**
 * Trieda realizujuca najdenie nadrahsej ohodnotenej cesty v ohodnotenom grafe z daneho pociatocneho do daneho koncoveho
 * vrcholu.
 */
public class CostliestWeightedPath {
    /**
     * Ohodnoteny graf, v ktorom sa hladanie najdrahsej cesty realizuje.
     */
    private WeightedDirectedGraph g;

    /**
     * Koncovy vrchol hladanej najdrahsej cesty.
     */
    private int to;

    /**
     * Cena vygenerovanej casti cesty.
     */
    private double cost;

    /**
     * Cena doposial najdrahsej najdenej cesty z vrcholu from do vrcholu to.
     */
    private double maxCost;

    /**
     * Zoznam, v ktorom sa postupne budu cesty generovat.
     */
    private LinkedList<Integer> path;

    /**
     * Doposial najdrahsia najdena cesta z vrcholu from do vrcholu to.
     */
    private LinkedList<Integer> costliestWeightedPath;

    /**
     * Informacie o navstiveni jednotlivych vrcholov pri prehladavani s navratom.
     */
    private ArrayList<Boolean> visited;

    /**
     * Konstruktor, ktory najde najdrahsiu ohodnotenu cestu medzi danymi dvoma vrcholmi daneho ohodnoteneho grafu.
     * @param g    Graf, v ktorom sa hladanie ciest realizuje.
     * @param from Pociatocny vrchol.
     * @param to   Koncovy vrchol.
     */
    public CostliestWeightedPath(WeightedDirectedGraph g, int from, int to) {
        this.g = g;
        this.to = to;

        visited = new ArrayList<>();
        for (int v = 0; v <= g.getVertexCount() - 1; v++) {
            visited.add(false);
        }

        cost = 0;
        path = new LinkedList<>();
        path.add(from);
        visited.set(from, true);
        search();
    }

    /**
     * Metoda realizujuca samotne prehladavanie s navratom.
     */
    private void search() {
        if (path.getLast() == to) {
            if (costliestWeightedPath == null || cost > maxCost) {
                maxCost = cost;
                costliestWeightedPath = new LinkedList<>(path);
            }
        } else {
            for (WeightedDirectedEdge weightedDirectedEdge : g.outgoingWeightedDirectedEdges(path.getLast())) {
                int successor = weightedDirectedEdge.getTo();
                double weight = weightedDirectedEdge.getWeight();
                if (!visited.get(successor)) {
                    visited.set(successor, true);
                    path.addLast(successor);
                    cost += weight;
                    search();
                    cost -= weight;
                    path.removeLast();
                    visited.set(successor, false);
                }
            }
        }
    }

    /**
     * Metoda, ktora vrati najdenu najdrahsiu ohodnotenu cestu.
     * @return Jedna z najdrahsich ohodnotenych ciest z from do to ako nemodifikovatelny zoznam. V pripade, ze ziadna
     *         cesta medzi vrcholmi from a to neexistuje, vrati sa na vystupe referencia null.
     */
    public List<Integer> getCostliestWeightedPath() {
        if (costliestWeightedPath != null) {
            return Collections.unmodifiableList(costliestWeightedPath);
        } else {
            return null;
        }
    }
}

Použitie tejto triedy:

package graphs;

import java.util.*;

public class Trieda {

    public static WeightedDirectedGraph readWeightedDirectedGraph(Scanner s) {
        int n = s.nextInt();
        int m = s.nextInt();
        ArrayList<WeightedDirectedEdge> weightedDirectedEdges = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            double weight = s.nextDouble();
            weightedDirectedEdges.add(new WeightedDirectedEdge(u, v, weight));
        }
        return new WeightedSuccessorListsDirectedGraph(n, weightedDirectedEdges);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Zadaj ohodnoteny graf:");
        WeightedDirectedGraph g = readWeightedDirectedGraph(scanner);
        System.out.println("Zadaj pociatocny a koncovy vrchol:");
        int from = scanner.nextInt();
        int to = scanner.nextInt();

        CostliestWeightedPath costliestWeightedPath = new CostliestWeightedPath(g, from, to);
        List<Integer> result = costliestWeightedPath.getCostliestWeightedPath();
        if (result != null) {
            System.out.println("Najdrahsia cesta: " + result);
        } else {
            System.out.println("Ziadna cesta neexistuje.");
        }
    }
}

Najlacnejšie cesty v ohodnotených grafoch

Poznamenajme, že najlacnejšia cesta v ohodnotenom grafe sa vo všeobecnosti nedá nájsť prehľadávaním do šírky:

• Ak sú ohodnoteniami prirodzené čísla, možno hranu ohodnotenú číslom k reprezentovať postupnosťou k nadväzujúcich hrán a aplikovať algoritmus pre najkratšie cesty v neohodnotených grafoch. Pokiaľ však nemáme zaručené, že sú ohodnotenia hrán malé, ide o extrémne neefektívny prístup.
• Najlacnejšiu cestu samozrejme možno hľadať aj prehľadávaním s návratom, podobne ako cestu najdrahšiu. To je však tiež veľmi neefektívne (pri najdrahšej ceste to až tak nevadí, keďže efektívny algoritmus s najväčšou pravdepodobnosťou neexistuje).
• „Rozumné” algoritmy na hľadanie najlacnejšej cesty v ohodnotenom grafe sa preberajú napríklad v rámci predmetu Tvorba efektívnych algoritmov. Tieto predpokladajú neexistenciu cyklov so zápornou cenou (čo je v praxi zmysluplný predpoklad), a teda v skutočnosti hľadajú najlacnejšie sledy. V prípade možnej existencie záporne ohodnotených cyklov efektívny algoritmus, rovnako ako pri najdrahšej ceste, s najväčšou pravdepodobnosťou neexistuje.

Zhrnutie prebratých grafových algoritmov

Väčšina grafových algoritmov (s výnimkou prvého algoritmu pre topologické triedenie), s ktorými sme sa v rámci posledných niekoľkých prednášok stretli, bola založená na niektorej z nasledujúcich troch techník:

• Prehľadávanie do hĺbky (angl. depth-first search).
• Prehľadávanie do šírky (angl. breadth-first search).
• Prehľadávanie s návratom (angl. backtracking).

Prvé dve z týchto techník sú pomerne efektívne – je pri nich zaručené, že žiadna hrana nebude pri „objavovaní” nových vrcholov použitá viac, než raz. To znamená, že časová zložitosť týchto algoritmov je rádovo O(n + m), kde n je počet vrcholov a m je počet hrán grafu.

Prehľadávanie s návratom je naopak extrémne neefektívna technika prehľadávajúca všetky možnosti, ktorých vo všeobecnosti môže byť veľmi veľa. Dá sa teda aplikovať iba na malé vstupy a používa sa najmä vtedy, keď efektívny algoritmus pre danú úlohu neexistuje alebo nie je známy.