Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Prednáška 34

Z Programovanie
Prejsť na: navigácia, hľadanie

Oznamy

  • Posledná DÚ zverejnená, odovzdávajte do 16.5. do 22:00
  • V prípade záujmu o nepovinný projekt si vyberte tému do stredy (odovzdajte na testovači)
  • Projekty bude treba odovzdať pravdepodobne do nedele 20.5. 22:00, predvádzanie upresníme
  • Piatok 18.5. o 13:00 v posluchárni B záverečná písomka
  • Termíny skúšok
    • Streda 23.5. 9:00 v H6 (riadny)
    • Štvrtok 7.6. 9:00 v H6 (riadny alebo 1. opravný)
    • Utorok 20.6. 9:00 v H6 (1. alebo 2. opravný)
    • Koncom júna bude ešte 2. opravný termín, dátum upresníme neskôr
  • Prípadné konflikty s dátumami písomky alebo skúšok nám dajte vedieť čím skôr
  • Budúci pondelok na prednáške dôležité pokyny k skúške a testu (príďte načas)

Opakovanie

Reprezentácia grafov

Neorientovaný graf s vrcholmi očíslovanými 0,1,...,n-1.

  • Príklad: V={0,...,6}, E={{0,5},{1,2},{2,3},{1,3},{3,4}}

Interface Graph

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

Matica susednosti (adjacency matrix), trieda AdjMatrixGraph

  • Matica nxn napr typu boolean
  • Políčko a[i][j]=true ak {i,j} je hrana
   0 1 2 3 4 5 6
0  F F F F F T F
1  F F T T F F F
2  F T F T F F F
3  F T T F T F F
4  F F F T F F F
5  T F F F F F F
6  F F F F F F F

Zoznamy susedov (adjacency lists), trieda AdjListsGraph

  • Pre každý vrchol zoznam jeho susedov
  • Uložíme ako pole potrebnej veľkosti alebo spájaný zoznam (ArrayList, LinkedList)
  • Lepšia reprezentácia pre väčšinu algoritmov, obzvlášť ak je graf riedky, t.j. má pomerne málo hrán
0: 5
1: 2,3
2: 1,3
3: 1,2,4
4: 3
5: 0
6:

Prehľadávanie do hĺbky, komponenty súvislosti

  • Vrcholy neorientovaného grafu vieme rozdeliť na komponenty súvislosti.
  • V grafe existuje cesta z vrcholu u do vrcholu v práve vtedy, keď sú v tom istom komponente súvislosti.
  • Mnohé úlohy vieme formulovať ako zisťovanie komponentov súvislosti (videli sme valec lesom, šachového koňa, červíka v bludisku).


  • Prehľadávanie do hĺbky začne z jedného vrcholu a rekurzívne prehľadá celý komponent.
  • Môžeme teda postupným volaním prehľadávania očíslovať komponenty 0,1,...,k-1 a pre každý vrchol uložiť číslo jeho komponentu.
  • Potom dva vrcholy sú spojené cestou práve vtedy, keď majú rovnaké číslo komponentu.
  • Dáta potrebné počas rekurzie a výsledky si uložíme do pomocnej triedy.
/** Trieda obsahujúca rozdelenie vrcholov grafu do komponentov súvislosti */
class Components {

    /** Pre každý vrchol číslo jeho komponentu 0..počet komponentov-1 */
    private int[] componentId;
    /** počet komponentov grafu */
    private int numComponents;
    /** samotný graf */
    private Graph g;

    /** Konštruktor, ktorý dostane graf a prehľadávaním do hĺbky
     * hľadá komponenty súvislosti */
    public Components(Graph g) {
        this.g = g;  // uloz graf
        numComponents = 0;  // inicializuj pocet komponentov
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        // vytvor pole cisel komponentov a inicializuj na -1 - nevyfarbene
        componentId = new int[n];
        for (int i = 0; i < n; i++) {
            componentId[i] = -1;
        }
        // prechadzaj cez vrcholy a ak najdes nevyfarbeny, spusti prehladavanie
        for (int i = 0; i < n; i++) {
            if (componentId[i] == -1) {
                search(i, numComponents); // vyfarbi cislom numComponents
                numComponents++;          // zvys numComponents
            }
        }
    }

    /** Pomocná rekurzívna metóda používaná v konštruktore na vyfarbenie
     * jedného komponentu číslom id. */
    private void search(int vertex, int id) {
        componentId[vertex] = id;
        for (int neighbor : g.adjVertices(vertex)) {
            if (componentId[neighbor] == -1) {
                search(neighbor, id); // navstivime ho rekurzivne
            }
        }
    }

    /** Vráti true ak vrcholy from a to sú v tom istom komponente */
    public boolean areConnected(int from, int to) {
        return componentId[from] == componentId[to];
    }

