Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Графы в Паскале

Автор: freeda 4.11.2004, 19:54

Как нарисовать граф на Паскале?
Граф неориентированный, задается матрицей смежностей или матрицей инциденций, может содержать петли
help plzzz

Автор: Zero 4.11.2004, 20:53

Простейшая из программ... smile

Вот например приобразование матриц инцендентности в матрицу смежности и наоборот...

Код


Program Lab1;
Uses crt;
Const
     n=4;
Type
    matr1=array[1..n,1..n] of integer;
    matr2=array[1..n*n,1..2] of integer;
Var
   a:matr1;
   b:matr2;
   i,k,m:integer;
   z:char;

Procedure Vvod1(n:integer; var a:matr1);
var
   i,j:integer;
   z:char;
begin
     for i:=1 to n do
     for j:=1 to n do
     begin
          repeat
                write('a[',i,',',j,']=');
                z:=readkey;
                write(z);
                if z in ['0','1'] then
                   begin
                        if z='0' then a[i,j]:=0;
                        if z='1' then a[i,j]:=1;
                        writeln
                   end
                else
                    begin
                         writeln;
                         writeln(Матрица смежности состоит лиш из "0" и "1"');
                    end
          until z in ['0','1'];
     end
end;

Procedure Vvod2(var a:matr2);
Var
   k,n,i,j:integer;
   t,z:char;
begin
     write('‚введите кол-во строк=');
     repeat
           t:=readkey;
           writeln(t);
           for i:=1 to 9 do
           if t=chr(i+48) then n:=i;
     until t in ['2'..'9'];
     for i:=1 to n do
     for j:=1 to 2 do
     begin
          repeat
                write('b[',i,',',j,']=');
                z:=readkey;
                write(z);
                if z in ['1'..'9'] then
                   begin
                        if z='1' then a[i,j]:=1;
                        if z='2' then a[i,j]:=2;
                        if z='3' then a[i,j]:=3;
                        if z='4' then a[i,j]:=4;
                        if z='5' then a[i,j]:=5;
                        if z='6' then a[i,j]:=6;
                        if z='7' then a[i,j]:=7;
                        if z='8' then a[i,j]:=8;
                        if z='9' then a[i,j]:=9;
                        writeln
                   end
                else
                    begin
                         writeln;
                         writeln('Матрица инцендентности состоит лишь из цифр от "1" до "9"');
                    end
          until z in ['1'..'9'];
     end
end;

Procedure PREOBRAZOVANIE1(var m:integer);
var
   i,j,bi,bj:integer;
begin
      k:=0;
      for i:=1 to n do
      for j:=1 to n do
      if a[i,j]<>0 then k:=k+1;
      m:=k;

     for bi:=1 to k do
     for bj:=1 to 2 do
     b[bi,bj]:=0;

     bi:=1;
     for i:=1 to n do
     for j:=1 to n do
     if a[i,j]<>0 then
     begin
          b[bi,1]:=i;
          b[bi,2]:=j;
          bi:=bi+1;
     end;
end;

Procedure PREOBRAZOVANIE2;
var
   ij,i,j,k:integer;
begin
      k:=0;
      for i:=1 to n*n do
      if b[i,1]<>0 then k:=k+1;
      m:=k;

      for i:=1 to n do
      for j:=1 to n do
      a[i,j]:=0;

      for ij:=1 to k do
      begin
           i:=b[ij,1];
           j:=b[ij,2];
           a[i,j]:=1;
      end;
end;

Procedure Vyvod1(m:integer; var x:matr2);
var
   i,j:integer;
begin
     for i:=1 to m do
     begin
          writeln;
          write('B[',i,']: ');

          for j:=1 to 2 do
          begin
               write(b[i,j],' ');
          end;
     end;
end;

Procedure Vyvod2(var x:matr1);
var
   i,j:integer;
begin
     for i:=1 to n do
     begin
          writeln;
          for j:=1 to n do
          write(x[i,j],' ');
     end;
end;

Begin
     clrscr;
{*=============Организация вывода=================================*}
     writeln('Для преобразования матрицы смежности "A",');
     write('    в матрицу инцендентности "‚", введите: "');
     textcolor(63);
     write('1');
     textcolor(7);
     writeln('"');
     writeln;
     writeln('Для преобразования матрицы Инцендентности "‚",');
     write('     в матрицу смежности "A", введите: "');
     textcolor(63);
     write('2');
     textcolor(7);
     writeln('"');
     textcolor(2);
     writeln('├─────────────────────────────────────────────┤ ');
     textcolor(7);
     writeln;
     Repeat
           write('Выбор режима:');
           z:=readkey;

           if (z<>'1') and (z<>'2') then
              begin
                   clrscr;
                   writeln('Вводит можно только цифруг "1" или "2"');
              end;

           if z='1' then
              begin
                   clrscr;
                   Vvod1(n,a);
                   clrscr;
                   write('Матрица смежности "A":');
                   vyvod2(a);
                   PREOBRAZOVANIE1(m);
                   writeln; writeln;
                   write('Матрица инцендентности:');
                   Vyvod1(m,b);
              end;

           if z='2' then
              begin
                   clrscr;
                   Vvod2(b);
                   clrscr;

                   k:=0;
                   for i:=1 to n*n do
                   if b[i,1]<>0 then k:=k+1;
                   m:=k;

                   write('Матрица инцендентности:');
                   Vyvod1(m,b);
                   PREOBRAZOVANIE2;
                   writeln; writeln;
                   write('Матрица смежности "A":');
                   Vyvod2(a);
              end;
     Until (z='1') or (z='2');
     readkey;
End.

Freeda, если будут какие-то непонятки, то пиши... smile

Автор: Medved 5.11.2004, 00:55

Модератор: Название темы должно отражать ее суть!

Автор: freeda 5.11.2004, 20:37

Zero
спасибки конечно smile

но мне нужно именно нарисовать граф, ну там все эти ребра, вершины,
а преобразование я вроде как сделала
напиши pls как это сделать

Автор: Zero 5.11.2004, 21:08

Извини Freeda, но если ты имеешь ввиду нарисовать в графическом виде, то чтобы это сделать, то там впринципе работа не настолько сложно реализуемая, насколько творческая, и чтобы это сделать там нужно много времени, или покрайней мере я так сразу немогу тебе быстро что-нибудь предложить...
И кстати где такое тебе задали рисовать его в графическом виде, ведь его даже на системе программировани Delphi, чтобы нарисовать надо немало времени потратить, а на паскале, вообще врядли такое могли задать, может тебе лучше переспросить у прподователя задание поточнее, потому что рисовать граф на паскале это просто смешно, представь даже если там будет 100 вершин...
Кстати когда мне в том году задавли сделать граф, с которым нужно провести преобразования и т.п., то всегда имелось ввиду, что представление его осуществляется с помощью матриц, которые ты написала...

Автор: freeda 6.11.2004, 13:50

Вообщем мне сказали, что вершины нужно располагать примерно так:

Код


 for i:=1 to n do
     circle (x+cos(2*Pi*i/n)*r,y+sin(2*Pi*i/n)*r,5)

тогда это будут круги радиуса 5, расположенные в вершинах правильного многоугольника (x,y,r-центр и радиус описанной окружности). вот. Останется ребра и петли нарисовать. Хотя конечно для 100 вершин это не очень красиво получится
А задали мне это в универе, можно и на Delphi, но я там плохо ориентируюсь пока, поэтому и приходится на паскале... smile

Автор: Zero 6.11.2004, 16:46

Цитата

вот. Останется ребра и петли нарисовать.

Ну тогда, вот тебе пример для рисования ребер

Код


line(x1,y1,x2,y2);

где x1,y1,x2,y2 ─ координаты 1-ой и 2-ой точек, между которыми будет линия
А петли можно, нарисовать в виде элепса

Код


Ellipse(x1,y1,v,alpha,w,h)

где
x1,y1 ─ координаты,
v ─ кол-во пикселей вырезаных из эллипса (в твоём случае 0),
alpha ─ это угол на сколько он будет нарисован (в твоём случае 360),
w,h ─ ширена и высота соответственно.

Цитата

А задали мне это в универе, можно и на Delphi, но я там плохо ориентируюсь пока, поэтому и приходится на паскале...

Все говорят, я там плохо ориентируюсь, я и сам примерно пол года назад, думал что мне вообще не дано научится на нём програамировать, но а когда взял книжку и прочитал её (причём не всю), то оказалось, что там всё легко, ну покрайней мере, если знать паскаль... Там впринцепе всё однотипно, только вывод происходит не на экран с задаными координатами, а в тот объект который ты сама сделаешь... А нарисовать граф там уж куда легче, чем на этом глюченом паскале... smile