% GraphTook - 2007-2012 Glotin & Chouchane
% Dyni LSIS USTV - { glotin, halkias } @ univ-tln.fr

%%%%%%%%%%%%%%%%%
function graph_plot(adja,cas,v) %
% graph_plot(G, ones(1,sum(G(:))),1)
% graph_plot(adja,v,cas) trace le graphe de matrice d'adjacence adja et numérote les arcs avec les valeurs non nulles dans v,
% les arcs sont les couples (L,C) dans l'ordre de lecture gauche-droite, haut-bas de 'adja' ; si v=[0..0], taille nb arc alors aucun numéro d'arc tracé.
if nargin < 3 ; v=zeros(1,sum(adja(:))); end
% cas=1 => algo d'attraction/repulsion (par défaut)
% cas=2 => algo de permutation des sommets sur un cercle
% LANCER PLUSIEURS FOIS ET CHOISIR LA MEILLEURE REPRESENTATION
% PG 2009 V2 2010 compatible OCTAVE 3.0 et MATLAB
% glotin@univ-tln.fr
% exemple d'utilisation :
% h =[0 0 1 1 0;0 0 1 0 1;1 1 0 1 0;1 0 1 0 1;0 1 0 1 0];
% graph_plot(h,[0 6 0 2 5 1 0 0 4 0 0 3])
% PARAMETRES
if nargin==1, cas=1; end;
nb_iter=1000;
nbs=length(adja); [n1 n2]=find(adja);
% matrice du nb min d'arcs pour relier chaque paire de sommets
nb_int=adja+adja';
for i=1:nbs-1
    for s=1:nbs
        c=find(nb_int(s,:));
        for s1=1:length(c)-1, for s2=s1+1:length(c)
                if nb_int(c(s1),c(s2))==0 | nb_int(c(s1),c(s2))>nb_int(s,c(s1))+nb_int(s,c(s2))
                    nb_int(c(s1),c(s2))=nb_int(s,c(s1))+nb_int(s,c(s2));
                    nb_int(c(s2),c(s1))=nb_int(s,c(s1))+nb_int(s,c(s2));
                end;end;end;end;end;
nb_int(find(nb_int==0))=max(max(nb_int))+1;
if cas==1
    % POSITIONS ALEATOIRES DES NOEUDS
    pos=rand(2,nbs)*100;
    % OPTIMISATION PAR ATTRACTION-REPULSION
    for e=1:nb_iter
        % Chaque sommet se rapproche du centre de gravitÃÂ©
        for i=1:nbs
            pos(:,i) = pos(:,i) + (mean(pos')'-pos(:,i))*e/nb_iter/100;
        end;
        % Chaque paire se repousse en dessous d'une distance de 10
        for i=1:nbs-1,
            for j=i+1:nbs
                d=sqrt(sum((pos(:,i)-pos(:,j)).^2));
                if d<10,
                    pos(:,i) = pos(:,i) - (pos(:,j)-pos(:,i))*e/nb_iter/d;
                    pos(:,j) = pos(:,j) - (pos(:,i)-pos(:,j))*e/nb_iter/d;
                end;end;end;
        % Chaque paire se repousse en fonction du nb min d'arcs
        for i=1:nbs-1,
            for j=i+1:nbs
                d=10*sqrt(nb_int(i,j))-sqrt(sum((pos(:,i)-pos(:,j)).^2));
                pos(:,i)= pos(:,i) - (pos(:,j)-pos(:,i))*d/nb_int(i,j)*(nb_iter-e)/nb_iter/100;
                pos(:,j)= pos(:,j) - (pos(:,i)-pos(:,j))*d/nb_int(i,j)*(nb_iter-e)/nb_iter/100;
            end;end;end;
elseif cas==2
    % POSITIONS ALEATOIRES SUR UN CERCLE
    pos(1,:)=cos([1:nbs]*2*pi/nbs);
    pos(2,:)=sin([1:nbs]*2*pi/nbs);
    % OPTIMISATION PAR PERMUTATIONS SUR LE CERCLE
    d=sum(sqrt(sum((pos(:,n1)-pos(:,n2)).^2)));
    for e=1:nb_iter
        test=randperm(nbs);
        if sum(sqrt(sum((pos(:,test(n1))-pos(:,test(n2))).^2)));
            pos=pos(:,test);d=sum(sqrt(sum((pos(:,n1)-pos(:,n2)).^2)));
        end;end;end;
% TRACE
pos_x=[pos(1,n1); pos(1,n2)];
pos_y=[pos(2,n1); pos(2,n2)];
plot(pos(1,:),pos(2,:),'ob','LineWidth',7);
x1=min(pos(1,:)); y1=min(pos(2,:)); x2=max(pos(1,:)); y2=max(pos(2,:));
xlim([x1 x2]+[-0.1 0.2]*(x2-x1));
ylim([y1 y2]+[-0.1 0.2]*(y2-y1));
text(pos(1,:),pos(2,:)+0.05*(y2-y1),num2str([1:nbs]'),'fontsize',24,'color','b');
for i=1:size(pos_x,2)
    line(pos_x(:,i),pos_y(:,i),'color','r','LineWidth',4);
    if v(i)
        text((pos_x(1,i)+2*pos_x(2,i))/3,(pos_y(1,i)+2*pos_y(2,i))/3,num2str(v(i)),'fontsize',24,'color','k');
    end;
end;
end %endfunction;
