Make graph from mask grid in Python

I've got a 'mask' numpy 2D array with ones and zeros, e.g.

array([[0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0],         [0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0],         [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],         [1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1],         [0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0],         [1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1],         [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0],         [0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0],         [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0],         [1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1],         [0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0],         [1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1],         [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],         [0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0],         [0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0]])  

My task is to convert this matrix into a connected graph with the zeros as nodes connected with their direct neighbors, that is, for example, the graph in this case would contain several graphs (not connected with each other), like:

*         *---*  |  *---*            *  |                |  *                *  etc...  

So basically each zero here is a node and edges are paths to other zeros which are their direct neighbors (on the top, bottom, right or left). Direction of edges does matter! Edges are either vertical or horizontal, as in the input matrix. My ultimate goal is to use the resulting graph / collection of graphs to perform a number of tests:

• connectivity of all nodes
• max and min length of edges (in each orientation)
• etc.

I've found out the excellent networkx library which seems to be able to generate graphs from arrays, but the reference says it can only treat nd-arrays or pandas dataframes as 'adjacency' matrices and not as direct graph representations as in my case.

https://stackoverflow.com/questions/67259669/make-graph-from-mask-grid-in-python April 26, 2021 at 09:05AM