%s = [   1 1 2 2 3 4 5 6 8 14 10 9 1 4 8 12 10 13 12] ; % polaczenia miedzy wierzchołkami
%t = [   8 3 5 9 6 7 7 2 5 10 9 6 11 11 11 3 13 14  14];

s=[1 1 2 2 3 4 4 5  5 6  6 7  7 8   9  9 10 11 12];
t=[2 3 4 5 6 3 8 7 12 9 10 8 13 14 11 13 11 12 14];

dlugosc = length(s);
weights = randi(5,dlugosc,1)+2;

G = graph(s,t,weights) % tworzenie i rysowanie grafu
h = plot(G,'EdgeLabel',G.Edges.Weight)
f = degree(G);  % maciez ktora trzyma ile kazdy wierzcholek ma polaczen
G1=G;
koniec=0;
m=1;
a=0;
wierzcholki = numnodes(G);

for k = 1 : wierzcholki
    odwiedzone(k)=f(k);% szukamy tych co maja nieparzysta ilosc krawedzi
    if (rem( f(k), 2 ) == 1 ) % a zawiera numery wierzcholkow ktore sa nieparzyste
    a(m) = k;
    odwiedzone(k)=odwiedzone(k)+10;
    m = m+1 ;
    end


end
min=10000;
brutemin = 10000;

n = length(a);

for i = 1:100*n
    force = randperm(n,n);

    [path1,d1] = shortestpath(G,a(force(1)),a(force(2)));
    [path2,d2] = shortestpath(G,a(force(3)),a(force(4)));
    [path3,d3] = shortestpath(G,a(force(5)),a(force(6)));
    [path4,d4] = shortestpath(G,a(force(7)),a(force(8)));
    [path5,d5] = shortestpath(G,a(force(9)),a(force(10)));

    brutemin = length(path1)+length(path2)+length(path2)+length(path2)+length(path2);
    min1 = d5+d4+d3+d2+d1;
    if(min1+brutemin<min+brutemin)
        min=min1;
       pathSecond1=path1;
       pathSecond2=path2;
       pathSecond3=path3;
       pathSecond4=path4;
       pathSecond5=path5;
    end

end
pathSecond1R=fliplr(pathSecond1);
pathSecond2R=fliplr(pathSecond2);
pathSecond3R=fliplr(pathSecond3);
pathSecond4R=fliplr(pathSecond4);
pathSecond5R=fliplr(pathSecond5);

 highlight(h,pathSecond1,'NodeColor','g','EdgeColor','g','LineWidth',2)
 highlight(h,pathSecond2,'NodeColor','g','EdgeColor','g','LineWidth',2)
 highlight(h,pathSecond3,'NodeColor','g','EdgeColor','g','LineWidth',2)
 highlight(h,pathSecond4,'NodeColor','g','EdgeColor','g','LineWidth',2)
 highlight(h,pathSecond5,'NodeColor','g','EdgeColor','g','LineWidth',2)

if(length(a)==10)

     %start = randi(wierzcholki);
     start = 1;
     highlight(h,start,'NodeColor','red')
    % path= shortestpath(G,a(1),a(2));



    index = 1;
    v = start; %  pozniej v = start;

    while(numedges(G1)>1) % dopóki g1 ma krawedzie
        next= neighbors(G1,v)
        if(length(neighbors(G1,start))==1) % sprawdzamy droge ktora ma byc ostatnia do przejscia
           last = neighbors(G1,start);
           koniec = shortestpath(G,last,start);
        end


        path = shortestpath(G,v,next(index) ); % to idziemy do niego

        unusual=0; %% czy to niezwykla droga
        if(isequal(path,pathSecond1) ||isequal(path,pathSecond1R))
           unusual=1;
        end
         if(isequal(path,pathSecond2) ||isequal(path,pathSecond2R))
           unusual=1;
         end
         if(isequal(path,pathSecond3) ||isequal(path,pathSecond3R))
           unusual=1;
         end
         if(isequal(path,pathSecond4) ||isequal(path,pathSecond4R))
           unusual=1;
         end
         if(isequal(path,pathSecond5) ||isequal(path,pathSecond5R))
           unusual=1;
        end






        if(unusual==0) %%%%%% jezeli to zwykla krawedz to idziemy raz
            if(path == koniec)
              index=index+1;
            else
            G1 = rmedge(G1,v,next(index))
            pause(0.5)
            highlight(h,path,'EdgeColor','r','LineWidth',2)
            v=next(index);
            index=1
            end

         else % jezeli nie jest zwykla to dwa razy
            if(length(path)==2)
                 pause(0.5)
                 highlight(h,path,'EdgeColor','r','LineWidth',2)
                 pause(0.5)
                 highlight(h,path,'EdgeColor','b','LineWidth',2)
                 G1 = rmedge(G1,v,next(index));
             else
                 for i = 1 : (length(path)-1)
                    path2 =shortestpath(G,path(i),path(i+1))
                    pause(0.5)
                    highlight(h,path2,'EdgeColor','r','LineWidth',2)
                 end
                 for i = 1 : (length(path)-1)
                    path2 =shortestpath(G,path(length(path)+1-i),path(length(path)-i))
                    pause(0.5)
                    highlight(h,path2,'EdgeColor','b','LineWidth',2)
                    G1 = rmedge(G1,path(length(path)+1-i),path(length(path)-i));
                 end
            end

         end

    end

    if(numedges(G1)==1)
        G1 = rmedge(G1,last,start);
        pause(0.5)
        highlight(h,koniec,'EdgeColor','r','LineWidth',2)
    end


end