====== Úloha 2 ======

Počítačová síť

[[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=pocitacova_sit|Zadání]]

Limit: 2s

Jak na to:
  - Načíst vstup a uložit do listu hran. Je potřeba dávat pozor na to, že A->B je to stejné jako B->A. Mohou se tam také vyskytnout duplicitní nabídky, takže zachovat jenom tu s menší cenou
  - Seřadit hrany podle ceny, pokud jsou ceny stejné tak podle čísla první budovy
  - Inicializovat struktury na UNION-FIND - dvě pole:
    * "pole bossů" - index je číslo budovy a obsah je kdo je boss budovy, na začátku je každý svůj boss
    * "pole hloubek" - index je číslo budovy a obsah její hloubka, na začátku je hloubka 0
  - Procházet možné hrany od těch s nejmenších cenou a postupně je přidávat dokud jich nebude (počet budov-počet připojení k netu)
  - Nesmím ale přidat hranu, která by vytvořila cyklus - máme funkci můžuPřidatHranu(hrana), kterou řeší UNION-FIND:
    * pokud obě budovy z hrany mají stejného bosse, vzniknul by cyklus a vracím false
    * pokud obě budovy z hrany mají různého bosse, vracím true a přidávám hranu do dvou polí takto:
      * pokud hloubka bosse první budovy < hloubka bosse druhé budovy => boss první budovy je boss druhé budovy
      * pokud hloubka bosse první budovy > hloubka bosse druhé budovy => boss druhé budovy je boss první budovy
      * pokud hloubka bosse první budovy == hloubka bosse druhé budovy => boss druhé budovy je boss první budovy && zvyšuju hloubku u bosse první budovy o 1
  - Najít budovy, kam zavést interfernet, to už je easy:
    * Projdu pole bossů a uložím si tolik různých bossů, kolik mám zavést internetů
  - Všechno vypsat

====== Hledání koster a UNION-FIND ======
Mnohem lépe vysvětlené než na přednáškách včetně praktických ukázek pseudokódu:{{:courses:a4m33pal:kostry.pdf|Hledání minimální kostry a UNION-FIND problém}}

====== Generátor grafů ======
Přidávám svůj generátor grafů pro tuhle úlohu. Snad někomu pomůže. Pro opravdu velké grafy je nutné krapet přepsat a flushovat více String Buildery

public class MatrixGenerator {

    public static void main(String[] args) {
        if(args.length!=4){
            System.out.println("Run the program with [nodes] [connections] [edges] [full/random/noconn] params.");
            return;
        }
        final int NODES = Integer.parseInt(args[0]);
        final int CONNECTIONS = Integer.parseInt(args[1]);
        final int EDGES = Integer.parseInt(args[2]);
        final String type = args[3];
        if("full".equals(type.toLowerCase())){
            makeFullGraph(NODES,CONNECTIONS);
        }else if("random".equals(type.toLowerCase())){
            makeRandomGraph(NODES, CONNECTIONS,EDGES);
        }else{
            makeNotConnectableFullGraph(NODES,CONNECTIONS);
        }
        
    }
    
    public static void makeRandomGraph(int NODES,int CONNECTIONS, int EDGES){
        StringBuilder sb = new StringBuilder();
        final boolean random = true;
        sb.append(NODES);
        sb.append("\n");
        sb.append(CONNECTIONS);
        sb.append("\n");
        for(int i = 0 ; i<= EDGES ; i++){
            int x = (int)(1+((Math.random()*NODES)%(NODES-1)));
            int y = (int)(1+((Math.random()*NODES)%(NODES-1)));
            if(x == y){
                i--;
                continue;
            }
            sb.append(x);
            sb.append(" ");
            sb.append(y);
            sb.append(" ");
            sb.append(getWeight(random));
            sb.append("\n");
        }
        sb.append("0 0 0\n");
        System.out.println(sb.toString());
    }

    public static void makeNotConnectableFullGraph(int NODES,int CONNECTIONS) {
        final boolean random = true;
        StringBuilder sb = new StringBuilder();
        sb.append(NODES+CONNECTIONS+1);
        sb.append("\n");
        sb.append(CONNECTIONS);
        sb.append("\n");
        for (int i = 1; i <= NODES; i++) {
            for (int y = 1; y <= NODES; y++) {
                if (i != y) {
                    sb.append(y);
                    sb.append(" ");
                    sb.append(i);
                    sb.append(" ");
                    sb.append(getWeight(random));
                    sb.append("\n");
                }
            }
        }
        sb.append("0 0 0\n");
        System.out.println(sb.toString());
    }
    
    public static void makeFullGraph(int NODES,int CONNECTIONS) {
        final boolean random = true;
        StringBuilder sb = new StringBuilder();
        sb.append(NODES);
        sb.append("\n");
        sb.append(CONNECTIONS);
        sb.append("\n");
        for (int i = 1; i <= NODES; i++) {
            for (int y = 1; y <= NODES; y++) {
                if (i != y) {
                    sb.append(y);
                    sb.append(" ");
                    sb.append(i);
                    sb.append(" ");
                    sb.append(getWeight(random));
                    sb.append("\n");
                }
            }
        }
        sb.append("0 0 0\n");
        System.out.println(sb.toString());
    }

    public static int getWeight(boolean random) {
        if (random) {
            return (int) (Math.random() * 99 + 1);
        } else {
            return 10;
        }
    }
}

====== Diskuze ======
~~DISCUSSION~~