Parallel graph input

[schnellerhase]

Support the construction from multiple, process local, graphs (given in global node indices), e.g.

Proc 0:

0
| \
1  2

Proc 1:

2
| \
3  4

Should result in the parallel mesh

0
| \
1  2
   | \
   3  4

[jorgensd]

There would have to be some very specific requirements on the node distribution for such graphs.
I am tempted to say we could support the case above, i.e.

from mpi4py import MPI
import networkx as nx
import numpy as np

comm = MPI.COMM_WORLD

G = nx.DiGraph()
if comm.rank == 0:
    G.add_node(0, pos=np.zeros(3))
    G.add_node(1, pos=np.array([1, 0, 0]))
    G.add_node(2, pos=np.array([1, 1, 0]))
    G.add_edge(0, 1)
    G.add_edge(0, 2)
elif comm.rank == 1:
    G.add_node(2, pos=np.array([1, 1, 0]))
    G.add_node(3, pos=np.array([0, 1, 0]))
    G.add_node(4, pos=np.array([2, 2, 0]))
    G.add_edge(2, 3)
    G.add_edge(2, 4)

print(f"Rank {comm.rank} has nodes: {list(G.nodes())}, edges: {G.edges()}")

However, you already see the issue that both ranks has node 2, and then one should sync pos.
Secondly, for construction of the mesh, we need the nodes to be order consecutively on the process, i.e. rank 0 has nodes
[0, N_0), rank 1, [N_0, N_1), rank2, [N_1, N_2), etc.
which means that a global synchronization has to take place to ensure that we get them in the right order. This potentially has a huge cost, as the above example could be modified such that:
Proc N:

0
| \
1  2

Proc 0:

55
|    \
103  2

Proc 1:

103 --- 1

where some other processes have the remaining indices.
I am tempted to say we shouldn't support this, as the synching will be quite complex, and potentially needs to add renumbering for non-consecutive node ordering etc.