# How to connect all points in a graph generated by a set of given vertexes?

I am trying to construct a tree by looking at the nearest neighbors (or just approximately nearest for higher efficient) of a set of given vertexes. I first try this:-

BlockRandom[SeedRandom[12]; pts = RandomReal[1, {10, 2}]];
NearestNeighborGraph[pts, 1]


As you can see, there are 3 trees and they are not connected. I want to connect them in a way (or some other ways) similar to below:-

How can I get it done? Many thanks!

This is called the Euclidean minimum spanning tree problem. The Euclidean minimum spanning tree is a subgraph of the Delaunay graph. Exploiting this, we can solve this as follows.

Generate points:

pts = RandomPoint[Disk[], 50]


Compute a Delaunay triangulation and retrieve it as a graph (using IGraph/M, which needs to be installed first):

graph = IGMeshGraph@DelaunayMesh[pts]


Note that this is a weighted graph with the weights representing the edge lengths.

Find a minimum spanning tree (taking edge weights into account) and transfer the vertex coordinates from the original graph.

FindSpanningTree[graph, VertexCoordinates -> GraphEmbedding[graph]]


This gives us the graph (tree) with the shortest total edge length that connects all of the points.

You may find it useful to use

IGSpanningTree[graph, VertexCoordinates -> GraphEmbedding[graph]]


instead, as this function preserves the edge weights (FindSpanningTree throws them away).

Here's a possible alternative for IGraph/M's IGMeshGraph function (so that you don't have to install IGraph/M just for this trivial task):

meshGraph[mesh_] :=
Graph[
Range@MeshCellCount[mesh, 0],
MeshCells[mesh, 1][[All, 1]],
EdgeWeight -> PropertyValue[{mesh, 1}, MeshCellMeasure],
VertexCoordinates -> MeshCoordinates[mesh]
]


You may be interested in other proximity graph functions that IGraph/M has, such IGLuneBetaSkeleton, IGRelativeNeighborhoodGraph, etc.

• Thanks for reply. Did I misunderstand something? It seems that I don't have the function IGMeshGraph. I am using Mathematica 11.2. – H42 Jun 13 '18 at 17:27
• @HMC As I said, it is part of the IGraph/M package. But you can also implement your own mesh-to-graph conversion. IGraph/M is open source, so you can check how it does it. – Szabolcs Jun 13 '18 at 17:28
• @HMC Sorry, but at this point I can't be bothered to do any graph stuff without the convenience of IGraph/M :-P – Szabolcs Jun 13 '18 at 17:28
• @HMC I added a possible implementation of IGMeshGraph to avoid the impression that I'm trying to push my package on people (in reality I was just lazy, and I really don't do graph stuff without it anymore) – Szabolcs Jun 13 '18 at 17:44
• Thanks, and it really helps. I noted a typo of your function name, which I trust should be IGMeshGraph  instead of meshGraph. I tried to edit it for you, but my edit needs to be 6 characters at least so I can't submit the amendment. Please note. – H42 Jun 14 '18 at 3:29

Starting with a disconnected graph add new edges to make the graph connected:

ClearAll[makeConnected]
makeConnected = If[ConnectedGraphQ @ #, #,
EdgeAdd[#, Join @@ UndirectedEdge @@@ MinimalBy[#, EuclideanDistance @@ # &]&/@
Tuples /@ Partition[ConnectedComponents[#], 2, 1]]]&;


Examples:

BlockRandom[SeedRandom[12]; pts = RandomReal[1, {10, 2}]];
nng = NearestNeighborGraph[pts, 1];

HighlightGraph[makeConnected @ nng, nng]


BlockRandom[SeedRandom[12]; pts2 = RandomReal[1, {40, 2}]];
nng2 = NearestNeighborGraph[pts2, 1];

HighlightGraph[makeConnected [nng2], nng2]


IsomorphicGraphQ[makeConnected @ nng2, FindSpanningTree[makeConnected @ nng2]]


True

If what you want is to obtain the minimum spanning tree of the distance graph (i.e. the complete graph with edge-weights equal to the Euclidean distance between the points in your set), you can do so using built-in Mathematica functions like so

FindSpanningTree@WeightedAdjacencyGraph@Outer[Norm[#1 - #2] &, Points, Points,1]


I think the only part requiring some explanation is

Outer[Norm[#1 - #2] &, Points, Points,1]


which builds the distance graph adjacency matrix, and is equivalent to the more readable

Table[Norm[p1-p2],{p1,Points},{p2,Points}]

• DistanceMatrix would be much faster (but still of $O(n^2)$ complexity). The purpose of using a Delaunay triangulation as the base graph was to avoid the $O(n^2)$ complexity. – Szabolcs Jun 14 '18 at 12:30
• Thanks for your comment, I didn't know about DistanceMatrix. I just thought I'd mention this because it was conceptually simpler and efficiency didn't seem the issue here... – Fidel I. Schaposnik Jun 14 '18 at 13:57
• Thanks for both. I tested some cases and recorded the timing. In 2D cases, seems that WeightedAdjacencyGraph@Outer is faster than IGMeshGraph@DelaunayMesh more than 10 times. My real case is a 3D case, in which IGMeshGraph@DelaunayMesh is faster than WeightedAdjacencyGraph@Outer 10 times. – H42 Jun 14 '18 at 14:19
• @Szabolcs So I will use Delaunay triangulation in my case. May I ask what is the theorectical complexity of Delaunay triangulation? – H42 Jun 14 '18 at 14:21
• Delaunay triangulation can be done in O(n log n), so it should be faster for large enough sets. As suggested by @Szabolcs , however, DistanceMatrix will be much faster than Outer even if it has the same O(n^2) complexity, so this is what you should compare to timingwise... – Fidel I. Schaposnik Jun 14 '18 at 15:13