Supongamos que tengo un DiGraph, generado por el siguiente código:

G = nx.DiGraph()

G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=1)
G.add_edges_from([('D','A'),('D','E'),('B','D'),('D','E')], weight=2)
G.add_edges_from([('B','C'),('E','F')], weight=3)
G.add_edges_from([('C','F')], weight=4)


edge_labels=dict([((u,v,),d['weight'])
                 for u,v,d in G.edges(data=True)])

pos=nx.spring_layout(G)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)
pylab.show()

digraph

Con un valor inicial de n y el nodo inicial A, suponiendo que todos los nodos tienen un borde interno y otro externo, quiero recorrer todos los caminos de la red y dividir constantemente el n por el valor del borde direccional, y luego encuentra la ruta que maximiza n de tal manera que termino en el nodo A nuevamente.

Por ejemplo, si n = 100, esta es una ruta de ejemplo para un gráfico diferente, donde recorro algunas rutas y obtengo un valor final:

N / 2 = 50, 50/5 = 10, 10/2 = 5, 5 / 0.01 = 500

Mi caso de uso en particular tiene una red mucho más grande, donde una solución iterativa no es viable. ¿Existe un algoritmo que se aproxime a una solución exacta, minimizando al mismo tiempo el tiempo de cálculo?

1
Évariste Galois 23 ene. 2021 a las 03:58

1 respuesta

La mejor respuesta

Respuesta inicial: basada en nx.simple_cycles

Hay muchas formas de lograr lo que estás buscando, pero aquí tienes una sugerencia:

Primero, permítanme reemplazar el gráfico original por uno que tenga más ciclos y otro diseño.

G = nx.DiGraph()

G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=50)
G.add_edges_from([('D','B')], weight=1)
G.add_edges_from([('B','C'),('F','E'),('E','A')], weight=2)
G.add_edges_from([('C','F'),('B','G'),('A','G')], weight=3)

edge_labels=dict([((u,v,),d['weight'])
                 for u,v,d in G.edges(data=True)])

# improve layout and draw node labels

pos=nx.drawing.layout.circular_layout(G,scale=10)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G,pos,font_color='white')
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)

enter image description here

Ahora encontramos todos los ciclos simples en G que comienzan y terminan en un nodo de interés dado y calculamos n para cada ciclo.

# node of interest
inode  = 'A'


acycs  = [ cyc for cyc in nx.simple_cycles(G) if inode in cyc ]

# for ease of computation we append the first node to the end of each cycle
acycs = [cyc+[cyc[0]] for cyc in acycs]

mcyc = []
maxn = 0

# for each cycle involving node of interest
for cyc in acycs:
    n = 100
    
    # group the nodes in the cycle by pairs
    for u, v in zip(cyc[:-1], cyc[1:]):
        
        # retrieve the respective edge weigth for the current pair
        print(u,v, end=',\t')
        div = G.get_edge_data(u,v)['weight']
        
        # calculate and update n
        r   = n/div
        print(f"{n}\t/\t{div}\t=\t{r}")
        n=r
        
    print('----------------------------------------------------------------------------')

    if n>maxn:
        maxn=n
        mcyc=cyc

Esto nos da todos los bucles que comienzan en inode='A':

[out]:

E A,    100 /   2   =   50.0
A G,    50.0    /   3   =   16.666666666666668
G D,    16.666666666666668  /   50  =   0.33333333333333337
D B,    0.33333333333333337 /   1   =   0.33333333333333337
B C,    0.33333333333333337 /   2   =   0.16666666666666669
C F,    0.16666666666666669 /   3   =   0.05555555555555556
F E,    0.05555555555555556 /   2   =   0.02777777777777778
----------------------------------------------------------------------------
E A,    100 /   2   =   50.0
A B,    50.0    /   50  =   1.0
B C,    1.0 /   2   =   0.5
C F,    0.5 /   3   =   0.16666666666666666
F E,    0.16666666666666666 /   2   =   0.08333333333333333
----------------------------------------------------------------------------
B A,    100 /   50  =   2.0
A G,    2.0 /   3   =   0.6666666666666666
G D,    0.6666666666666666  /   50  =   0.013333333333333332
D B,    0.013333333333333332    /   1   =   0.013333333333333332
----------------------------------------------------------------------------
B A,    100 /   50  =   2.0
A B,    2.0 /   50  =   0.04
----------------------------------------------------------------------------

Y también el ciclo que maximiza n:

print(f"The loop {mcyc} in G maximizes n with {maxn}")
[out]:
The loop ['E', 'A', 'B', 'C', 'F', 'E'] in G maximizes n with 0.08333333333333333

He subido este cuaderno aquí en caso de que prefiera clonarlo y probar este enfoque localmente.

Alternativa no iterativa: basada en nx.dijkstra_path

Según su comentario, parece que lo que está buscando no es to traverse every path in the network, pero si es posible, recorra solo la ruta de n-maximización y calcule nmax.

Esta es solo una variante del algoritmo Dijkstra Shortest Path con una función de ponderación de actualización.

Sin embargo, nx.Dijkstra_path tiene problemas para encontrar ciclos. nx.Dijkstra_path('A','A') rinde A incluso si w(A,A)=math.inf

Pero uno puede usar un truco:

  1. eliminar el nodo A e introducir Ai y Ao
  2. reemplace A en todos sus bordes internos con Ai
  3. reemplace A en todos sus bordes con Ao
  4. enlace Ai y Ao con un peso de borde igual a math.inf.
  5. calcular la ruta más corta de Ao a Ai

Así es como se vería el gráfico que proporcioné en mi respuesta inicial:

import math
Gp = nx.DiGraph()

Gp.add_edges_from([('Ao', 'B'),('B', 'Ai'), ('C','D'),('G','D')], weight=50)
Gp.add_edges_from([('D','B')], weight=1)
Gp.add_edges_from([('B','C'),('F','E'),('E','Ai')], weight=2)
Gp.add_edges_from([('C','F'),('B','G'),('Ao','G')], weight=3)

# this edge is strictly speaking not needed.
Gp.add_edges_from([('Ai','Ao'),('Ao','Ai')], weight=math.inf)

edge_labels=dict([((u,v,),d['weight'])
                 for u,v,d in Gp.edges(data=True)])

pos=nx.drawing.layout.circular_layout(Gp,scale=10)
pos['Ai'], pos['B'] = pos['B'], pos['Ai']
nx.draw_networkx_edge_labels(Gp,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(Gp,pos,font_color='white')
nx.draw(Gp,pos, node_size=1500,edge_cmap=plt.cm.Reds)

enter image description here

Usando nx.dijkstra_path tenemos:

nmpath = nx.dijkstra_path(Gp,'Ao','Ai')
nmpath

[fuera]: ['Ao', 'B', 'C', 'F', 'E', 'Ai']

Podemos ver los pesos de ese camino de la siguiente manera:

lennmpath=len(nmpath)
datnmpath=[Gp.get_edge_data(u, nmpath[i+1])['weight'] for u,i in zip(nmpath[:-1], range(lnmpath))]

[fuera]: [50, 2, 3, 2, 2]

Y podemos calcular nmax trivialmente:

maxn=100; 
for w in datnmpath: maxn/=w
print(maxn)

[out] 0.08333333333333333

Actualicé el cuaderno para que pueda clonarlo y probar este enfoque localmente.

1
jdsalaro 24 ene. 2021 a las 19:11