Closed uekerman closed 3 years ago
I will take care of this issue today. First some good news:
for v1 in vertices.keys():
for v2 in vertices.keys():
if are_connected_by_edge(v1, v2):
vertices[v1] = v2
vertices[v2] = v1
Is O(N^2) with N equal to the total number of vertices in the mesh. However,
for edge1 in dolfin.edges(v1):
for edge2 in dolfin.edges(v2):
if edge1.index() == edge2.index(): # Vertices are connected by edge
return True
return False
Only iterates over the edges of v1
times the edges of v2
. Meaning O(M^2) with M << N.
In the end we arrive at a complexity of c*O(N^2), where c is a constant describing the number of edges per vertex ^ 2.
We currently do: https://github.com/precice/fenics-adapter/blob/e16d434345553f8c8cccf8d0804c6af94168e7c1/fenicsprecice/adapter_core.py#L213-L217
and within
are_connected_by_edge
: https://github.com/precice/fenics-adapter/blob/e16d434345553f8c8cccf8d0804c6af94168e7c1/fenicsprecice/adapter_core.py#L180-L184which means O(N^4) :exploding_head: This makes volume coupling quasi infeasible. Should be possible in O(N).