I am not familiar with METIS at all, so is there a way to provide the underlying graph in a more intuitive format? An actual image would be nice. Or again, the dot-output for graphviz?
An image of the graph distributed among two processes. http://lamberti.web.cs.unibo.it/bfs.png If i get your point, process 0 starts a bfs with the n0 as root and process 1 starts with n4 as root cause n0 and n4 are the local node 0 of each process. And the ouput is the minimum distance value of each node discovered via n0 and n4 either? To what end? This is the ouput with three processes: graph g { subgraph cluster_0 { label="p0"; n0[label=0]; n1[label=0]; } n0 -- n2; n1 -- n1; n1 -- n3; n1 -- n4; subgraph cluster_1 { label="p1"; n2[label=0]; n3[label=1]; } n2 -- n1; n2 -- n3; n3 -- n4; subgraph cluster_2 { label="p2"; n4[label=0]; } n4 -- n0; n4 -- n1; } This seems to confirm your explanation (at least what i understood of your explanation). -- Best regards, Mattia