8
$\begingroup$

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]

enter image description here

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:-

enter image description here

How can I get it done? Many thanks!

$\endgroup$
5
$\begingroup$

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]

enter image description here

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]]

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thanks for reply. Did I misunderstand something? It seems that I don't have the function IGMeshGraph. I am using Mathematica 11.2. $\endgroup$ – H42 Jun 13 '18 at 17:27
  • $\begingroup$ @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. $\endgroup$ – Szabolcs Jun 13 '18 at 17:28
  • $\begingroup$ @HMC Sorry, but at this point I can't be bothered to do any graph stuff without the convenience of IGraph/M :-P $\endgroup$ – Szabolcs Jun 13 '18 at 17:28
  • $\begingroup$ @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) $\endgroup$ – Szabolcs Jun 13 '18 at 17:44
  • $\begingroup$ 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. $\endgroup$ – H42 Jun 14 '18 at 3:29
1
$\begingroup$

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]

enter image description here

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

HighlightGraph[makeConnected [nng2], nng2]

enter image description here

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

True

$\endgroup$
1
$\begingroup$

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}]
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Jun 14 '18 at 12:30
  • $\begingroup$ 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... $\endgroup$ – Fidel I. Schaposnik Jun 14 '18 at 13:57
  • $\begingroup$ 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. $\endgroup$ – H42 Jun 14 '18 at 14:19
  • $\begingroup$ @Szabolcs So I will use Delaunay triangulation in my case. May I ask what is the theorectical complexity of Delaunay triangulation? $\endgroup$ – H42 Jun 14 '18 at 14:21
  • 1
    $\begingroup$ 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... $\endgroup$ – Fidel I. Schaposnik Jun 14 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.