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

В параграфі Графічне представлення графа засобами Delphi ми створили проект, який малював неорієнтований граф на канві компонента Image1. Сьогодні розглянемо алгоритм побудови орієнтованого графа, тобто графа ребрам якого присвоєно певний напрямок. Послідовність дій при побудові вершин орієнтованого графа аналогічна послідовності дій, яку ми здійснювали у випадку неорієнтованого. Проте, процес побудови орієнтованого ребра дещо відрізняється. Для того, щоб нарисувати орієнтоване ребро, будемо використовувати наступний алгоритм: нехай маємо дві вершини графа (зображені у вигляді кола з центром у точках V1 та V2 і радіусом r). Для того, щоб побудувати ребро проведемо від точки V1 до V2 пряму лінію. Далі для того, щоб задати напрямок необхідно знайти точку перетину кола з центром в точці V2 та радіусом r з прямою, яка прорходить через дві точки V1 та V2. В результаті отримаємо деяку точку A. Далі, побудуємо деяке уявне коло з радіусом r1 (на малюнку зображено штрихпунктирною лінією), і знову знайдемо точку перетину даного кола з прямою V1V2. Отримуємо деяку точку B. Після того, як координати точки B відомі, виконуємо поворот даної точки відносно точки A, проти годинникової стрілки на кут l. В результаті отримуємо точку B1. Аналогічно, виконуємо поворот точки B за годинниковою стрілкою — отримуємо точку B2. Таким чином ми отримали трикутник AB1B2, який і буде вказувати напрямок орієнтованого ребра.

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

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

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

type
MAS1 = array [1..2, 1..2] of real;
VECT1 = array [1..2] of real;
VECT2 = array [1..4] of TPoint;

Далі задамо дві функції, одна з яких описує рівняння прямої, яка проходить через дві точки A1(x1;y1) та A2(x2;y2) і друга — рівняння кола з центром в деякій точці O(a;b) і радіусом r.

function TForm1.f1(x, y: real; x1, y1, x2, y2: real): real;
begin
f1 := (y1-y2)*x + (x2-x1)*y + (x1*y2 — x2*y1);
end;
function TForm1.f2(x, y, a, b, r: real): real;
begin
f2 := (x-a)*(x-a) + (y-b)*(y-b) -r*r;
end;

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

function TForm1.df1x(x, y, x1, y1, x2, y2: real): real;
var
h: real;
begin
h := 0.01;
df1x := (f1(x+h, y, x1, y1, x2, y2) -f1(x, y, x1, y1, x2, y2))/h;
end;
function TForm1.df2x(x, y, a, b, r: real): real;
var
h: real;
begin
h := 0.01;
df2x := (f2(x+h, y, a, b, r) -f2(x, y, a, b, r))/h;
end;
function TForm1.df1y(x, y: real; x1, y1, x2, y2: real): real;
var
h: real;
begin
h := 0.01;
df1y := (f1(x, y+h, x1, y1, x2, y2) -f1(x, y, x1, y1, x2, y2))/h;
end;
function TForm1.df2y(x, y, a, b, r: real): real;
var
h: real;
begin
h := 0.01;
df2y := (f2(x, y+h, a, b, r) -f2(x, y, a, b, r))/h;
end;

І на останньому кроці опишемо процедуру set_edges_direction, яка відповідатиме за візуалізацію напрямку для кожного ребра графа.