    /** Vráti počet komponentov grafu */
    public int getNumberOfComponents() {
        return numComponents;
    }
}

Najkratšie cesty, prehľadávanie do šírky (breath-first search, BFS)

Graf s kostrou najkratších ciest pre vrchol 0
  • Ak sú dva vrcholy v jednom komponente súvislosti, mohli by sme chcieť vypísať aj cestu, ktorá ich spája
  • Najlepšie najkratšiu cestu, teda takú, ktorá obsahuje najmenej hrán
  • To nám prehľadávanie do hĺbky nenájde, použijeme prehľadávanie do šírky
  • Začneme v nejakom vrchole s
  • V prehľadávaní do šírky najprv navštívime všetky vrcholy vo vzdialenosti 1 od s, potom vo vzdialenosti 2, ...
  • Pre každý navštívený vrchol v spočítame jeho vzdialenosť od s aj predposledný vrchol na najkratšej ceste z s do v
  • Hrany medzi v a pred[v] tvoria strom (kostru grafu, ak je súvislý)
  • Ak chceme vypísať cestu, po strome sa pohybujeme smerom k jeho koreňu vo vrchole s
  • Algoritmus používa rad (frontu, queue), do ktorej dáva vrcholy, ktoré už majú známu vzdialenosť, ale ešte sme nepozreli ich susedov
  • V rade sú v každej chvíli vrcholy najviac dvoch vzdialeností od s: najprv nejaké vrcholy vo vzdialenosti d, potom nejaké vrcholy vo vzdialenosti d+1
  • Zložitosť je tiež O(n+m), ak použijeme zoznamy susedov
/** Trieda, ktorá reprezentuje najkratšie cesty a vzdialenosti
 * z jedného vrchola do ostatných. */
class ShortestPaths {

    /** Graf, v ktorom rátame cesty */
    private Graph g;
    /** Startovaci vrchol, z ktoreho ratame najkratsie cesty */
    private int start;
    /** Pre kazdy vrchol v grafe vzdialenost od startu
     * alebo -1 ak je v inom komponente. */
    private int[] dist;
    /** Pre kazdy vrchol u predchadzajuci vrchol na ceste zo start do u */
    private int[] prev;

    /** Konstruktor, ktory dostane graf a startovaci vrchol a najde najkratsei cesty */
    public ShortestPaths(Graph g, int start) {
        this.g = g;
        this.start = start;
        int n = g.getNumberOfVertices();
        // inicializacia poli - vyplnime -1
        dist = new int[n];
        prev = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = -1;
            prev[i] = -1;
        }

        // prehladavanie do sirky
        // vytvorime rad a vlozime do neho startovaci vrchol
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.addLast(start);
        dist[start] = 0;  // sam od seba ma vzdialenost 0

        while (!queue.isEmpty()) {
            // vyberieme prvok na zaciatku radu
            int vertex = queue.removeFirst();
            // prejdeme cez jeho susedov a ak este neboli navstiveni
            // urcime im vzdialenost a pridame ich do radu
            for (int neighbor : g.adjVertices(vertex)) {
                if (dist[neighbor] < 0) {
                    dist[neighbor] = dist[vertex] + 1;
                    prev[neighbor] = vertex;
                    queue.addLast(neighbor);
                }
            }
        }
    }

    /** Je vrchol vertex spojeny so startovacim vrcholom? */
    public boolean isConnected(int vertex) {
        return dist[vertex] >= 0;
    }

    /** Vrati vzdialenost vrcholu vertex od starovacieho vrcholu.
     * Ak su v roznych komponentoch, vrati -1. */
    public int distance(int vertex) {
        return dist[vertex];
    }

    /** Vrati najkratsiu cestu zo startovacieho vrcholu
     * do vrcholu vertex (postupnost vrcholov, cez ktore cesta ide).
     * Ak su v roznych komponentoch, vrati null. */
    public int[] shortestPath(int vertex) {
        if (!isConnected(vertex)) {  // vybav rozne koponenty
            return null;
        }
        int[] path = new int[dist[vertex] + 1];  // alokujeme cestu
        int v = vertex;   //posledny vrchol bude vertex
        path[dist[vertex]] = v;
        for (int i = dist[vertex] - 1; i >= 0; i--) { // odzadu pridavame vrcholy
            v = prev[v];      // posunieme sa na predchadzajuci vrchol na ceste
            path[i] = v;
        }
        return path;
    }
}

Opakovanie: prehľadávanie s návratom (backtracking)

  • Prehľadávanie s návratom sme videli minulý semester napr. na problém 8 dám
  • Riešenie úlohy je nejaká postupnosť, rekurzívne skúšame pridať všetky možnosti ďalšieho prvku postupnosti
  • Prehľadávame exponenciálny počet možností, algoritmus môže byť veľmi pomalý
  • Snažíme sa ukončiť prehľadávanie vždy, keď už nie je šanca dosiahnuť platné riešenie

