Create edges from cells

Question

I have a (large) number of nodes and (triangular) cells, e.g.,

cells_nodes = [
 [0, 3, 1],
 [0, 2, 3]
 ]

This example represents the small mesh

enter image description here

(Please call me Picasso from here on out.)

Now, I would like to create the edges for these meshes (in red above), specifically edge–node and edge–cell relations. For the above example, the result would be

[[0], [1], [1], [0, 1], [0]] # edge -> cells
[[1, 3], [2, 3], [0, 2], [0, 3], [0, 1]] # edge -> nodes
[[0, 3, 4], [1, 2, 3]] # cell -> edges

The problem I wasn't able to solve to my satisfaction is to identify the individual edges. Note that [1, 2] is the same edge as [2, 1]. Using frozensets works, but is perhaps overkill. This code

import numpy
def create_edges(cells_nodes):
 from collections import defaultdict
 d = defaultdict(list)
 # Loop over lists all pairs of nodes, i.e., all possible edges.
 cells_edges = []
 for local_edges in [[0, 1], [1, 2], [2, 0]]:
 # Put those into a list of frozensets so [21, 54] == [54, 21].
 cells_edges.append(
 map(frozenset, cells_nodes[:, local_edges])
 )
 # Store the edges in a dictionary, store the corresponding cell too.
 for k, f in enumerate(cells_edges[-1]):
 d[f].append(k)
 edges_nodes = numpy.array(map(list, d))
 edges_cells = list(d.values())
 edge_indices = dict(zip(d.keys(), range(len(d))))
 cells_edges = numpy.vstack(
 [[edge_indices[edge] for edge in c] for c in cells_edges]
 ).T
 return edges_nodes, edges_cells, cells_edges
if __name__ == '__main__':
 import meshzoo
 vertices, cells = meshzoo.rectangle.create_mesh(
 0.0, 1.0,
 0.0, 1.0,
 2, 2
 )
 edges_nodes, edges_cells, cells_edges = create_edges(cells)
 print(vertices)
 print
 print(cells)
 print
 print(edges_nodes)
 print
 print(edges_cells)
 print
 print(cells_edges)

works, but it too slow. The applications of map, and likely the explicit loops are killing the performance.

$ python -m cProfile -o program.prog e.py
$ snakeviz program.prog

enter image description here

Any idea of how improve this?

• Peilonrayz: Hello, I'm unsure on what the edge -> cells are, I can guess the other two, but could you explain it to me?

Answer 1

Honestly? It looks pretty straightforward. Everything in your code screams you've done this before. Good!

You're adhering to the standards of Python (the PEPs). The imports are at the exactly right places. The code is readable, easy to understand and does things the easiest way possible. In other words: it's Pythonic.

You could consider wrapping your print statements in main into a template so you'll only need one print call. However, since you only print once, I'm not sure how useful this would be in the end.

While your code is easy to understand, you might want to make the naming even better. You got 5 variables with the term edges in it, not even counting main where you use some of the exact names again. You're also overwriting cells_edges after the for after using it as a temporary variable. That's probably not the most maintainable way.

Single-character variable names should be avoided, even if they appear to be obvious.

d[f].append(k)

Yea, not a good idea. c, d, f and k should be renamed.