Разработка приложения интерактивного построения графа

Размещено на http://www.allbest.ru/

Разработка приложения интерактивного построения графа

Хасанова Светлана Леонидовна, кандидат наук, доцент, доцент

Иванов Евгений Юрьевич, бакалавр, студент

Башкирский государственный университет



В работе реализовано приложение интерактивного построения графа.

В настоящее время теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Теория графов предоставляет удобный язык для описания программных моделей. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи реальной действительности. Теория графов имеет широкие приложения, и важным является наличие наглядной графической интерпретации состояния графа. Визуализация графов и их алгоритмов позволяют лучше понять состояние системы. В работах [2,3] были сделаны попытки визуализация графов и их алгоритмов средствами MacromediaFlash.

Представленное приложение визуализации построения графа реализовано в среде разработки Embarcadero RAD Studio 10.1 Berlin. Данная среда разработки была выбрана в связи с тем, что она позволяет наиболее удобно реализовать структуру данных графа. В качестве структур данных для описания графа были использованы записи, списки, классы.

type

TEdge = record

istart :integer; //где istart -- индекс первой вершины ребра в TVertexList

ifinish:integer; // ifinish -- второй

value:integer;

end;

TVertexList = TList;

TEdgeList = TList;

TGraph = class

Vertex:TVertexList;

Edges :TEdgeList;

constructor Create;

destructor Destroy; override;

procedure Draw( Canvas:TCanvas );

functionFindVertexIndex( constmouse:TPoint; out index:integer ):Boolean;

procedureDeleteVertex( index:integer );

end;

граф алгоритм визуализация программирование

При запуске приложения пользователю предлагается пустая форма для построения графа (рис. 1).

Рисунок 1. Пустая форма

Для начала построения графа пользователю необходимо нажать на форму левой кнопкой мыши, после чего на ней появится первая вершина графа (рис 2). Чтореализованоследующимобразом:

if Shift = [ssLeft] then

begin

ifGraph.FindVertexIndex( StartPt, i ) then

IndexPt :=i

else

IndexPt :=Graph.Vertex.Add( StartPt );

IsStartPt := true;

InvalidateRect( Handle, nil, false );

exit;

end;

i:=1;

Canvas.Brush.Color := clSkyBlue;

for p in Vertex do

begin

Canvas.Ellipse(p.X-R, p.Y-R, p.X+R, p.Y+R );

Canvas.TextOut(p.X -- (Length(IntToStr(i))*3), p.Y -- 6, IntToStr(i));

inc(i);

end;

Аналогичным образом создаются все последующие вершины.

Рисунок 2. Построение вершин

Удаление вершины реализовано нажатием на вершине правой кнопкой мыши, при этом оставшиеся вершины будут переиндексированы:

if Shift = [ssRight] then

begin

ifGraph.FindVertexIndex( StartPt, i ) then

Graph.DeleteVertex(i );

InvalidateRect( Handle, nil, false );

end;

procedureTGraph.DeleteVertex( index:integer );

var i:integer;

e:TEdge;

begin

i := 0;

whilei<Edges.Count do

begin

e := Edges[i];

if(e.istart = index )or( e.ifinish = index )then

begin

Edges.Delete(i);

continue;

end;

Inc(i );

end;

Vertex.Delete( index );

//одна вершина была удалена -- нужна переиндексовка рёбер

for i:=0 to Edges.Count-1 do

begin

e := Edges[i];

ife.istart>= index then

Dec(e.istart );

ife.ifinish>= index then

Dec(e.ifinish );

Edges[i] := e;

end;

end;

На следующем этапе строится ребро графа. Для этого, зажав клавишу «Clrl» и левую кнопку мыши, протянем ребро от начальной до конечной вершины. При этом происходит интерактивная прорисовка графа (рис. 3).

Рисунок 3. Построение ребра

Для построения ребра был реализован следующий код:

ifssCtrl in Shift then

begin

if not Graph.FindVertexIndex( StartPt, i ) then

exit;

IndexPt :=i;

StartPt :=Graph.Vertex[i];

FinishPt :=StartPt;

IsStartLn := true;

InvalidateRect( Handle, nil, false );

exit;

end;

ifIsStartLn then

begin

FinishPt := Point(X,Y);

IsFinishLn :=Graph.FindVertexIndex( FinishPt, i );

ifIsFinishLn then

begin

IndexFinish :=i;

FinishPt :=Graph.Vertex[i];

end;

InvalidateRect( Handle, nil, false );

end;

Отпустив зажатые клавиши, пользователю будет предложено ввести вес ребра, посредством диалогового окна (рис. 4), реализованного следующим образом:

begin

ifIsStartLn and IsFinishLn then

begin

e.istart := IndexPt;

e.ifinish := IndexFinish;

str := InputBox('Введите вес ребра', 'Вес: ', '0');

e.value := strtoint(str);

ife.istart<>e.ifinishthen // исключаем создание ребра -- петли

Graph.Edges.Add( e );

end;

IsFinishLn := false;

IsStartLn := false;

IsStartPt := false;

InvalidateRect( Handle, nil, false );

end;

Рисунок 4. Диалоговое окно выбора веса ребра

Особенностью реализованного приложения является возможность передвигать вершины в более удобную позицию, использовав технологию “Drag-Draw”. Для этого пользователю надо зажать левую кнопку мыши на вершине, которую необходимо передвинуть (рис 5). При этом будет перерисована как сама вершина, так и исходящие из нее ребра, с помощью следующего кода:

if Shift = [ssLeft] then

begin

ifGraph.FindVertexIndex( StartPt, i ) then

IndexPt :=i

else

IndexPt :=Graph.Vertex.Add( StartPt );

IsStartPt := true;

InvalidateRect( Handle, nil, false );

exit;

end;

ifIsStartPt then

begin

Graph.Vertex[IndexPt] := Point(X,Y);

InvalidateRect( Handle, nil, false );

exit;

end;

На рис. 5 приведен пример «перетаскивания» вершины 2.

Рисунок 5. Перемещение вершин



Графы имеют множество приложений: для описания алгоритмов автоматического проектирования, при установлении разного рода соответствий, при решении транспортных задач, в программировании, теории игр и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Теория графов, на данный момент, применяется и в таких областях, как экономика, психология и биология [1]. Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории структур данных, поэтому их алгоритмы сложны для понимания и требуют визуализации.



Список литературы

1. Березина Л.Ю. Графы и их применение М.: Просвещение, 1979. - 143 с.

2. Хасанова С.Л., Зайнуллин Ф.Ф. Интерактивное приложение Визуализация алгоритмов на графах // Роспатент № 2016619842 31.08.2016

Размещено на Allbest.ur