Графічне представлення графа засобами Delphi

Основним питанням, що виникає при розробці алгоритмів для опрацювання графів, є їх візуалізація (графічне представлення). З матемотичної точки зору граф зручно представляти у вигляді матриці суміжності. Проте з практичної точки, його доцільно було б представити у вигляді вершин і ребер на множині точок площини.

В даному параграфі створимо delphi-проект, який для побудови вершини графа буде використовувати наступний алгоритм: при натисканні лівої кнопки миші по робочій області на екрані будуть відображатись вершини графа, нумерація яких здійснюється в порядку зростання.
Після того, як вершини створено, необхідно поєднати їх ребрами. Для того, щоб створити ребро між парою вершин необхідно буде виконати наступні дії: натиснути ліву кнопку миші по першій вершині, після чого, не відпускаючи її, перетягнути курсор на другу вершину. Далі, відпускаємо ліву кнопку миші, і таким чином на екрані відобразиться неорієнтоване ребро.

Отже, запустимо Delphi і створимо новий проект. На формі розмістимо компонент Panel1, який буде слугувати контейнером для двох кнопок SpeedButton1 («Сиворити вершину») та SpeedButton2 («Створити ребро»). Також, розмістимо компонент Image1 — область форми, яка буде відповідати за відображення графа і встановимо для даних компонентів наступні властивості.

Компонент Властивість Значення
Panel1 Align alTop
SpeedButton1 Caption "Створити вершину"
SpeedButton1 GroupIndex 1
SpeedButton1 Width 100
SpeedButton1 Down True
SpeedButton2 Caption "Створити ребро"
SpeedButton2 GroupIndex 1
SpeedButton2 Width 100
Image1 Align alClient

В результаті форма набуде наступного вигляді.

Інтерфейс програми, яка здійснює побудову неорієнтованого графа в середовищі Delphi

Інтерфейс програми, яка здійснює побудову неорієнтованого графа в середовищі Delphi

Далі, для початку,  створимо два типи, які описують масив розмірності 10×10 та масив розмірності 10.

type
MAS = array [1..10, 1..10] of integer;
VECT = array [1..10] of integer;

І опишемо три глобальні змінні типу VECT, одну глобальну змінну типу MAS і три типу integer.

var
{ координати вершин графа по X та Y, та порядкові номера вершин }
MAS_X, MAS_Y, MAS_N: VECT;
{ матриця суміжності графа }
Matrix: MAS;
{ кількість вершин графа, порядковий номер вершини над якою було натиснуто ліву кнопку миші в режимі створення ребра, порядковий номер над якою було відпущено ліву кнопку миші в режимі створення ребра }
nodes_count, edge_start, edge_end: integer;

Після цього, для того, щоб реалізувати вище розглянутий алгоритм побудови та візуалізації неорієнтованого графа, на першому кроці, опишемо процедури, які на канві компонента Image1 малюють його вершини (draw_graph_node) та поєднюють їх відповідними неорієнтованими ребрами:

procedure TForm1.draw_graph_node(X, Y, N: integer; Image: TImage);
var
i: integer;
begin
With Image do
begin
Canvas.Pen.Width := 1;
Canvas.Pen.Color := clBlack;
Canvas.Brush.Color := clActiveCaption;
Canvas.Ellipse(X-12, Y-12, X+12, Y+12);
Canvas.TextOut(X — (Length(IntToStr(N))*3), Y — 5, IntToStr(N));
end;
end;

