En la entrada anterior de Algoritmo incremental de Ramalingam y Reps, hablamos acerca de un algoritmo incremental propuesto por Ramalingam y Reps en 1996, un poco antiguo pero bastante citado. Esta vez les comparto un algoritmo que ataca otro problema, un poco parecido, que es el de la inserción de un vértice o nodo.

El algoritmo de Sushant S. Khopkar, Rakesh Nagi, Alexander G. Nikolaev y Vaibhav Bhembre calcula el APSP para grafos incrementales. En su artículo titulado en inglés como “Efficient Algorithms for Incremental All Pairs Shortest Paths, Closeness and Betweeness in Social Network Analysis“, publicado en el 2014, nos habla acerca del análisis de redes sociales como un grafo dinámico.

Algoritmos de grafos dinámicos

Los algoritmos de grafos dinámicos superan la dificultad al evitar recálculos. Se han definido como algoritmos “que mantienen algunas propiedades de un grafo cambiante de manera más eficiente que el recálculo desde cero después del cambio”.

Un algoritmo de grafo dinámico modifica una solución de datos conocidos para reflejar los cambios en el conjunto de datos del estado anterior. No aplica el algoritmo que se utilizó para el conjunto de datos original. Pero una vez que el algoritmo, del grafo dinámico, se aplica al conjunto de datos original, se repite el mismo algoritmo para cada estado de datos formado por el cambio en él.

Los algoritmos de grafos dinámicos también se clasifican como Algoritmos Parcialmente Dinámicos y Algoritmos Completamente Dinámicos.

Algoritmos parcialmente dinámicos: Es aquel en el que solo está involucrado un tipo de actualización. Esta actualización podría ser una inserción o eliminación de vértices y/o arcos. Los algoritmos parcialmente dinámicos que incluyen actualizaciones de inserción se denominan algoritmos incrementales; mientras que los que implican la eliminación se llaman algoritmos decrementales.
Algoritmos totalmente dinámicos: Estos implican la inserción, así como la eliminación de vértices y/o arcos. Esto se compone de dos sub-algoritmos independientes. Uno es para la adición de vértices y/o arcos y el otro es para la eliminación de vértices y/o arcos.

Algoritmo APSP incremental para la inserción de vértices o nodos

Este algoritmo actualiza rápidamente todos los pares de rutas más cortas (APSP), luego de agregar un nuevo vértice. La adición de vértice implica que también se agregan los arcos que lo conectan a los vértices del grafo existentes. Este es un algoritmo de grafo parcialmente dinámico y funciona en grafos generales dirigidos y no dirigidos que tienen ponderaciones de borde en valores reales. El algoritmo se basa en el concepto de que, si alguna ruta más corta pasa a través del vértice recién agregado en el grafo, primero debe pasar por al menos uno de sus vecinos, que ya estaban presentes en el grafo original (ver Figura 1 ). El algoritmo aprovecha su rendimiento mediante la ayuda del conocimiento de todos los pares de rutas más cortas en el grafo original para calcular las nuevas rutas más cortas. Las rutas más cortas recién encontradas se comparan con las antiguas para obtener las rutas más cortas actualizadas.

Los siguientes pasos para explicar el algoritmo, son tal cual como los enseña en el artículo

Agregue un nuevo vértice ‘ $z$ ‘ en el grafo original de $n$ vértices. Identificar a sus vecinos. Sea $T_{1}$ el conjunto de todos los vecinos entrantes de $z$ . Puede haber a lo sumo $n$ vecinos entrantes. Sea $T_{2}$ el conjunto de todos los vecinos salientes de $z$ . Puede haber a lo sumo $n$ vecinos salientes. Sea $t_{1}$ la cardinalidad del conjunto $T_{1}$ y $t_{2}$ la cardinalidad del conjunto $T_{2}$ .

Figura 1. Grafo dinámico incremental por vértice, imagen tomada del artículo

Dejemos que $k^{in}$ denote un vecino entrante del nodo $z$ recién agregado (por ejemplo, $k_{1}$ o $k_{3}$ en la Figura 1). Sea $d_{ik^{in}}$ la longitud del camino más corto entre los nodos $i$ y $k_{in}$ . Tenga en cuenta que esta longitud de ruta más corta ya está disponible, ya que se ha calculado para la red antigua. Deje que $d^{k^{in}}_{iz}$ denote la longitud de la ruta desde el nodo $i$ al nodo $z$ que pasa a través de $k_{in}$ . Sea $w_{k^{in},z}$ el peso del borde entre los nodos $k^{in}$ y $z$ . Entonces, uno tiene:

