给定一个坐标列表，向这些坐标添加值，直到最短路径列表发生变化 [英] Given a list of coordinates add values to those coordinates until shortest path list changes

问题描述

所以我有一个问题，我希望你能指出正确的方向，完整的上下文问题，我有一个 3D numpy 数组，我用来使用 Networkx 创建图形，并通过这些图形找到最短路径.我需要的是给定一组坐标添加1"在这些坐标中，直到最短路径列表发生变化(这只是一个例子，坐标列表可以有更多的坐标)，我的代码如下:

So I got a question and I was hoping you can point me to the right direction, full context problem, I have a 3D numpy array that I use to create graphs using Networkx and with these graphs I find the shortest path. What I need is that given a set of coordinates add "1" in these coordinates until the list of the shortest path changes (This is just an example, the list of coordinates can have more coordinates), my code is the following:

import numpy as np
import networkx as nx

arr = np.array([[[  0., 378.,  50., 174., 125.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 154.,   0.,  20.,   0.],
                 [  0., 111.,  15.,   0.,  22.],
                 [  0.,  16.,   0.,  12.,   0.]],

                [[  0., 488.,  64.,  98., 117.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 151.,   0.,  24.,   0.],
                 [  0.,  35.,  13.,   0.,  24.],
                 [  0.,  71.,   0.,  10.,   0.]],

                [[  0., 374., 110., 187., 189.],
                 [  0.,   0.,   0.,   0.,   0.],
                 [  0., 195.,   0.,  12.,   0.],
                 [  0.,  42.,  14.,   0.,  21.],
                 [  0.,  16.,   0.,  19.,   0.]]])

graphs = []
path = []

for i in arr:
    graphs.append(nx.from_numpy_array(i, create_using = nx.DiGraph)) #Create graphs from numpy array

for graph in graphs:
    path.append(nx.shortest_path(graph, 0, 1, weight = 'weight'))   #Find the shortest path

print(path) 

#path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]] #Shortest path for each array

coordinates = [[2, 3], [3, 4]] #List of coordinates in the array that I want to add 1

我想遍历我的坐标列表并添加 1 直到我的路径列表更改，例如

I want to iterate through my list of coordinates and be adding 1 until my path list changes, for example

#My first coordinate is [2, 3] so I add 1 to these coordinates and calculate the shortest path again 
#to see if the path changes

arr[:, 2, 3] = arr[:, 2, 3] + 1     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 2, 3] = arr[:, 2, 3] + 2     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
...
arr[:, 2, 3] = arr[:, 2, 3] + 9     #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 2, 3] = arr[:, 2, 3] + 10    #Path = [[0, 2, 3, 4, 1], [0, 3, 1], [0, 2, 3, 4, 1]] #Here the path changes so I keep the 9

在我完成第一个坐标后，然后我去第二个.

After I finish with the first coordinate, then I go to the second one.

#The second coordinate is [3, 4] so...

arr[:, 3, 4] = arr[:, 3, 4] + 1  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
...
arr[:, 3, 4] = arr[:, 3, 4] + 4  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 4, 1]]
arr[:, 3, 4] = arr[:, 3, 4] + 5  #Path = [[0, 2, 3, 4, 1], [0, 2, 3, 1], [0, 2, 3, 1]] #Here the path changes so I keep the 4

我正在考虑使用类似 while (path == newpath) 的 while 循环，然后继续添加一个，但我不确定如何遍历坐标列表以及如何停止找到改变路径的值后，任何帮助将不胜感激，谢谢！

I was thinking about using a while loop something like while (path == newpath) then continue adding one, but I'm not sure how to iterate through the list of coordinates and how to stop after it finds the value that changes the path, so any help will be appreciated, thank you!

推荐答案

您对循环结构的假设是正确的.只需确保正确复制数组即可.代码如下:

You were correct in assuming the structure of the loop. Just make sure that you copy the arrays properly. Here is the code:

from copy import deepcopy

for x,y in coordinates:
    # Make deepcopies of path and arr
    # For the first iteration, set newpath = path
    new_path = deepcopy(path)
    temp_arr = deepcopy(arr)

    # Set counter for each coordinate to zero
    cnt = 0

    # Iterate till a change in path is observed
    while path == new_path:
        # Add 1 to x,y
        temp_arr[:, x, y] = temp_arr[:, x, y] + 1

        # Increment the counter
        cnt += 1

        # Reconstruct the graph and shortest path
        temp_graph = []
        new_path = []
        for i in temp_arr:
            temp_graph.append(nx.from_numpy_array(i, create_using = nx.DiGraph))

        for graph in temp_graph:
            new_path.append(nx.shortest_path(graph, 0, 1, weight = 'weight'))

    # If we are out of the loop, this means that
    # the shortest path has changed. Print the details.
    print("For coordinates X={} and Y={} the change is at {}".format(x, y, cnt))

对于工作版本，您可以查看此笔记本.

For a working version, you can check out this notebook.

另外，我不确定您是否总是想找出 source=0 和 target=1 之间的最短路径，但是您可以将这些值更改为您的需要.您可以查看文档 此处.

Also, I am not sure if you always want to find out the shortest path between source=0 and target=1, but you can change the values to your need. You can check out the documentation here.

参考资料:

• Deepcopy Python 列表

这篇关于给定一个坐标列表，向这些坐标添加值，直到最短路径列表发生变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！