% CVICENI - 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rychle algoritmy, trideni, vyhledáváni (2)

clc; close all;

% ----------------- Prace s grafy ----------------- %
% priklad vytvoreni grafu
n = 10;
A = delsq(numgrid('L',n+2));
G = graph(A,'omitselfloops');
fig = figure(1);
plot(G);


% priklad vytvoreni grafu: pomoci dvojic uzlu [s,t] s prislusnou hranou
% s vahou w
s = [1 1 1 1 2 2 3 4 4 5 6];
t = [2 3 4 5 3 6 6 5 7 7 7];
w = [50 10 20 80 90 90 30 20 100 40 60];
G = graph(s,t,w);
% zobrazeni grafu, hrany jsou zobrazeny s tloustkou v zavislosti na vaze
fig = figure(2);
LWidths = 5*G.Edges.Weight/max(G.Edges.Weight);
plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',LWidths)


% priklad vytvoreni grafu, pomoci prechodove matice
A = [
    0 5 7 0;
    5 0 3 8;
    7 3 0 4;
    0 8 4 0
];
G = graph(upper(A), 'OmitSelfLoops', 'upper');
fig = figure(3);
h = plot(G, 'EdgeLabel', G.Edges.Weight, 'Layout', 'force');
% Jina barva a velikost uzlu
highlight(h, 1:numnodes(G), 'NodeColor', 'r', 'MarkerSize', 10);


% --------- Jarnikuv algoritmus ----------- %
% Priklad prechodove matice
A = [
    0 5 7 0;
    5 0 3 8;
    7 3 0 4;
    0 8 4 0
];
% generovani nahodnych prechodovych matic
N = 20;
Wmin = 0;
Wmax = 12;
B = randi([Wmin, Wmax], N, N); 
B = triu(B, 1) + triu(B, 1).' + diag(zeros(1, size(B, 1)));

%[T, E] = Jarnik_Algorithm(A);
%disp(T); % matice incidence pro minimalni kostru
[T, E] = Jarnik_Algorithm(B);
T
E

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   FUNKCE   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [T, E] = Jarnik_Algorithm(A)
    N = size(A, 1);             % pocet uzlu v grafu
    visited = false(1, N);      % pole navstivenych uzlu
    visited(1) = true;          % zacatek v uzlu 1 (muze byt i jiny...)
    E = cell(1, N-1);           % (n-1)-hran mezi n-uzly, zde zatim jako
                                % prazdne pole: {[],[],[],...,[]}, n-1 hran
    
    for i = 1:N-1  % iterujeme dokud nenalezneme vsech n-1 hran
        
        % inicializace pocatecni min. vahy a zacatku/konce hrany
        minWeight = Inf;
        from = 0;
        to = 0;
        
        % (j) prochazime prakticky jen mnozinu jiz drive navstivenych uzlu
        for j = 1:N         
            if visited(j)
                % (k) k jiz drive navstivenym uzlum pridame dalsi uzel
                % z nenavstivenych, takovy ze jeho cesta je minimalni
                % vzhledem k mnozine navstivenych
                % Pr. v prostoru E2 bychom k mracnu bodu (navstivenych)
                % pridali dalsi bod, ktery ma nejmensi vzdalenost vzhledem
                % k jakemukoliv bodu
                for k = 1:N 
                    if ~visited(k) && A(j, k) > 0 && A(j, k) < minWeight
                        minWeight = A(j, k);
                        from = j;
                        to = k;
                    end
                end
            end
        end
        
        % po pridani noveho uzlu tento oznacime jako navstiveny
        % a pridame i-tou hranu
        E{i} = [from, to];
        visited(to) = true;
    end
    
    % Vystupem je prechodova matice, ktera reprezentuje nejmensi kostru,
    % tj. v puvodni matici (vstup A) jsou 'vyskrtany' nektere jednicky...
    T = zeros(N);
    for i = 1:length(E)
        T(E{i}(1), E{i}(2)) = A(E{i}(1), E{i}(2));
        T(E{i}(2), E{i}(1)) = A(E{i}(2), E{i}(1));
    end
    % Druhym vystupem jsou hrany E ve formatu: {[s1,e1],[s2,e2],[],...,[]}
    % s-start, e-end = pocatecni, koncovy uzel hrany

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % ZDE uz jen pro ucely animace / zobrazeni
    % zobrazeni puvodniho grafu
    fig = figure(4);
    G = graph(A, 'OmitSelfLoops', 'upper');
    h = plot(G, 'EdgeLabel', G.Edges.Weight, 'Layout', 'force');
    
    hold on;    
    % zvyrazneni hran pro minimalni kostru grafu
    for i = 1:length(E)
        highlight(h, E{i}(1), E{i}(2), 'EdgeColor', 'r', 'LineWidth', 1.5);
    end    
    hold off;
end