procedure TForm1.draw_graph_edge(A: MAS; X, Y: VECT; N: integer; Image: TImage);
var
i, j, text_X, text_Y: integer;
begin
Image.Canvas.Pen.Width := 1;
Image.Canvas.Pen.Color := clBlack;
Image.Canvas.Brush.Color := clWhite;
Image.Canvas.FillRect(Rect(0, 0, Image.Width, Image.Height));
for i := 1 to Ndo
for j := 1 to N do
if (A[i, j] <> 0) then
begin
Image.Canvas.MoveTo(X[i], Y[i]);
Image.Canvas.LineTo(X[j], Y[j]);
if (X[i] > X[j]) then
text_X := X[j] + ((X[i]-X[j]) div 2) — (Length(IntToStr(A[i, j]))*3)
else
text_X := X[i] + ((X[j]-X[i]) div 2) — (Length(IntToStr(A[i, j]))*3);
if (Y[i] > Y[j]) then
text_Y := Y[j] + ((Y[i]-Y[j]) div 2) — 6
else
text_Y := Y[i] + ((Y[j]-Y[i]) div 2) — 6;
Image.Canvas.TextOut(text_X, text_Y, IntToStr(A[i, j]));
end;
end;

Далі, весь процес малювання неорієнтованого графа організуємо з допомогою трьох методів обробників подій OnMouseDown, OnMouseMove і OnMouseUp компонента Image1. Отже, для початку, скористаємось подією OnMouseDown і в обробник даної події вставимо наступний код:

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
var
i, j: integer;
p: boolean;
begin
p := True;
if (SpeedButton1.Down = True) then
begin
{ Якщо ліва кнопка миші натиснута }
if (ssLeft in Shift) then
begin
{ Якщо кількість вершин графа відмінна від нуля }
if (nodes_count > 0) then
for i := 1 to nodes_count do
{ Виконуємо провірку чи ккординати мишки не співпадають з вже побудованими вершинами графа. Це зроблено для того, щоб одна вершина не перекривалась другою }
if (X > (MAS_X[i] — 50)) and (X < (MAS_X[i] + 50)) and (Y > (MAS_Y[i] — 50)) and (Y < (MAS_Y[i] + 50)) then
begin
p := False;
break;
end;
{ Якщо координати курсора не співпадають з жодною вершиною, то створюємо нову }
if (p) then
begin
{ Значення змінної, яка відповідає за кількість створених вершин графа збільшимо на одиницю }
nodes_count := nodes_count + 1;
{ Збережемо координати нової вершини та її порядковий номер у відповідні масиви }
MAS_X[nodes_count ] := X;
MAS_Y[nodes_count ] := Y;
MAS_N[nodes_count ] := nodes_count;
{ Намалюємо новоствоерну вершину на канві компонента Image1 }
draw_graph_node(X, Y, nodes_count , Image1);
end;
end;
end;
end;

Запустивши проект на виконання бачимо, що при натисканні лівою кнопкою миші по компоненті Image1 на екрані відображаються вершини графа.

Створення

Побудова вершин неорієнтованого графа в середовищі Delphi

Далі, реалізуємо процес поєднання двох вершин неорієнтованим ребром. Для цього доповнимо подію OnMouseDown компонента Image1 наступним кодом:

{ Якщо програма знаходиться в режимі створення неорієнтованого ребра }
if (SpeedButton2.Down = True) then
begin
{ Якщо ліва кнопка мишки натиснута }
if (ssLeft in Shift) then
for i := 1 to nodes_count do
begin
{ Перевіряємо, чи координати мишки знаходяться в межах створеної вершини }
if (X >= (MAS_X[i] — 12)) and (X <= (MAS_X[i] + 12)) and (Y >= (MAS_Y[i] — 12)) and (Y <= (MAS_Y[i] + 12)) then
begin
{ Збережемо номер вершини в глобальну змінну }
edge_start := i;
break;
end;
end;
end;

Після чого, на подію OnMouseMove реалізуємо вивід уявного ребра, яке буде відображатися на робочій області у вигляді пунтирної лінії. Це зроблено для того, щоб користувач міг візуально контролювати процес переміщення курсора між парою вершин.

procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
var
i: integer;
begin
{ Якщо значення змінної, яка зберігає порядковий номер вершини не дорівнює нулю і натиснута ліва кнопка миші }
if (edge_start <> 0) and (ssLeft in Shift) then
begin
{ На канві компонента Image1 малюємо неорієнтовані ребра }
draw_graph_edge(Matrix, MAS_X, MAS_Y, nodes_count, Image1);
{ Малюємо уявне неорієнтоване ребро }
Image1.Canvas.Pen.Style := psDot;
Image1.Canvas.MoveTo(MAS_X[edge_start], MAS_Y[edge_start]);
Image1.Canvas.LineTo(X, Y);
Image1.Canvas.Pen.Style := psSolid;
{ Малюємо вершини графа }
for i := 1 to nodes_count do
draw_graph_node(MAS_X[i], MAS_Y[i], i, Image1);
end;
end;