Príklad: vypisujeme všetky variácie bez opakovania dĺžky k z prvkov {0..n-1}

package prog;

import java.util.Scanner;

public class Prog {

    static void vypis(int[] a) {
        for (int x : a) {
            System.out.print(" " + x);
        }
        System.out.println();
    }

    static void generuj(int[] a, boolean[] bolo, int i, int n) {
        /* v poli a dlzky k mame prvych i cifier,
         * v poli bolo mame zaznamenane, ktore cifry su uz pouzite,
         * chceme vygenerovat vsetky moznosti
         * poslednych k-i cifier */
        if (i == a.length) {
            vypis(a);
        } else {
            for (int x = 0; x < n; x++) {
                if (!bolo[x]) {
                    a[i] = x;
                    bolo[x] = true;
                    generuj(a, bolo, i + 1, n);
                    bolo[x] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        int k, n;
        Scanner s = new Scanner(System.in);
        k = s.nextInt();
        n = s.nextInt();
        int[] a = new int[k];
        boolean[] bolo = new boolean[n];
        for (int i = 0; i < n; i++) {
            bolo[i] = false;
        }
        generuj(a, bolo, 0, n);
    }
}

Prehľadávanie s návratom na grafoch

  • Veľa úloh na grafoch nevieme riešiť rýchlymi algoritmami, backtrackingom vieme spočítať odpoveď aspoň pre malé vstupy

Hľadanie ciest dĺžky k

  • Cesta v grafe je postupnosť vrcholov v_{0},v_{1},...,v_{k} taká, že každé dva za sebou idúce vrcholy v_{i} a v_{{i+1}} sú spojené hranou a žiaden vrchol sa na ceste neopakuje. Dĺžka tejto cesty je k, t.j. počet hrán na ceste.
  • Prehľadávaním do šírky vieme nájsť najkratšiu cestu z u do v.
  • Čo ak chceme nájsť cestu z u do v dĺžky presne k?

Príklad použitia: vypisujeme cesty rôznych dĺžok medzi vrcholmi from=0 a to=3:

       for (int length = 1; length < g.getNumberOfVertices(); length++) {
            System.out.println("Cesty dlzky " + length + ":");
            FixedLengthPaths p = new FixedLengthPaths(g, 0, 3, length);
        }
PROG-P36-graf1.png

Výstup pre graf s V={0,...,4} a E={{0,1},{0,2},{0,3},{1,2},{2,3},{2,4},{3,4}}

Cesty dlzky 1:
 0 3
Cesty dlzky 2:
 0 2 3
Cesty dlzky 3:
 0 1 2 3
 0 2 4 3
Cesty dlzky 4:
 0 1 2 4 3
  • Opäť použijeme pomocnú triedu na ukladanie všetkých premenných potrebných v rekurzii
    • Pole path s práve vyrábanou cestou
    • Pole visited, v ktorom máme poznačené, ktoré vrcholy sú použité na ceste
    • Vstupné dáta: graf, 2 vrcholy, požadovaná dĺžka
  • V rekurzii skúšame k ceste pridať ďalší vrchol, pričom vyberáme z vrcholov susedných s posledným vrcholom na ceste
  • Keď nájdeme cestu požadovanej dĺžky, ktorá končí v cieľovom vrchole, cestu vypíšeme
/** Trieda, ktora umoznuje najst vsetky cesty zadanej
 * dlzky medzi dvoma danymi vrcholmi. */
class FixedLengthPaths {

    /** samotny graf */
    private Graph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** pozadovana dlzka cesty */
    private int length;
    /** tvorena cesta */
    private int[] path;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a pozadovanu dlzku cesty a rovno aj spusti rekurzivne vyhladavanie
     * a vypisuje vysledky. */
    public FixedLengthPaths(Graph g, int from, int to, int length) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        this.length = length;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj polia visited a path
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[length + 1];  // length hran, teda length+1 vrcholov
        search(0, from); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda ako i-ty vrchol cesty ulozi vertex a
     * potom skusa vsetky moznosti ako sa na length-i krokov
     * dostat do cieloveho vrcholu. */
    private void search(int i, int vertex) {
        // ulozime vrchol do cesty a poznacime ho ako pouzity
        path[i] = vertex;
        visited[vertex] = true;
        // ak uz mame cestu dlzky length, pozrieme,
        // ci konci v spravnom vrchole a vypiseme
        if (i == length) {
            if (vertex == to) {
                printPath();
            }
        } else {
            // ak este nemame cestu dlzky length,
            // pozrieme na susedov aktualneho vrcholu vertex
	    for(int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, preskumame ho rekurzivne
                    search(i + 1, neighbor);
                }
            }
        }
        visited[vertex] = false;
    }

    private void printPath() {
        for (int i = 0; i < path.length; i++) {
            System.out.print(" " + path[i]);
        }
        System.out.println();
    }
}

Cvičenia:

  • Namiesto vypisovania ciest iba spočítajte, koľko ich je
  • Zistite, či cesta dĺžky k existuje, po nájdení prvej cesty je už možné ukončiť ďalšie prehľadávanie
  • Navrhnite spôsoby, ako v niektorých prípadoch zistiť, že aktuálne rozrobenú cestu už nie je možné požadovaným spôsobom rozšíriť

Hľadanie najdlhšej cesty

  • V grafe chceme nájsť najdlhšiu cestu z u do v
  • Malé zmeny v predchádzajúcom programe
    • Pamätáme si najdlhšiu nájdenú cestu
    • Vždy keď prídeme do cieľového vrcholu, porovnáme dĺžku aktuálnej cesty s najdlhšou nájdenou doteraz
/** Trieda, ktora umoznuje najst najdlhsiu cestu medzi dvoma danymi vrcholmi. */
class LongestPath {

    /** samotny graf */
    private Graph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** najvyssia najdena dlzka cesty */
    private int maxLength;
    /** najlepsia najdena cesta */
    private int[] longestPath;
    /** tvorena cesta */
    private int[] path;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a spusti rekurzivne vyhladavanie */
    public LongestPath(Graph g, int from, int to) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj pole visited
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[n];
        maxLength = -1;
        search(0, from); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda ako i-ty vrchol cesty ulozi vertex a
     * potom skusa vsetky moznosti ako v ceste pokracovat dalej. */
    private void search(int i, int vertex) {
        // ulozime vrchol do cesty a poznacime ho ako pouzity
        path[i] = vertex;
        visited[vertex] = true;
        // ak sme v cielovom vrchole, porovname cestu s maximom
        if (vertex == to) {
            if (i > maxLength) {
                // ak sme nasli lepsiu cestu, ulozime si ju
                longestPath = Arrays.copyOf(path, i + 1); // kopiruj prvych i+1 prvkov
                maxLength = i;
            }
        } else {
            // ak este nie sme vo vrchole to,
            // pozrieme na susedov aktualneho vrcholu vertex
	    for(int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, preskumame ho rekurzivne
                    search(i + 1, neighbor);
                }
            }
        }
        visited[vertex] = false;
    }

    int[] longestPath() {
        return Arrays.copyOf(longestPath, maxLength + 1);
    }
}

Použitie triedy:

