python-3.xgraphnetworkxdelaunayscipy-spatial

Creating networkx graph using Delaunay Triangulation


I have a Delaunay Triangulation (DT) (scipy) as follows:

# Take first 50 rows with 3 attributes to create a DT-
d = data.loc[:50, ['aid', 'x', 'y']].values
dt = Delaunay(points = d) 

# List of triangles in the DT-
dt.simplices                                       
'''
array([[1, 3, 4, 0],
       [1, 2, 3, 0],
       [1, 2, 3, 4]], dtype=int32)
'''

Now, I want to create a graph using 'networkx' package and add the nodes and edges found using DT from above.

# Create an empty graph with no nodes and no edges.
G = nx.Graph()

The code I have come up with to add the unique nodes from DT simplices into 'G' is-

# Python3 list to contain nodes
nodes = []

for simplex in data_time_delaunay[1].simplices.tolist():
    for nde in simplex:
        if nde in nodes:
            continue
        else:
            nodes.append(nde)

nodes
# [1, 3, 4, 0, 2]

# Add nodes to graph-
G.add_nodes_from(nodes)

How do I add edges to 'G' using 'dt.simplices'? For example, the first triangle is [1, 3, 4, 0] and is between the nodes/vertices 1, 3, 4 and 0. How do I figure out which nodes are attached to each other and then add them as edges to 'G'?

Also, is there a better way to add nodes to 'G'?

I am using Python 3.8.

Thanks!


Solution

  • You could add the rows in the array as paths. A path just constitutes a sequence of edges, so the path 1,2,3 translates to the edge list (1,2),(2,3). So iterate over the rows and use nx.add_path:

    simplices = np.array([[1, 3, 4, 0],
                          [1, 2, 3, 0],
                          [1, 2, 3, 4]])
    
    G = nx.Graph()
    for path in simplices:
        nx.add_path(G, path)
    
    nx.draw(G, with_labels=True, node_size=500, node_color='lightgreen')
    

    enter image description here