Запустимо проект на виконання, розмістимо на робочій області (компонент Image1) дві вершини, і спробуємо поєднати їх ребром. Бачимо, що при переміщенні курсора над компонентом Image1 (ліва кнопка миші натиснута), на екрані відображається уявне ребро, яке починається у вершині, над якою було натиснуто ліву кнопку миші і кінець якого співпадає з координатами курсора.

Побудова неорієнтованого ребра в середовищі Delphi

Побудова неорієнтованого ребра в середовищі Delphi

І на останньому кроці, реалізуємо процес побудови ребра, яке, згідно з алгоритмом, створюється при відпусканні лівої кнопки миші над вершиною, координати якої відмінні від координат вершини, над якою було натиснуто ліву кнопку. Для цього на подію OnMouseUp компонента Image1 напишемо наступний код.

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var
i, j: integer;
begin
{ Малюємо неорієнтовані ребра, які поєднюють вершини графа }
draw_graph_edge(Matrix, MAS_X, MAS_Y, nodes_count, Image1);
{ Малюємо вершини графа }
for i := 1 to nodes_count do
draw_graph_node(MAS_X[i], MAS_Y[i], i, Image1);
if (edge_start <> 0) then
begin
for i := 1 to nodes_count do
{ Якщо координати курсора містяться в межах побудованої вершини графа  }
if (X >= (MAS_X[i] — 12)) and (X <= (MAS_X[i] + 12)) and (Y >= (MAS_Y[i] — 12)) and (Y <= (MAS_Y[i] + 12)) then
begin
{ Зберігаємо порядковий номер вершини, над якою було відпущено кнопку мишки }
edge_end := i;
{ Перевіряємо чи відмінні порядкові номери вершин над якою була натиснута кнопка миші і відпущена }
if (edge_end <> edge_start) then
begin
{ Генеруємо випадкове число, яке відповідає за довжину ребра і зберігаємо його у відповідній комірці матриці суміжності }
randomize;
Matrix[edge_end, edge_start] := random(10) + 1;
{ Маліємо щойностворене ребро графа }
draw_graph_edge(Matrix, MAS_X, MAS_Y, nodes_count, Image1);
{ Маліємо вершини графа }
Image1.Canvas.Pen.Style := psSolid;
for j := 1 to nodes_count do
draw_graph_node(MAS_X[j], MAS_Y[j], j, Image1);
break;
end;
end;
end;
end;

Таким чином ми створили повноцінний проект, який можна використовувати при створенні програм, які реалізують алгоритми знаходження дерева мінімальної вартості для неорієнтованого графа. Відмітимо, що саме такий підхід побудови графа використовується у проектах, які реалізують  алгоритм Прима та алгоритм Крускала.

Створення неорієнтованого графа в середовищі програмування Delphi

Створення неорієнтованого графа в середовищі програмування Delphi

Скачати delphi-проект Візуалізація неорієнтованого графа засобами Delphi.

Матеріал був корисним, поділись в соціальних мережах:

Коментарі