        LongestPath p = new LongestPath(g, 0, 3);
        System.out.println("Najdlhsia cesta: "
                + Arrays.toString(p.longestPath()));

Príklad výstupu na rovnakom grafe ako vyššie:

Najdlhsia cesta: [0, 1, 2, 4, 3]

Hľadanie najdlhšej cesty v grafe s ohodnotenými hranami

Mierna obmena predchádzajúceho problému

  • Každá hrana v grafe má priradené číslo (váha alebo dĺžka hrany)
  • Hľadáme cestu z u do v s najväčším súčtom váh hrán
PROG-P36-graf2.png
Napr. ak v grafe vyššie majú všetky hrany dĺžku 1, ale hrany {0,2} a {2,3} majú dĺžku 10, dostávame:
Najdlhsia cesta: [0, 2, 3]

Pozor, na hľadanie najkratšej cesty v ohodnotenom grafe sa nedá použiť prehľadávanie do šírky, algoritmy uvidíte v treťom ročníku.

Rozhranie pre graf s ohodnotenými hranami

Potrebujeme v prvom rade takýto graf reprezentovať. V abstraktnom dátovom type potrebujeme aspoň tieto zmeny:

  • Možnosť pri vkladaní hrany uložiť aj jej dĺžku
  • Možnosť zistiť dĺžku hrany medzi dvoma vrcholmi, ak existuje (nebudeme implementovať)
  • Možnosť pri iterovaní cez susedov zistiť dĺžku hrany k susedovi
/** Pomocna trieda reprezentujuca dvojicu sused a
 * vaha hrany k tomuto susedovi. */
class WeightedNeighbor {
    
    private int vertex;    // cislo suseda
    private double weight; // vaha hrany k susedovi
    
    /** Konstruktor dostane vrchol v a vahu w */
    public WeightedNeighbor(int v, double w) {
	vertex = v;
	weight = w;
    }

    public int vertex() { return vertex; }
    double weight() { return weight; }
}

/** Rozhranie pre graf s hranami ohodnotenymi
 * desatinnymi cislami. */
interface WeightedGraph extends Graph {

    /** Pridaj hranu s danou vahou */
    boolean addEdge(int from, int to, double weight);

