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

Aquí os dejo la última versión de Thundax Box Manager que incluye el algoritmo Dijkstra para la búsqueda del camino más corto (versión mejorada). Ahora el algoritmo funciona correctamente y permite generar grafos de hasta 100 vértices (realmente podríamos poner los que quisiéramos). En las siguientes imágenes podréis ver como se busca el camino más corto marcando un vértice inicial y uno final. Si os fijáis el código no es muy extenso y es de fácil comprensión (tampoco he tardado mucho en sacarlo, la idea y su funcionamiento los tenía muy claro). Ahora simplemente es cuestión de tiempo el empezar a automatizar ideas y empezar a dibujar cosas pre-tratadas para hacer más amena la inserción de bloques en el lienzo. También tengo pensado mejorar la capacidad de copiar y pegar propiedades, ya que he notado que la edición es bastante lenta y hay que mejorar eso. También el clonado de objetos debería ser más fácil y desde el teclado poder hacer alguna cosa. Cada vez que manejo la herramienta me voy dando cuenta de las cosas que aún le faltan y es que aún está bastante verde, pero por lo menos hay una buena base, bien estructurada con una buena implementación hacia la Orientación a Objetos, Persistencia de datos y un buen uso de los patrones de diseño.


Aquí os dejo los enlaces para la descarga de la aplicación que además incorpora el diagrama. Tan solo tenéis que dejar el diagrama en la carpeta donde esté el ejecutable y hacer un load. Luego os aparecerá el mismo diagrama que veis aquí.

El código fuente del algoritmo para la resolución del camino más corto utilizando DijKstra es el siguiente:


procedure TfrmMain.Dijkstra1Click(Sender: TObject);
const
NoWeight = 999999;
MaxVertexs = 12;
type
ArrayOfInteger = array[1..MaxVertexs] of Integer;
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;
DrawingList : ArrayOfInteger;
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;

RestoreDefaults1Click(Sender);

for i := 1 to MaxVertexs do
begin
for j := 1 to MaxVertexs do
begin
AdjacentList[i, j] := NoWeight;
if i = j then
AdjacentList[i, j] := 0
end;
DrawingList[i] := NoWeight;
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 vertexs 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 := '';
DrawingList[firstNode] := LastNode;
j := firstNode;
while (LastNode <> firstNode) do
begin
j := j + 1;
LastNode := predecessor[LastNode];
DrawingList[j] := LastNode;
end;

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


En definitiva, creo que la aplicación va por buen camino y estoy contento porque por fin tengo una aplicación visual para poder tratar los diferentes datos que tengo en mente. Ya os iré contando!.


Comments

Popular Posts