Convert Numpy Array to Monotone Graph (networkx)

Question

I have a simple array of 1s and 0s, and I want to convert this array to a graph using NetworkX with the following conditions:

• monotone
• Directional
• Weighted graph (go/no go areas)
• Starts in the lower left hand corner and works right

There is a built in function called from_numpy_matrix

See this

The goal is to take this graph and show that I can get from the lower left hand corner of the matrix (think raster dataset) to the upper right hand corner without moving backwards or down.

Example array:

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

That was fun.

from_numpy_matrix doesn't help as there is no simple transformation from your maze to an adjacency matrix. Instead it is much easier to iterate over allowed positions (i.e. "not wall") and check if there is an allowed position in the allowed directions (up, right, diagonal up-right).

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