    /** Iterovatelny zoznam ovahovanych susedov */
    Iterable <WeightedNeighbor> weightedAdjVertices(int vertex);
}

Implementácia ohodnoteného grafu zoznamami susedov

  • podobná na neváhovanú verziu
/** Trieda reprezentujúca neorientovaný graf s hranami ohodnotenymi
 * desatinnymi cislami. Graf je ulozeny pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class WeightedAdjListsGraph implements WeightedGraph {

    /** Zoznam susedov pre každý vrchol (dvojice vrchol, vaha hrany) */
    private ArrayList<ArrayList<WeightedNeighbor>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public WeightedAdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<WeightedNeighbor>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<WeightedNeighbor>());
        }
        numEdges = 0;
    }

    public int getNumberOfVertices() {
        return adjLists.size();
    }

    public int getNumberOfEdges() {
        return numEdges;
    }

    /** Pridanie hrany s vahou 0 */
    public boolean addEdge(int from, int to) {
        return addEdge(from, to, 0);
    }

    /** Pridanie hrany s danou vahou */
    public boolean addEdge(int from, int to, double weight) {
        adjLists.get(from).add(new WeightedNeighbor(to, weight)); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(new WeightedNeighbor(from, weight));
        numEdges++;
        return true;

    }

    /** Test na existenciu hrany */
    public boolean existsEdge(int from, int to) {
        // prejdeme cez susedov from iteratorom, testujeme na rovnost s to
	for(WeightedNeighbor other : weightedAdjVertices(from)) {
	    if (other.vertex() == to) {
                return true;
            }
        }
        return false;
    }

    /** Iterátor cez váhovaných susedov vrchola */
    public Iterable <WeightedNeighbor> weightedAdjVertices(int vertex) {
	// vrati ArrayList obaleny, aby sa nedal menit
	return Collections.unmodifiableList(adjLists.get(vertex));
    }

    /** Iterátor cez susedov vrchola */
    public Iterable <Integer> adjVertices(int vertex) {
	// vytvori ArrayList a obali ho, aby sa nedla menit
	ArrayList <Integer> result = new ArrayList<Integer>();
	for(WeightedNeighbor other : weightedAdjVertices(vertex)) {
	    result.add(other.vertex());
	}
	return Collections.unmodifiableList(result);
    }
}

Samotné prehľadávanie

  • Okrem aktuálnej cesty si musíme pamätať aj jej dĺžku, t.j. súčet váh hrán na ceste
  • Rekurzia riešená trochu inak: v cykle cez susedov rovno ukladáme suseda do všetkých potrebných polí (lebo vieme váhu hrany)
    • Rekurzívne prehľadávanie sa väčšinou dá zapísať veľa rôznymi spôsobmi
    • Treba si vždy dobre rozmyslieť, čo robí rekurzívna funkcia a čo by malo platiť o jednotlivýh premenných
/** Trieda, ktora umoznuje najst najdlhsiu cestu
 * medzi dvoma danymi vrcholmi v ovahovanom grafe. */
class LongestWeightedPath {

    /** samotny graf */
    private WeightedGraph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** najvyssia najdena dlzka cesty */
    private double maxLength;
    /** najlepsia najdena cesta */
    private int[] longestPath;
    /** tvorena cesta */
    private int[] path;
    /** dlzka tvorenej cesty */
    private double length;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a spusti rekurzivne vyhladavanie */
    public LongestWeightedPath(WeightedGraph g, int from, int to) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj pole visited
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[n];  // vytvor cestu dlzky 0 obsahujucu iba zac. vrchol
        path[0] = from;
        visited[from] = true;
        length = 0;
        maxLength = -1;     // najlespia najdena cesta
        search(1); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda skusa pridat novy vrchol na poziciu i a
     * potom skusa vsetky moznosti ako v ceste pokracovat dalej. */
    private void search(int i) {
        int vertex = path[i - 1];  // predchadzajuci vrchol na ceste
        // ak sme v cielovom vrchole, porovname cestu s maximom
        if (vertex == to) {
            if (length > maxLength) {
                // ak sme nasli lepsiu cestu, ulozime si ju
                longestPath = Arrays.copyOf(path, i); // kopiruj prvych i prvkov
                maxLength = length;
            }
        } else {
            // ak este nie sme v cielovom vrchole,
            // pozrieme na susedov predchadzajuceho vrcholu vertex
	    for(WeightedNeighbor other : g.weightedAdjVertices(vertex)) { // prejdi cez susedov
                int neighbor = other.vertex();  // sused vrcholu vertex
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, ulozime ho do cesty
                    // a zavolame rekurziu
                    path[i] = neighbor;
                    visited[neighbor] = true;
                    double weight = other.weight();
                    length += weight;
                    search(i + 1);
                    length -= weight;
                    visited[neighbor] = false;
                }
            }
        }
    }

    int[] longestPath() {
        return Arrays.copyOf(longestPath, longestPath.length);
    }
}

