Tuesday, 29 September 2009

Primera aplicación con Thundax Box Manager (Parte I)

Bueno, lo prometido es deuda y aquí tenéis la primera representación a la utilización de éste nuevo framework que me he creado from scratch. Ésta primera aplicación utilizando mi unnamed framework consiste como no, en el dibujado de un grafo (dirigido o no) y el correspondiente cálculo del camino mínimo aplicando el algoritmo de Dijkastra. He tenido que tirar de mis apuntes de matemática discreta, pero estoy muy contento al poder realizar ésta primera aplicación sin muchas complicaciones en la utilización de los objetos personalizados. Esta implementación sencilla es muy fácil de utilizar, simplemente dibujamos todo el grafo con sus conexiones (con dirección simple o doblemente dirigidas, ésto provoca que en la lista de adyacentes se publican las dos direcciones, tanto la ida como la vuelta). Luego tenemos que marcar el origen y el final mediante unos colores concretos y marcamos los vértices y aristas con números para identificarlos y sus pesos.

Lo veremos mejor con un ejemplo:

Como veis en el grafo, todas las aristas son de doble sentido y tiene marcado el peso de pasar por ése camino. Los vertices (TBox) estan numerados y tenemos marcado también con colores el origen (1 - clLime) y el final (6 - clFucshia). Hay que marcarlos siempre con éstos colores para que funcione. Una vez hecho ésto, vamos a Extension -> DijKstra Algorithm y nos devolverá el camino mínimo marcado en rojo.

Aún tengo que arreglar alguna cosa del algoritmo, porque aún no afina muy bien, pero de momento la cosa funciona correctamente, y permite de una manera rápida, sencilla y gráfica, montar nuestros propios grafos y luego calcular el camino mínimo.

Aquí os dejo el código fuente del algoritmo:
  • Dijkstra algorithm with Delphi:


procedure TfrmMain.Dijkstra1Click(Sender: TObject);
var
AdjacentList: array[1..MaxVertexs, 1..MaxVertexs] of Integer;
VertexList: ArrayOfInteger;
predecessor: ArrayOfInteger;
visiteds: array[1..MaxVertexs] of boolean;
vertexs, edges, firstNode, LastNode: integer;
i, j, pos1, pos2, min: integer;
Conn: TConnector;
textList: string;
begin
vertexs := boxlist.count;
edges := connectorList.count;
firstNode := -1;
LastNode := -1;
for i := 0 to BoxList.count - 1 do
begin
if BoxList.items[i].boxColor = clLime then
firstNode := StrToInt(BoxList.items[i].getText);
if BoxList.items[i].boxColor = clFuchsia then
LastNode := StrToInt(BoxList.items[i].getText);
end;
if (firstNode = -1) or (LastNode = -1) then
exit;

for i := 1 to MaxVertexs do
for j := 1 to MaxVertexs do
begin
AdjacentList[i, j] := NoWeight;
if i = j then
AdjacentList[i, j] := 0
end;

for i := 0 to edges - 1 do
begin
Conn := ConnectorList.items[i];
pos1 := StrToInt(Conn.SourceBox.GetText);
pos2 := StrToInt(Conn.targetBox.GetText);
AdjacentList[pos1, pos2] := StrToInt(Conn.Line.GetText);
if Conn.Line.ClassNameIs('TAbstractDottedDoubleArrowLine') or
Conn.Line.ClassNameIs('TAbstractSimpleDoubleArrowLine') then
AdjacentList[pos2, pos1] := StrToInt(Conn.Line.GetText);
end;

for i := 1 to vertexs do
begin
VertexList[i] := AdjacentList[firstNode, i];
predecessor[i] := firstNode;
visiteds[i] := false;
end;
VertexList[firstNode] := 0;
visiteds[firstNode] := true;

j := firstNode;
repeat
for i := 1 to LastNode do
if (not visiteds[i]) and (VertexList[i] > VertexList[j] + AdjacentList[j, i]) then
begin
VertexList[i] := VertexList[j] + AdjacentList[j, i];
predecessor[i] := j;
end;
min := NoWeight;
for i := 1 to vertexs do
if (not visiteds[i]) and (VertexList[i] < min) then
begin
min := VertexList[i];
j := i;
end;
if (min <> NoWeight) then
visiteds[j] := true;
until (visiteds[LastNode]) or (min = NoWeight);

textList := '';
while (LastNode <> firstNode) do
begin
textList := textList + IntToStr(LastNode);
LastNode := predecessor[LastNode];
end;

textList := Swap(textList + IntToStr(FirstNode));

i := 1;
while i < length(textList) do
begin
for j := 0 to connectorList.count - 1 do
begin
Conn := ConnectorList.items[j];
if ((Conn.SourceBox.getText = textList[i]) and
(Conn.TargetBox.getText = textList[i + 1])) or
((Conn.SourceBox.getText = textList[i + 1]) and
(Conn.TargetBox.getText = textList[i])) then
begin
Conn.SourceBox.lineColor := clRed;
Conn.TargetBox.lineColor := clRed;
Conn.Line.LineColor := clRed;
end;
end;
i := i + 1;
end;
end;


Podéis descargar la última versión de la aplicación aquí: ThundaxBoxManager v2.0.0 build 65.exe.
  • Enlaces de interés:
Dijkstra applet Demos.


0 comments:

Post a Comment