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.