procedure TForm1.set_edges_direction(Mas: MAS; Color: TColor);
var
A, M1, M2: MAS1;
b, X, XY, rXY, XY1, rXY1: VECT1;
xp, yp, xn, yn, resx, resy, eps, x1, x2, y1, y2, a1, b1, r: real;
xp1, yp1, xn1, yn1, resx1, resy1, x11, x21, y11, y21, a11, b11, r1: real;
i, j, ii: integer;
P: VECT2;
pnt: TPoint;
begin
eps := 0.001;
M1[1, 1] := Cos(Pi/25); M1[1, 2] := -Sin(Pi/25);
M1[2, 1] := Sin(Pi/25); M1[2, 2] := Cos(Pi/25);
M2[1, 1] := Cos(Pi/25); M2[1, 2] := Sin(Pi/25);
M2[2, 1] := -Sin(Pi/25); M2[2, 2] := Cos(Pi/25);
for i := 1 to nodes_count do
for j := 1 to nodes_count do
begin
if (Mas[i, j] <> 0) then
begin
xp := MAS_X[i];
yp := MAS_Y[i];
x1 := MAS_X[i]; y1 := MAS_Y[i];
x2 := MAS_X[j]; y2 := MAS_Y[j];
a1 := MAS_X[j]; b1 := MAS_Y[j];
r := 12;
{ За методом Ньютона знаходимо координати точки А }
repeat
A[1, 1] := df1x(xp, yp, x1, y1, x2, y2); A[1, 2] := df1y(xp, yp, x1, y1, x2, y2);
A[2, 1] := df2x(xp, yp, a1, b1, r); A[2, 2] := df2y(xp, yp, a1, b1, r);
b[1] := -f1(xp, yp, x1, y1, x2, y2); b[2] := -f2(xp, yp, a1, b1, r);
X := Kramer(A, b);
xn := xp + X[1]; yn := yp + X[2];
resx := abs(xn — xp);
resy := abs(yn — yp);
xp := xn;
yp := yn;
until((resx < eps) and (resy < eps));
pnt.X := Round(xp); pnt.Y := Round(yp);
P[1] := pnt;
xp1 := xp;
yp1 := yp;
x11 := MAS_X[i]; y11 := MAS_Y[i];
x21 := MAS_X[j]; y21 := MAS_Y[j];
a11 := MAS_X[j]; b11 := MAS_Y[j];
r1 := 27;
{ За методом Ньютона знаходимо координати точки B }
repeat
A[1, 1] := df1x(xp1, yp1, x11, y11, x21, y21); A[1, 2] := df1y(xp1, yp1, x11, y11, x21, y21);
A[2, 1] := df2x(xp1, yp1, a11, b11, r1); A[2, 2] := df2y(xp1, yp1, a11, b11, r1);
b[1] := -f1(xp1, yp1, x11, y11, x21, y21); b[2] := -f2(xp1, yp1, a11, b11, r1);
X := Kramer(A, b);
xn1 := xp1 + X[1]; yn1 := yp1 + X[2];
resx1 := abs(xn1 — xp1);
resy1 := abs(yn1 — yp1);
xp1 := xn1;
yp1 := yn1;
until((resx1 < eps) and (resy1 < eps));
XY1[1] := xp1 — xp; XY1[2] := yp1 — yp;
{ Знаходимо координати точки B1, тобто здійснюємо поворот точки B проти годинникової стрілки відносно точки A }
rXY1 := multiply(M1, XY1);
pnt.X := Round(rXY1[1] + xp); pnt.Y := Round(rXY1[2]+ yp);
P[2] := pnt;
{ Знаходимо координати точки B2, тобто здійснюємо поворот точки B за годинниковою стрілкою відносно точки A }
rXY := multiply(M2, XY1);
pnt.X := Round(xp1); pnt.Y := Round(yp1);
P[3] := pnt;
pnt.X := Round(rXY[1] + xp); pnt.Y := Round(rXY[2] + yp);
P[4] := pnt;
Image1.Canvas.Brush.Color := Color;
{ Малюємо стрілку, яка вказує напрямок орієнтованого ребра графа у вигляді трикутника AB1B2 }
Image1.Canvas.Polygon(P);
end;
end;
end;

Також, давайте опишемо функцію, яка використовуються при рішенні системи за методом Ньютона, а саме функцію Kramer (призначена для знаходження розв'язку системи лінійних рівнянь); функцію det, яка знаходить детермінант матриці і використовується при знаходжені коренів системи рівнянь за методом Крамера та функцію multiply, з допомогою якої визначаємо координати точок B1 та B2.

{ Функція, яка використовуючи алгоритм методу Крамера знаходить розв'язок системи з двох лінійних рівнянь }
function TForm1.kramer(A: MAS1; b: VECT1): VECT1;
var
i, j: integer;
d, d1: real;
res: VECT1;
A1: MAS1;
begin
d := det(A);
for i := 1 to 2 do
begin
A1 := A;
for j := 1 to 2 do
A1[j, i] := b[j];
d1 := det(A1);
res[i] := d1/d;
end;
kramer := res;
end;
{ Функція, яка обчислює детермінант матриці розмірності 2×2 }
function TForm1.det(A: MAS1): real;
begin
det := A[1, 1]*A[2, 2] — A[1, 2]*A[2,1];
end;
{ Функція, яка здійснює множення квадратної матриці на вектор стовбець }
function TForm1.multiply(A: MAS1; b: VECT1): VECT1;
var
res: VECT1;
i, j: integer;
S: real;
begin
for i := 1 to 2 do
begin
S := 0;
for j := 1 to 2 do
S := S + A[i, j] * b[j];
res[i] := S;
end;
multiply := res;
end;

Після запуску проекту на виконання бачимо, що напрямок орієнтованого ребра не відображається. Для того, щоб напрямок відображався необхідно здійснити виклик процедури set_edges_direction у обробниках подій OnMouseMove та OnMouseUp компонента Image1.

procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
var
i: integer;
begin
{ Якщо значення змінної, яка зберігає порядковий номер вершини не дорівнює нулю і натиснута ліва кнопка миші }
if (edge_start <> 0) and (ssLeft in Shift) then
begin
{ Очищаємо робочу область }
clear_img(Image1);
{ На канві компонента 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);
Вказуємо напрямок ребер для орієнтованого графа }
set_edges_direction(Matrix, clBlack);
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;
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);
{ Вказуємо напрямок ребер для орієнтованого графа }
set_edges_direction(Matrix, clBlack);
{ Малюємо вершини графа }
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);
{ Вказуємо напрямок  для щойно створеного ребра графа }
set_edges_direction(Matrix, clBlack);
{ Маліємо вершини графа }
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;

Інтерфейс програми, яка малює на канві компонента Image1 орієнтований граф

Інтерфейс програми, яка малює на канві компонента Image1 орієнтований граф

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

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

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