Después de unos días muy ajetreados y con mucho trabajo (y que no falte) he podido medio acabar la primera aplicación profesional sobre mi framework. Ésta se trata sobre el cálculo de rutas. He utilizado diversos tipos de algoritmos para su recorrido y búsqueda de diferentes caminos para obtener la ruta de un origen a un destino pasando por una serie de nodos. Luego vincularé la búsqueda de éstas rutas con mi anterior aplicación Thundax Genies Scanner y así poder crear mapas mentales de aplicaciones Scada para la búsqueda de caminos automáticos. En que consiste ésta idea?
Como podéis ver en la siguiente imagen:
Disponemos de un origen marcado en verde y un destino marcado en fucsia. Con mi framework he generado el diagrama y aplicado diversas propiedades a las diferentes cajas y conectores. El problema que se presenta, es el de calcular las diferentes rutas que hay de un punto a otro y guardarlas en algún sitio para poder utilizar éstos datos y evitar sobretodo el cálculo manualmente. Poco a poco, os iré explicando la utilizad de ésto y el propósito de su cálculo.
Por lo tanto, si nos fijamos en la imagen existen 2 rutas para ir del origen (1) al destino (19):
Así, calcularíamos:
Si observamos mi aplicación, veremos como se calculan las rutas automáticamente:
Ahora un ejemplo más real:
Como podéis comprobar, son los mismos nodos, pero ahora tenemos 7 rutas disponibles!.
El cálculo de sus rutas es el siguiente:
Aún estoy acabando de perfilar el algoritmo y calculando sus diferentes costes para una mejora en su rendimiento. Dentro de poco tendré disponible la versión para búsqueda de rutas con múltiples orígenes y múltiples destinos. Y poder realizar la búsqueda de rutas de diagramas como el siguiente:
Si os fijáis, incluso he creado un tipo de enlace nuevo con la imagen de una cadena. Éste enlace consiste en un enlace de bloqueo donde los nodos están fuertemente vinculados y también se tienen que tener en cuenta a la hora de escribir la ruta de transporte. Ésto significa que si queremos pasar por un nodo de éstos, el otro debe aparecer bloqueado (en términos de fluidos seria cerrar uno de los caminos).
Primero calculo los orígenes y destinos en función del color de la caja:
El siguiente paso es marcar los diferentes nodos con su peso marcado por la cantidad de nodos conectados a un nodo.
Esto nos permite crear un diagrama con la siguiente información:
Cómo podéis ver el algoritmo es bastante simple pero se puede mejorar bastante. El coste de calculo es O(n2) para visitar todos los nodos. Aquí os dejo la última versión de la aplicación ThundaxBoxManager v2.3.0 build 57 con los diagramas de ejemplo. Para si resolución hay que ir al menú Citect y allí ejecutar la opción Backtracking2.
Como podéis ver en la siguiente imagen:
Disponemos de un origen marcado en verde y un destino marcado en fucsia. Con mi framework he generado el diagrama y aplicado diversas propiedades a las diferentes cajas y conectores. El problema que se presenta, es el de calcular las diferentes rutas que hay de un punto a otro y guardarlas en algún sitio para poder utilizar éstos datos y evitar sobretodo el cálculo manualmente. Poco a poco, os iré explicando la utilizad de ésto y el propósito de su cálculo.Por lo tanto, si nos fijamos en la imagen existen 2 rutas para ir del origen (1) al destino (19):
Así, calcularíamos:RUTA1: 1-4-8-11-19 RUTA2: 1-5-9-11-19
- ¿Dónde está la complicación aquí?
Si observamos mi aplicación, veremos como se calculan las rutas automáticamente:
Ahora un ejemplo más real:
Como podéis comprobar, son los mismos nodos, pero ahora tenemos 7 rutas disponibles!.
El cálculo de sus rutas es el siguiente:
Aún estoy acabando de perfilar el algoritmo y calculando sus diferentes costes para una mejora en su rendimiento. Dentro de poco tendré disponible la versión para búsqueda de rutas con múltiples orígenes y múltiples destinos. Y poder realizar la búsqueda de rutas de diagramas como el siguiente:
Si os fijáis, incluso he creado un tipo de enlace nuevo con la imagen de una cadena. Éste enlace consiste en un enlace de bloqueo donde los nodos están fuertemente vinculados y también se tienen que tener en cuenta a la hora de escribir la ruta de transporte. Ésto significa que si queremos pasar por un nodo de éstos, el otro debe aparecer bloqueado (en términos de fluidos seria cerrar uno de los caminos).- ¿Cómo funciona el algoritmo?
Primero calculo los orígenes y destinos en función del color de la caja:
Luego, nos centramos en calcular la lista de adyacentes en función del tipo de conexión. Además existe una lista de bloqueos en función del tipo de conector utilizado:
for i := 0 to boxlist.count - 1 do
begin
if boxlist.items[i].properties.fillColor = clLime then
SetArrayValue(OrigenList, StrToInt(boxlist.items[i].properties.getText));
if boxlist.items[i].properties.fillColor = clFuchsia then
SetArrayValue(DestinoList, StrToInt(boxlist.items[i].properties.getText));
end;
for i := 0 to connectorList.count - 1 do
begin
conn := connectorList.items[i];
pos1 := StrToInt(conn.SourceBox.properties.getText);
pos2 := StrToInt(conn.TargetBox.properties.getText);
if not conn.Line.ClassNameIs('TAbstractDottedDoubleLinkedArrowLine') and
not conn.Line.ClassNameIs('TAbstractSimpleDoubleLinkedArrowLine') then
SetAdjacentValue(AdjacentList, pos1, pos2)
else
begin
SetAdjacentValue(InterlockList, pos1, pos2);
SetAdjacentValue(InterlockList, pos2, pos1);
end;
end;
El siguiente paso es marcar los diferentes nodos con su peso marcado por la cantidad de nodos conectados a un nodo.
for i := 0 to length(AdjacentList)-1 do
begin
AdjacentList[i].weight := getWeight(AdjacentList, AdjacentList[i].source);
if AdjacentList[i].weight = 1 then
AdjacentList[i].unique := true;
end;
Esto nos permite crear un diagrama con la siguiente información:
function TfrmMain.ExamineNodes(firstNode: integer; lastNode: integer; AdjacentList: TAdjacentArray): string;
var
nodeVisited: integer;
res: TArrayInteger;
i: integer;
father: integer;
begin
nodeVisited := firstNode;
father := nodeVisited;
while (nodeVisited <> lastNode) do
begin
res := GetConnections(AdjacentList, nodeVisited);
if length(res) = 0 then exit;
for i := 0 to length(res) - 1 do
begin
nodeVisited := res[i];
if isVisited(AdjacentList, father, nodeVisited) then
begin
visit(AdjacentList, father, nodeVisited);
setRoute(nodeVisited, father);
ExamineNodes(nodeVisited, lastNode, AdjacentList);
end;
end;
end;
end;
Cómo podéis ver el algoritmo es bastante simple pero se puede mejorar bastante. El coste de calculo es O(n2) para visitar todos los nodos. Aquí os dejo la última versión de la aplicación ThundaxBoxManager v2.3.0 build 57 con los diagramas de ejemplo. Para si resolución hay que ir al menú Citect y allí ejecutar la opción Backtracking2.
- ThundaxBoxManager v2.3.0 build 57.rar (with Data).