11 коментарів по темі “Графічне представлення графа засобами Delphi”
  1. andrey_khorolskiy пише:

    Дякую за представлену реалізацію. Проте в запропонованій реалізації є декілька неточностей, можливо це мені здається. В процесі роботи з програмою, а також як видно із Вашого рис. 4 (Створення неорієнтованого графу) чисельне значення ваги ребер (дуг) графу не відповідає довжині. На рис. 4 чітко видно що довжина ребра 1−4 ідентична довжині ребра 4−3, а на рис. 4 показники значно відрізняються 9 та 4. Чи є можливість усунути цей недолік?

  2. admin пише:

    Доброго вечора Андрій. Ми раді, що наш матеріал вкотре зацікавив Вас. А що стосується Вашого питання, то хочеться зазначити, що в даній реалізації, значення ваги кожного з ребер побудованого графа, ніякого відношення з відстанню між вершинами не мають. Вони генерується випадковим чином з допомогою функції Random.

  3. andrey_khorolskiy пише:

    Дякую за відповідь, тепер все стало зрозуміло.

  4. admin пише:

    Немає за що. Якщо ще виникнуть якісь питання, звертайтесь. Завжди буду радий відповісти на будь-яке з них.

  5. andrey_khorolskiy пише:

    Дуже гарно описано процес побудови та візуалізації, проте на початку необхідно вказувати, що перед початком створення події OnMouseDown необхідно прописати процедуру draw_graph_node. Це внесе одразу ясність, а так необхідно завантажувати проект та розбиратися у коді. Дана ремарка дозволить значно спростити сприйняття.

  6. admin пише:

    Доброго вечора Андрій. Ми раді, що Ви не просто читаєте наші матеріали, а робите певні висновки та вносите корективи щодо прочитаного. Для нас це дуже важливо. Найближчим часом даний матеріал буде переписано з урахуванням Ваших поправок.

  7. andrey_khorolskiy пише:

    Дякую за відповідь. Дуже приємно коли є зворотній зв'язок з адміністрацією сайту. Ви одні з небагатьох, які представляють якісний контент, а головне українською.

    В процесі роботи виникло декілька запитань, скоріше уточнень:

    1) бажано описати також процес очищення робочої області вікна;

    2) також слід звернути увагу, що при побудові ребер графу у фрагменті коду:

    Image.Canvas.Pen.Width := 1;

    Image.Canvas.Pen.Color := clBlack;

    Image.Canvas.Brush.Color := clWhite;

    Image.Canvas.FillRect(Rect(0, 0, Image.Width, Image.Height));

    for i := 1 to Ndo

    for j := 1 to N do

    if (A[i, j] 0) then

    begin

    Image.Canvas.MoveTo(X[i], Y[i]);

    Image.Canvas.LineTo(X[j], Y[j]);

    бажано вказувати номер зображення. наприклад Image1.Canvas.Pen.Color := clBlack; — можливо, дана проблема виникає тільки у мене, але мені це уточнення допомогло. Дана ремарка доцільна при розміщенні на робочому вікні декілької зображень, якщо тільки одне зображення все коректно.

    Дані пропозиції не принципові та не можуть впливати на позитивну оцінку запропонованих підходів.

  8. admin пише:

    Шановний Андрію, у вказаному Вами коді Image — це не компонент на канві якого здійснюється графічне представлення неорієнтовани графа, а лише один з параметрів процедури draw_graph_edge (малює неорієнтовані ребра). Компонент, на якому відображається граф вказується при виклику даної процедури. В нашому випадку це компонент Image1:

    draw_graph_edge(Matrix, MAS_X, MAS_Y, nodes_count, Image1);

  9. andrey_khorolskiy пише:

    Зрозуміло, більше питань не маю.

  10. admin пише:

    Добре Андрію. Якщо в процесі вивчення наших матеріалів ще якийсь момент виявиться для Вас незрозумілим, звертайтесь. Завжди будемо раді допомогти.

  11. admin пише:

    Доброго дня Андрію. В процесі редагування даного матеріалу згідно з Вашими поправками було виявлено, що використання процедури очищення робочої області (clear_img), в даному випадку, являється зайвим. Тому її повністю було видалено з програмного коду. Проте, хочеться зазначити, що застосування даної процедури було б доречніше, при розробці більш складних delphi-проектів, які б дозволяли не тільки створювати новий неорієнтований граф, а і редагувати існуючий (видаляти вершини, видаляти ребра, переміщувати вершини,...). В такому випадку необхідно було б очистити робочу область і побудувати граф заново, згідно з внесеними змінами.

Якщо тобі сподобалась дана тема, залиш свій коментар