Programy

Programy z tejto prednášky nájdete tu:

Zdrojový kód programu, prehľadávanie s návratom na neohodnotených grafoch

  • niekoľko prehľadávaní s návratom v neohodnotenom grafe (cesta zadanej dĺžky, najdlhšia cesta, najväčšia klika)
package prog;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Scanner;

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

/** Trieda reprezentujúca neorientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

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

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

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(from);
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
	// vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex)); 
    }
}

/** Trieda, ktora umoznuje najst vsetky cesty zadanej
 * dlzky medzi dvoma danymi vrcholmi. */
class FixedLengthPaths {

    /** samotny graf */
    private Graph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** pozadovana dlzka cesty */
    private int length;
    /** tvorena cesta */
    private int[] path;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a pozadovanu dlzku cesty a rovno aj spusti rekurzivne vyhladavanie
     * a vypisuje vysledky. */
    public FixedLengthPaths(Graph g, int from, int to, int length) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        this.length = length;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj polia visited a path
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[length + 1];  // length hran, teda length+1 vrcholov
        search(0, from); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda ako i-ty vrchol cesty ulozi vertex a
     * potom skusa vsetky moznosti ako sa na length-i krokov
     * dostat do cieloveho vrcholu. */
    private void search(int i, int vertex) {
        // ulozime vrchol do cesty a poznacime ho ako pouzity
        path[i] = vertex;
        visited[vertex] = true;
        // ak uz mame cestu dlzky length, pozrieme,
        // ci konci v spravnom vrchole a vypiseme
        if (i == length) {
            if (vertex == to) {
                printPath();
            }
        } else {
            // ak este nemame cestu dlzky length,
            // pozrieme na susedov aktualneho vrcholu vertex
	    for(int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, preskumame ho rekurzivne
                    search(i + 1, neighbor);
                }
            }
        }
        visited[vertex] = false;
    }

    private void printPath() {
        for (int i = 0; i < path.length; i++) {
            System.out.print(" " + path[i]);
        }
        System.out.println();
    }
}

/** Trieda, ktora umoznuje najst najdlhsiu cestu medzi dvoma danymi vrcholmi. */
class LongestPath {

    /** samotny graf */
    private Graph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** najvyssia najdena dlzka cesty */
    private int maxLength;
    /** najlepsia najdena cesta */
    private int[] longestPath;
    /** tvorena cesta */
    private int[] path;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a spusti rekurzivne vyhladavanie */
    public LongestPath(Graph g, int from, int to) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj pole visited
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[n];
        maxLength = -1;
        search(0, from); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda ako i-ty vrchol cesty ulozi vertex a
     * potom skusa vsetky moznosti ako v ceste pokracovat dalej. */
    private void search(int i, int vertex) {
        // ulozime vrchol do cesty a poznacime ho ako pouzity
        path[i] = vertex;
        visited[vertex] = true;
        // ak sme v cielovom vrchole, porovname cestu s maximom
        if (vertex == to) {
            if (i > maxLength) {
                // ak sme nasli lepsiu cestu, ulozime si ju
                longestPath = Arrays.copyOf(path, i + 1); // kopiruj prvych i+1 prvkov
                maxLength = i;
            }
        } else {
            // ak este nie sme vo vrchole to,
            // pozrieme na susedov aktualneho vrcholu vertex
	    for(int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, preskumame ho rekurzivne
                    search(i + 1, neighbor);
                }
            }
        }
        visited[vertex] = false;
    }

    int[] longestPath() {
        return Arrays.copyOf(longestPath, maxLength + 1);
    }
}

/** Trieda, ktora umoznuje najst maximalnu kliku v danom grafe. */
class MaximumClique {

    /** samotny graf */
    private Graph g;
    /** zoznam vrcholov v najvacsej doteraz najdenej klike */
    private LinkedList<Integer> maxClique;
    /** zoznam vrcholov v aktualnej klike */
    private LinkedList<Integer> clique;

