Tp De Recherche Oper

Ce TP réalise les opérations suivantes: 1-remplissage d’une matrice d’une manière aléatoire. 2-dessin du graphe associer à la matrice. 3-construction du tableau de la fermeture transitive à partir de la première matrice. 4-dessin du graphe de la fermeture transitive. 5-calcul du nombres de chemins. 6-la recherche des composantes fortement connexes. 7-dessin du graphe avec la séparation des composantes fortes connexes avec différentes couleurs Il est fait avec delphi.

unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ComCtrls, StdCtrls, ExtCtrls, Grids, Menus; type Tform1 = class(TForm) Button1: TButton; Button2: TButton; Button3: TButton; Button4: TButton; S1: TStringGrid; S2: TStringGrid; Image1: TImage; Image2: TImage; Edit1: TEdit; UpDown1: TUpDown; Button5: TButton; Button6: TButton; Button7: TButton; S3: TStringGrid; S4: TStringGrid; MainMenu1: TMainMenu; algorithmes1: TMenuItem; matrice1: TMenuItem; StaticText1: TStaticText; StaticText2: TStaticText; StaticText3: TStaticText; procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Button3Click(Sender: TObject); procedure Button4Click(Sender: TObject);

procedure Button5Click(Sender: TObject); procedure Button6Click(Sender: TObject); procedure Button7Click(Sender: TObject); procedure quitter1Click(Sender: TObject); procedure matrice1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var form1: Tform1; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); var i,j,n:integer; begin S1.Visible:=true; n:=strtoint(edit1.Text); s1.RowCount:=strtoint(edit1.text)+1; s1.colCount:=strtoint(edit1.text)+1; s2.RowCount:=strtoint(edit1.text)+1; s2.colCount:=strtoint(edit1.text)+1; // Mettre les indices pour les lignes et les colonnes for i:= 1 to n do begin s1.Cells[0,i]:='a'+inttostr(i); s1.Cells[i,0]:='a'+inttostr(i); s2.Cells[0,i]:='a'+inttostr(i); s2.Cells[i,0]:='a'+inttostr(i); s3.Cells[0,i]:='a'+inttostr(i); s3.Cells[i,0]:='a'+inttostr(i); s4.Cells[0,i]:='a'+inttostr(i); s4.Cells[i,0]:='a'+inttostr(i); end; for i:=1 to n do for j:=1 to n do s1.Cells[i,j]:=inttostr(random(2)) end;

procedure TForm1.Button2Click(Sender: TObject); var i,j,n:integer; a,b,m:tpoint; v:array[1..50]of tpoint; flech:array[1..3]of tpoint; p:array[1..50,1..50]of integer; begin n:=strtoint(edit1.text); image1.picture:=image2.picture; image1.canvas.Brush.color:=clred; for i:=1 to n do for j:=1 to n do p[i,j]:=strtoint(s1.Cells[j,i]); for i:=1 to n do v[i]:=point(trunc(-cos((2*pi)*i/n)*(image1.width div 3))+(image1.width div 2),trunc(sin((2*pi)*i/n)*(image1.height div 3))+(image1.height div 2)); for i:=1 to n do for j:=1 to n do if (p[i,j]=1) and (i<> j) then begin a:=v[i]; b:=v[j]; image1.canvas.polyline([a,b]); m:=point((a.x+b.x)div 2,(a.y+b.y)div 2); flech[1]:=point(round(m.x+(-(b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.ya.y))),round(m.y+((b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.y-a.y)))); flech[2]:=m; flech[3]:=point(round(m.x+(-(b.x-a.x)+(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.ya.y))),round(m.y+(-(b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.y-a.y)))); image1.canvas.polygon(flech); end; for i:=1 to n do for j:=1 to n do if ((p[i,j]=1) and(i=j)) then begin image1.canvas.Brush.color:=clwhite; image1.Canvas.Ellipse(v[i].X+8,v[i].Y+8,v[i].X-30,v[i].Y-30); image1.Canvas.TextOut(v[i].X,v[i].Y,inttostr(i)); end ;

begin for i:=1 to n do begin image1.canvas.Brush.color:=clred; image1.canvas.pixels[v[i].x,v[i].y]:=clblue;

image1.canvas.ellipse(v[i].x-15,v[i].y-15,v[i].x+30,v[i].Y+30); image1.Canvas.TextOut(v[i].X,v[i].Y,inttostr(i)); end; end; end; procedure TForm1.Button3Click(Sender: TObject); var i,j,k,n:integer; m:array[1..50,1..50]of integer; begin S2.Visible:=true; n:=strtoint(edit1.text); for i:=1 to n do for j:=1 to n do m[i,j]:=strtoint(s1.cells[j,i]); for i:=1 to n do for j:=1 to n do begin if m[j,i]=1 then for k:=1 to n do if (m[i,k]=1) then m[j,k]:=1; end; for i:=1 to n do for j:=1 to n do s2.cells[i,j]:=inttostr(m[j,i]); end; procedure TForm1.Button4Click(Sender: TObject); var i,j,n:integer; a,b,m:tpoint; v:array[1..50]of tpoint; flech:array[1..3]of tpoint; mat:array[1..50,1..50]of integer; begin n:=strtoint(edit1.text); image1.canvas.Brush.color:=clblue; for i:=1 to n do for j:=1 to n do mat[i,j]:=strtoint(s2.Cells[j,i]); for i:=1 to n do

