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í.

• ThundaxBoxManager v2.0.0 build 70.zip (With Data).

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!.