    /** Konstruktor, ktory dostane graf a spusti rekurzivne vyhladavanie */
    public MaximumClique(Graph g) {
        this.g = g;  // uloz vstupny graf
        // vytvor dve prazdne kliky
        clique = new LinkedList<Integer>();
        maxClique = new LinkedList<Integer>();
        search(0); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda skusi pouzit aj vynechat vrchol vertex
     * potom skusa vsetky moznosti pre vrcholy vertex+1...n-1. */
    private void search(int vertex) {
        // ak aktualna klika je vacsia ako doterajsie maximum, uloz ju
        if (clique.size() > maxClique.size()) {
            // konstruktor LinkedListu moze vytvorit kopiu inej Collection
            maxClique = new LinkedList<Integer>(clique);
        }
        // ak uz sme vycerpali vsetky vrcholy, nie je co skusat dalej
        if (vertex == g.getNumberOfVertices()) {
            return;
        }
        // otestuj, ci sa vrchol vertex da pridat do kliky
        // a ci ma sancu byt vo vacsej klike ako doteraz najdena
        if (isConnected(g, vertex, clique)
                && degree(g, vertex) + 1 > maxClique.size()) {
            // ak ano, pridaj ho do kliky a zavolaj rekurziu
            clique.addLast(vertex);
            search(vertex + 1);
            // odober vertex x kliky
            clique.removeLast();
        }
        // preskoc vertex a zavolaj rekurziu na ostatne vrcholy
        search(vertex + 1);
    }

   /** pomocna metoda, ktora overi, ci vrchol vertex je v grafe g
     * spojeny s kazdym z vrcholov v mnozine vertexSet. */
    private static boolean isConnected(Graph g, int vertex,
            Collection<Integer> vertexSet) {
        // iterujeme cez mnozinu vertexSet
	for(int v : vertexSet) {
            if (!g.existsEdge(vertex, v)) { // over hranu
                return false;  // hrana nie je
            }
        }
        return true; // vsetky hrany najdene
    }

    /** pomocna metoda, ktora zisti stupen vrchola vertex v grafe g */
    private static int degree(Graph g, int vertex) {
        // iterujeme cez susedov vrchola, zvysujeme pocitadlo result
        int result = 0;
	for(int x : g.adjVertices(vertex)) {
            result++;
        }
        return result;
    }

    /** vrati maximalnu kliku najdenu v grafe g */
    public LinkedList<Integer> maxClique() {
        // vrat kopiu nasej najlepsej kliky
        return new LinkedList<Integer>(maxClique);
    }
}

public class Prog {

    /** Zo scannera s načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov.
     * Uloží ho ako AdjMatrixGraph. */
    static Graph readGraph(Scanner s) {
        int n = s.nextInt();
        int m = s.nextInt();
        Graph 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;
    }

    public static void main(String[] args) throws FileNotFoundException {

        Scanner s = new Scanner(new File("graph.txt"));
        Graph g = readGraph(s);
        s.close();

        for (int length = 1; length < g.getNumberOfVertices(); length++) {
            System.out.println("Cesty dlzky " + length + ":");
            FixedLengthPaths p = new FixedLengthPaths(g, 0, 3, length);
        }

        LongestPath p = new LongestPath(g, 0, 3);

        System.out.println("Najdlhsia cesta: "
                + Arrays.toString(p.longestPath()));

        MaximumClique c = new MaximumClique(g);
        System.out.println(
                "Maximalna klika: "
                + c.maxClique().toString());

    }
}


/* Priklad vstupu (ulozit do graph.txt)
    5 7
    0 1
    0 2
    0 3
    1 2
    2 3
    2 4
    3 4
*/

Zdrojový kód programu, prehľadávanie s návratom na ohodnotených grafoch

  • graf s ohodnotenými hranami a hľadanie najdlhšej cesty v ňom
package prog;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Scanner;

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

/** Trieda reprezentujúca neorientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

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

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

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(from);
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        return adjLists.get(vertex); // vrati ArrayList
    }
}

/** Pomocna trieda reprezentujuca dvojicu sused a
 * vaha hrany k tomuto susedovi. */
class WeightedNeighbor {

    private int vertex;    // cislo suseda
    private double weight; // vaha hrany k susedovi

    /** Konstruktor dostane vrchol v a vahu w */
    public WeightedNeighbor(int v, double w) {
        vertex = v;
        weight = w;
    }

    public int vertex() {
        return vertex;
    }
    double weight() {
        return weight;
    }
}

/** Interface pre graf s hranami ohodnotenymi
 * desatinnymi cislami. */
interface WeightedGraph extends Graph {

    /** Pridaj hranu s danou vahou */
    boolean addEdge(int from, int to, double weight);