v[i]:=point(trunc(-cos((2*pi)*i/n)*(image1.width div 3))+(image1.width div 2),trunc(sin((2*pi)*i/n)*(image1.height div 3))+(image1.height div 2)); for i:=1 to n do for j:=1 to n do begin if (mat[i,j]=1) and (i<> j) then begin if(mat[i,j]<>strtoint(s1.Cells[j,i])) then begin a:=v[i]; b:=v[j]; image1.canvas.Pen.Color:=clblue; image1.canvas.polyline([a,b]); m:=point((a.x+b.x)div 2,(a.y+b.y)div 2); flech[1]:=point(round(m.x+(-(b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.ya.y))),round(m.y+((b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.y-a.y)))); flech[2]:=m; flech[3]:=point(round(m.x+(-(b.x-a.x)+(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.ya.y))),round(m.y+(-(b.x-a.x)-(b.y-a.y))*10/sqrt(sqr(b.x-a.x)+sqr(b.y-a.y)))); image1.canvas.polygon(flech); end; end;

end; for i:=1 to n do for j:=1 to n do if ((mat[i,j]=1) and(i=j)) then begin image1.canvas.pen.color:=clblack; image1.canvas.Brush.color:=clwhite; image1.Canvas.Ellipse(v[i].X+8,v[i].Y+8,v[i].X-30,v[i].Y-30); image1.Canvas.TextOut(v[i].X,v[i].Y,inttostr(i)); end ; for i:=1 to n do for j:=1 to n do if ((mat[i,j]=1) and(i=j)) then begin if(mat[i,j]<>strtoint(s1.Cells[j,i])) then begin image1.canvas.pen.color:=clblue; image1.canvas.Brush.color:=clwhite; image1.Canvas.Ellipse(v[i].X+8,v[i].Y+8,v[i].X-30,v[i].Y-30);

image1.Canvas.TextOut(v[i].X,v[i].Y,inttostr(i)); end; end; for i:=1 to n do begin image1.canvas.pen.color:=clblack; image1.canvas.pixels[v[i].x,v[i].y]:=clblue; image1.canvas.brush.color:=clred; image1.canvas.ellipse(v[i].x-15,v[i].y-15,v[i].x+30,v[i].Y+30); image1.Canvas.TextOut(v[i].X,v[i].Y,inttostr(i)); end;

end; procedure TForm1.Button5Click(Sender: TObject); var i,j,k,l,n:integer; m1,m2,m3,m4:array[1..50,1..50] of integer; begin S3.Visible:=true; n:=strtoint(edit1.text); s3.RowCount:=strtoint(edit1.text)+1; s3.colCount:=strtoint(edit1.text)+1; for i:=1 to n do for j:=1 to n do begin m1[i,j]:=strtoint(s2.Cells[j,i]); m3[i,j]:=m1[i,j]; m2[i,j]:=m1[i,j]; end; for l:=1 to n do begin for i:=1 to n do for j:=1 to n do begin m4[i,j]:=0; for k:=1 to n do m4[i,j]:=m4[i,j]+m2[i,k]*m1[k,j]; end; for i:=1 to n do for j:=1 to n do begin

m2[i,j]:=m4[i,j]; m3[i,j]:=m3[i,j]+m2[i,j]; end; end; for i:=1 to n do for j:=1 to n do s3.Cells[j,i]:=inttostr(m3[i,j]);

end; procedure TForm1.Button6Click(Sender: TObject); var i,j,n,k,p,h:integer; v,m:array[1..50,1..50]of integer; begin S4.Visible:=true; n:=strtoint(edit1.Text); s4.RowCount:=strtoint(edit1.text)+1; s4.colCount:=strtoint(edit1.text)+1; for i:=1 to n do for j:=1 to n do begin m[i,j]:=0; v[i,j]:=strtoint(s2.cells[j,i]); end; for i:=1 to n do begin m[i,1]:=i; k:=1; for j:=1 to n do begin if((v[i,j]=1) and (v[j,i]=1))then begin k:=k+1; m[i,k]:=j; end; end; end; for i:=1 to n do for j:=1 to n do s4.Cells[j,i]:=inttostr(m[i,j]);

for i:=1 to n do for j:=2 to n do begin p:=m[i,j]; if ((p<>0) and (p
end;

procedure TForm1.Button7Click(Sender: TObject); var i,n,j,p:integer; v:array[1..50]of tpoint; begin n:=strtoint(edit1.text); for i:=1 to n do v[i]:=point(trunc(-cos((2*pi)*i/n)*(image1.width div 3))+(image1.width div 2),trunc(sin((2*pi)*i/n)*(image1.height div 3))+(image1.height div 2)); for i:=1 to n do for j:=1 to n do begin p:=strtoint(s4.cells[j,i]); image1.canvas.brush.Color:=RGB((i*500),(i*300),(i*5000)); image1.canvas.ellipse(v[p].x-15,v[p].y-15,v[p].x+30,v[p].Y+30); image1.Canvas.TextOut(v[p].X,v[p].Y,inttostr(p)); end; end; procedure Tform1.quitter1Click(Sender: TObject); begin Form1.Close; end;

procedure Tform1.matrice1Click(Sender: TObject); begin form1.Close; end; END.