$d^{k^{in}}_{iz} = d_{ik^{in}} + w_{k^{in},z \cdot}$

Dado que múltiples nodos como $k_{in}$ pueden existir en una red (por ejemplo, en el ejemplo presentado, uno tiene el caso $k_{in} = k_{1}$ y el caso $k_{in}$ = $k_{3}$ ), este paso se repite para todos los vecinos entrantes del nodo recién agregado, es decir ,

For $i= 1$ to $n$

For $k^{in} = 1$ to $T_{1}$

$d^{k^{in}}_{iz} = d_{ik^{in}} + w_{k^{in},z \cdot}$

En este paso, las rutas más cortas de cada nodo en el gráfico original al nodo ‘ $z$ ‘ recién agregado se ubican a través de uno de sus vecinos. Esto se puede hacer tomando el mínimo sobre todas las distancias $d^{k^{in}}_{iz}$ para cada $i$ . Denotamos por $min_{k^{in} \in T_{1}}\{d^{k^{in}}_{iz}\}$ . Esta es la ruta más corta entre el nodo $i$ y el nodo $z$ que pasa a través de uno de los vecinos entrantes de $z$ .
De manera similar, digamos que $k^{out}$ denota un vecino saliente del nodo $z$ (por ejemplo, en el ejemplo presentado en la Figura 1, $k^{out}$ podría ser $k_2$ o $k_4$ . Sea $d_{k^{out}j}$ la distancia más corta entre el nodo $k^{out}$ y el nodo $j$ . Tenga en cuenta que esta distancia de ruta más corta ya se había calculado en la red original (antigua). Sea $d^{k^{out}}_{zj}$ la longitud de la ruta desde el nodo $z$ al nodo $j$ que pasa a través de $k^{out}$ . Entonces, uno tiene

$d^{k^{out}}_{zj} = w_{z,k^{oout}} + d_{k^{out}j}$

En este paso, el camino más corto desde el nuevo nodo insertado ‘ $z$ ‘ a cada nodo en el grafo original se ubica a través de uno de sus vecinos. Esto se realiza tomando el mínimo de las distancias $d^{k^{out}}_{zj}$ , para cada $j$ . Denotamos por $min_{k^{out} \in T_{2}}\{d^{k^{out}}_{zj}\}$ . Nota que $min_{k^{out} \in T_{2}}\{d^{k^{out}}_{zj}\}$ es el camino más corto entre el nodo $z$ y el nodo $j$ que pasa a través de los vecinos salientes de $z$ .
Las combinaciones de $min_{k^{in} \in T_{1}}\{d^{k^{in}}_{iz}\}$ y $min_{k^{out} \in T_{2}}\{d^{k^{out}}_{zj}\}$ para cada par de nodos $(i, j)$ da lugar a un camino más corto recién formado ‘ $i$ ‘ a ‘ $j$ ‘. Por lo tanto, para cada par de nodos $(i,j)$ , si la suma de las longitudes de las rutas más cortas entre el nodo $i$ y el nodo $z$ y entre el nodo $z$ y el nodo $j$ es más pequeña que la longitud de la ruta más corta original entre $i$ y $j$ $(d_{ij})$ , reemplaza la distancia del camino más corto por la nueva. Este paso se repite para cada par de nodos $(i, j)$ en el grafo original.

Grafo incremental por vértice

Para simular ina inserción de vértice en el grafo, entonces le agregamos a nuestra clase, que hemos venido manejando en este blog, una función para insertar, dado un nuevo vértice y dos listas que representan los vértices del grafo que se conectan al nuevo vértice y los vértices a los cuales parte el nuevo vértice:

def dynamic_incremental_node(self, node, sources, w_sources, targets, w_targets):

    if self.vertex[self.vertex == node].size > 0:
        return -1

    sources = np.array(sources)
    targets = np.array(targets)
    self.source = np.concatenate((self.source, sources, np.full(targets.size, node)))
    self.target = np.concatenate((self.target, np.full(sources.size, node), targets))
    self.weight = np.concatenate((self.weight, w_sources, w_targets))
    self.vertex = np.append(self.vertex, node)

    self.node_incremental['node'] = node
    self.node_incremental['source'] = sources
    self.node_incremental['target'] = targets

    return self

Algoritmo KNNB

def knnb_node_incremental(self, dist):
    dist = np.array(dist)

    add = np.full(self.vertex.size-1, np.inf)
    dist = np.vstack([dist, add])
    dist = np.hstack([dist, np.append(add, np.inf)[:, None]])
    dist[self.vertex.size-1, self.vertex.size-1] = 0

    z = self.node_incremental['node']
    T1 = self.node_incremental['source']
    T2 = self.node_incremental['target']

    min_in_z = {}
    min_out_z = {}

    for k_in in T1:
        dist[self.vertex == k_in, self.vertex == z] = self.get_weight(k_in, z)

    for k_out in T2:
        dist[self.vertex == z, self.vertex == k_out] = self.get_weight(z, k_out)

    for v in self.vertex:
        if v == z:
            continue
        for k_in in T1:
            L_vz = dist[self.vertex == v, self.vertex == k_in][0] + self.get_weight(k_in, z)
            if v not in min_in_z or L_vz < min_in_z[v]:
                min_in_z[v] = L_vz
        for k_out in T2:
            L_zv = dist[self.vertex == k_out, self.vertex == v][0] + self.get_weight(z, k_out)
            if v not in min_out_z or L_zv < min_out_z[v]:
                min_out_z[v] = L_zv
    for i, L_iz in min_in_z.items():
        for j, L_jz in min_out_z.items():
            if i == j:
                continue
            if L_iz + L_jz < dist[self.vertex == i, self.vertex == j][0]:
                dist[self.vertex == i, self.vertex == j] = L_iz + L_jz

    for i, value in min_in_z.items():
        dist[self.vertex == i, self.vertex == z] = value
    for j, value in min_out_z.items():
        dist[self.vertex == z, self.vertex == j] = value

    return dist

El algoritmo tiene lineas adaptadas para el grafo de nuestro ambiente, como las lineas del 4 al 7.

Pruebas

Analicemos una sección de pruebas, como el mismo grafo que se usó para el algoritmod de Ramalingam:

Figura 2. Grafo de prueba. El vértice 6 es el vértice insertado en el grafo

from _graph.GraphPro import GraphPro as g
from time import time
import os

os.system('clear')
print("<--------Test Khopkar------->\n")

weights = [1, 2, 3, 4, 5]

sources = [1, 0, 3, 2, 1, 4, 5, 4, 5]
targets = [0, 2, 0, 1, 3, 1, 1, 3, 4]
weights = [2, 2, 4, 3, 2, 4, 4, 3, 1]
graph = g(sources, targets, weights)

print('.........................')

dist = graph.floyd_warshall()
print(dist)

graph.dynamic_incremental_node(
    node=6, sources=[2], w_sources=[1], targets=[5], w_targets=[1])

dist_new = graph.knnb_node_incremental(dist.tolist())
print(dist_new)

graph.print_r()

El resultado es:

<--------Test Khopkar------->

.........................
[[  0.   5.   2.   7.  inf  inf]
 [  2.   0.   4.   2.  inf  inf]
 [  5.   3.   0.   5.  inf  inf]
 [  4.   9.   6.   0.  inf  inf]
 [  6.   4.   8.   3.   0.  inf]
 [  6.   4.   8.   4.   1.   0.]]

[[  0.   5.   2.   7.   5.   4.   3.]
 [  2.   0.   4.   2.   7.   6.   5.]
 [  5.   3.   0.   5.   3.   2.   1.]
 [  4.   9.   6.   0.   9.   8.   7.]
 [  6.   4.   8.   3.   0.  10.   9.]
 [  6.   4.   8.   4.   1.   0.   9.]
 [  7.   5.   9.   5.   2.   1.   0.]]
Source:  [ 1.  0.  3.  2.  1.  4.  5.  4.  5.  2.  6.]
Target:  [ 0.  2.  0.  1.  3.  1.  1.  3.  4.  6.  5.]
Weight:  [2 2 4 3 2 4 4 3 1 1 1]
Vertex:  [0 1 2 3 4 5 6]

Claramenten la matriz de distancia aumenta en dimensión por el nuevo vértice. Nótese que en la primera matriz existen muchos valores inf, esto debido a que algunos vértices del grafo nunca son alcanzados. Esto cambia al insertar el nuevo vértice, las cuales hace alcanzables estos vértices. La última fila representa la distancia desde el nuevo vértice a los demás nodos. La última columna representa la distancia de todos los nodos al nuevo vértice insertado.

Se realiza una segunda pruea emulando el mismo algoritmo de ejemplo del artículo, es el grafo de la Figura 1:

sources = [10, 11, 5, 5, 6, 4, 8, 4, 9, 9,  2, 12, 3]
targets = [1,   1, 1, 6, 4, 7, 4, 9, 8, 2, 12,  9, 2]
weights = [1,   1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1, 1]
graph2 = g(sources, targets, weights)

print('.........................')

dist2 = graph2.floyd_warshall()
print(dist2)

graph2.dynamic_incremental_node(
    node=13, sources=[1, 3], w_sources=[1, 1], targets=[2, 4], w_targets=[1, 1])

dist2_new = graph2.knnb_node_incremental(dist2.tolist())
print(dist2_new)

graph2.print_r()

El resultado:

[[  0.  inf  inf  inf  inf  inf  inf  inf  inf  inf  inf  inf]
 [ inf   0.  inf   4.  inf  inf   5.   3.   2.  inf  inf   1.]
 [ inf   1.   0.   5.  inf  inf   6.   4.   3.  inf  inf   2.]
 [ inf   2.  inf   0.  inf  inf   1.   2.   1.  inf  inf   3.]
 [  1.   4.  inf   2.   0.   1.   3.   4.   3.  inf  inf   5.]
 [ inf   3.  inf   1.  inf   0.   2.   3.   2.  inf  inf   4.]
 [ inf  inf  inf  inf  inf  inf   0.  inf  inf  inf  inf  inf]
 [ inf   3.  inf   1.  inf  inf   2.   0.   2.  inf  inf   4.]
 [ inf   1.  inf   2.  inf  inf   3.   1.   0.  inf  inf   2.]
 [  1.  inf  inf  inf  inf  inf  inf  inf  inf   0.  inf  inf]
 [  1.  inf  inf  inf  inf  inf  inf  inf  inf  inf   0.  inf]
 [ inf   2.  inf   3.  inf  inf   4.   2.   1.  inf  inf   0.]]

[[  0.   2.  inf   2.  inf  inf   3.   4.   3.  inf  inf   3.   1.]
 [ inf   0.  inf   4.  inf  inf   5.   3.   2.  inf  inf   1.  inf]
 [ inf   1.   0.   2.  inf  inf   3.   4.   3.  inf  inf   2.   1.]
 [ inf   2.  inf   0.  inf  inf   1.   2.   1.  inf  inf   3.  inf]
 [  1.   3.  inf   2.   0.   1.   3.   4.   3.  inf  inf   4.   2.]
 [ inf   3.  inf   1.  inf   0.   2.   3.   2.  inf  inf   4.  inf]
 [ inf  inf  inf  inf  inf  inf   0.  inf  inf  inf  inf  inf  inf]
 [ inf   3.  inf   1.  inf  inf   2.   0.   2.  inf  inf   4.  inf]
 [ inf   1.  inf   2.  inf  inf   3.   1.   0.  inf  inf   2.  inf]
 [  1.   3.  inf   3.  inf  inf   4.   5.   4.   0.  inf   4.   2.]
 [  1.   3.  inf   3.  inf  inf   4.   5.   4.  inf   0.   4.   2.]
 [ inf   2.  inf   3.  inf  inf   4.   2.   1.  inf  inf   0.  inf]
 [ inf   1.  inf   1.  inf  inf   2.   3.   2.  inf  inf   2.   0.]]
Source:  [ 10.  11.   5.   5.   6.   4.   8.   4.   9.   9.   2.  12.   3.   1.   3.  13.  13.]
Target:  [  1.   1.   1.   6.   4.   7.   4.   9.   8.   2.  12.   9.   2.  13.  13.   2.   4.]
Weight:  [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
Vertex:  [ 1  2  3  4  5  6  7  8  9 10 11 12 13]

Anexos

El código se encuentra en mi repositorio público https://github.com/arturoverbel/grhttps://github.com/arturoverbel/graph_pythonaph_python, donde:

El algoritmo de KNND se encuentra en: https://github.com/arturoverbel/graph_python/blob/master/_graph/GraphKNNB.py

Mi Camino Master

Mi experiencia y mis pensamientos acerca de mis estudios de Maestría en Ciencias de la Información y las Comunicaciones

Algoritmo incremental de Khopkar – Python 3.5

Algoritmos de grafos dinámicos

Algoritmo APSP incremental para la inserción de vértices o nodos

Grafo incremental por vértice

Algoritmo KNNB

Pruebas

Anexos

Arturo Verbel De Leon

Comentarios Cancel reply

Lo más visto

Sígueme

Lo más visto

Últimas entradas

Sígueme