    /** Iterovatelny zoznam ovahovanych susedov */
    Iterable <WeightedNeighbor> weightedAdjVertices(int vertex);
}

/** Trieda reprezentujúca neorientovaný graf s hranami ohodnotenymi
 * desatinnymi cislami. Graf je ulozeny pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class WeightedAdjListsGraph implements WeightedGraph {

    /** Zoznam susedov pre každý vrchol (dvojice vrchol, vaha hrany) */
    private ArrayList<ArrayList<WeightedNeighbor>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public WeightedAdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<WeightedNeighbor>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<WeightedNeighbor>());
        }
        numEdges = 0;
    }

    public int getNumberOfVertices() {
        return adjLists.size();
    }

    public int getNumberOfEdges() {
        return numEdges;
    }

    /** Pridanie hrany s vahou 0 */
    public boolean addEdge(int from, int to) {
        return addEdge(from, to, 0);
    }

    /** Pridanie hrany s danou vahou */
    public boolean addEdge(int from, int to, double weight) {
        adjLists.get(from).add(new WeightedNeighbor(to, weight)); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(new WeightedNeighbor(from, weight));
        numEdges++;
        return true;

    }

    /** Test na existenciu hrany */
    public boolean existsEdge(int from, int to) {
        // prejdeme cez susedov from iteratorom, testujeme na rovnost s to
        for (WeightedNeighbor other : weightedAdjVertices(from)) {
            if (other.vertex() == to) {
                return true;
            }
        }
        return false;
    }

    /** Iterátor cez váhovaných susedov vrchola */
    public Iterable <WeightedNeighbor> weightedAdjVertices(int vertex) {
        // vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex));
    }

    /** Iterátor cez susedov vrchola */
    public Iterable <Integer> adjVertices(int vertex) {
        // vytvori ArrayList a obali ho, aby sa nedla menit
        ArrayList <Integer> result = new ArrayList<Integer>();
        for (WeightedNeighbor other : weightedAdjVertices(vertex)) {
            result.add(other.vertex());
        }
        return Collections.unmodifiableList(result);
    }
}


/** Trieda, ktora umoznuje najst najdlhsiu cestu
 * medzi dvoma danymi vrcholmi v ovahovanom grafe. */
class LongestWeightedPath {

    /** samotny graf */
    private WeightedGraph g;
    /** pociatocny a koncovy vrchol */
    private int from, to;
    /** najvyssia najdena dlzka cesty */
    private double maxLength;
    /** najlepsia najdena cesta */
    private int[] longestPath;
    /** tvorena cesta */
    private int[] path;
    /** dlzka tvorenej cesty */
    private double length;
    /** vrcholy, ktore su na ceste pouzite */
    private boolean[] visited;

    /** Konstruktor, ktory dostane graf, pociatocny a koncovy vrchol
     * a spusti rekurzivne vyhladavanie */
    public LongestWeightedPath(WeightedGraph g, int from, int to) {
        this.g = g;  // uloz vstupne data
        this.from = from;
        this.to = to;
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        visited = new boolean[n];  // vytvor a inicializuj pole visited
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        path = new int[n];  // vytvor cestu dlzky 0 obsahujucu iba zac. vrchol
        path[0] = from;
        visited[from] = true;
        length = 0;
        maxLength = -1;     // najlespia najdena cesta
        search(1); // zavolaj rekurziu
    }

    /** Hlavna rekurzivna metoda volana z konstruktora.
     * Metoda skusa pridat novy vrchol na poziciu i a
     * potom skusa vsetky moznosti ako v ceste pokracovat dalej. */
    private void search(int i) {
        int vertex = path[i - 1];  // predchadzajuci vrchol na ceste
        // ak sme v cielovom vrchole, porovname cestu s maximom
        if (vertex == to) {
            if (length > maxLength) {
                // ak sme nasli lepsiu cestu, ulozime si ju
                longestPath = Arrays.copyOf(path, i); // kopiruj prvych i prvkov
                maxLength = length;
            }
        } else {
            // ak este nie sme v cielovom vrchole,
            // pozrieme na susedov predchadzajuceho vrcholu vertex
            for (WeightedNeighbor other : g.weightedAdjVertices(vertex)) { // prejdi cez susedov
                int neighbor = other.vertex();  // sused vrcholu vertex
                if (!visited[neighbor]) {
                    // ak este sused nebol navstiveny, ulozime ho do cesty
                    // a zavolame rekurziu
                    path[i] = neighbor;
                    visited[neighbor] = true;
                    double weight = other.weight();
                    length += weight;
                    search(i + 1);
                    length -= weight;
                    visited[neighbor] = false;
                }
            }
        }
    }

    int[] longestPath() {
        return Arrays.copyOf(longestPath, longestPath.length);
    }
}

public class Prog {

    /** Zo scannera s načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov a vahami. */
    static WeightedGraph readGraph(Scanner s) {
        int n = s.nextInt();
        int m = s.nextInt();
        WeightedGraph g = new WeightedAdjListsGraph(n);
        for (int i = 0; i < m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            double weight = s.nextDouble();
            g.addEdge(u, v, weight);
        }
        return g;
    }

    public static void main(String[] args) throws FileNotFoundException {

        Scanner s = new Scanner(new File("weightedGraph.txt"));
        WeightedGraph g = readGraph(s);
        s.close();

        LongestWeightedPath p = new LongestWeightedPath(g, 0, 3);
        System.out.println("Najdlhsia cesta: "
                           + Arrays.toString(p.longestPath()));

    }
}

/* Priklad vstupu (ulozit do weightedGraph.txt)

5 7
0 1 1
0 2 10
0 3 1
1 2 1
2 3 10
2 4 1
3 4 1

*/