将Numpy数组转换为单调图（networkx）

Question

我有一个1和0的简单数组，我想使用NetworkX在以下条件下将该数组转换为图形：

• 单调的
• 定向的
• 加权图（通过/不通过区域）
• 从左下角开始，向右工作

有一个内置函数叫做from_numpy_matrix

见this

我们的目标是用这张图展示我可以从矩阵的左下角（比如光栅数据集）到右上角，而不需要向后或向下移动。在

示例数组：

array = [[0,0,1,0,0],
         [1,0,0,1,0],
         [1,0,1,1,0],
         [0,0,1,1,0]]
myarray = np.array(array)

0 means go area, 1 means blocked.

Answer 1

那很有趣。在

from_numpy_matrix没有帮助，因为没有从迷宫到邻接矩阵的简单转换。相反，迭代允许的位置（即“非墙”）并检查是否在允许的方向（上、右、对角线右上）上存在允许的位置，这要容易得多。在

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

def maze_to_graph(is_wall, allowed_steps):
    """
    Arguments:
         
    is_wall         2D boolean array marking the position of walls in the maze
    allowed_steps   list of allowed steps; e.g. [(0, 1), (1, 1)] signifies that
                     from coming from tile (i, j) only tiles (i, j+1) and (i+1, j+1)
                     are reachable (iff there is no wall)

    Returns:
        
    g               networkx.DiGraph() instance
    pos2idx         dict mapping (i, j) position to node idx (for testing if path exists)
    idx2pos         dict mapping node idx to (i, j) position (for plotting)
    """

    # map array indices to node indices and vice versa
    node_idx = range(np.sum(~is_wall))
    node_pos = zip(*np.where(~is_wall))
    pos2idx = dict(zip(node_pos, node_idx))

    # create graph
    g = nx.DiGraph()
    for (i, j) in node_pos:
        for (delta_i, delta_j) in allowed_steps: # try to step in all allowed directions
            if (i+delta_i, j+delta_j) in pos2idx: # i.e. target node also exists
                g.add_edge(pos2idx[(i,j)], pos2idx[(i+delta_i, j+delta_j)])

    idx2pos = dict(zip(node_idx, node_pos))

    return g, idx2pos, pos2idx

def test():
    arr = np.array([[0,0,1,0,0],
                    [1,0,0,1,0],
                    [1,0,1,1,0],
                    [0,0,1,1,0]]).astype(np.bool)

    steps = [(0, 1),  # right
             (-1, 0), # up
             (-1, 1)] # diagonal up-right

    g, idx2pos, pos2idx = maze_to_graph(arr, steps)

    nx.draw(g, pos=idx2pos, node_size=1200, node_color='w', labels=idx2pos)

    start = (3, 0)
    stop = (0, 4)
    print "Has path: ", nx.has_path(g, pos2idx[start], pos2idx[stop])

    return