将节点添加到断开连接的图中，以便完全连接图组件，并具有节点间距离约束

Question

我有一个图，其中每个节点都有一个由 (x,y) 给定的空间位置，并且仅当每个节点之间的欧几里得距离为sqrt(2)或更小时，节点之间的边才会连接。这是我的例子：

import networkx

G=nx.Graph()

G.add_node(1,pos=(1,1))
G.add_node(2,pos=(2,2))
G.add_node(3,pos=(1,2))

G.add_node(4,pos=(1,4))
G.add_node(5,pos=(2,5))

G.add_node(6,pos=(4,2))
G.add_node(7,pos=(5,2))
G.add_node(8,pos=(5,3))

# Connect component one
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)

# Connect component two
G.add_edge(6,7)

# Connect component three
G.add_edge(6,8)
G.add_edge(7,8)
G.add_edge(4,5)

pos=nx.get_node_attributes(G,'pos')

nx.draw(G,pos)

我的问题是，如何确定附加节点的最佳位置和数量，以便连接图形组件，同时确保任何附加节点始终位于现有节点的sqrt(2)内？

Answer 1

我非常确信这个问题是 NP 困难的。我知道的最接近的问题是具有八线性度量的几何斯坦纳树问题。我有两个相当快速但肮脏的建议。两者都是启发式的。

第一个想法：将问题表述为欧几里得施泰纳树问题（https://en.wikipedia.org/wiki/Steiner_tree_problem#Euclidean_Steiner_tree），其中您只考虑问题的节点并首先忘记边缘。使用 GeoSteiner 解决问题： http://www.geosteiner.com/ 这应该可以快速为您提供 10000 个或更多节点问题的解决方案（如果您需要解决更大的问题，可以在全斯坦纳树生成并使用https://scipjack.zib.de/）。没有Python接口，但只需将问题写入纯文本文件，语法非常简单。然后，将额外的节点放入 GeoSteiner 提供的解决方案中，以满足 \sqrt(2) 条件。最后，您需要进行一些清理以消除多余的边缘，因为该解决方案不会考虑到您在原始问题中已经存在的边缘。获取到目前为止计算出的所有边和节点，并通过给所有原始边权重 0 和所有新添加的边权重 1 来定义加权图。考虑图中的 Steiner 树问题 ( https://en. wikipedia.org/wiki/Steiner_tree_problem#Steiner_tree_in_graphs_and_variants）在此加权图上，其中终端集对应于您的原始节点。使用 SCIP-Jack 解决此斯坦纳树问题：https ://scipjack.zib.de/ 。

第二个想法：直接将您的问题视为图中的斯坦纳树问题，如下所示：每个原始边都分配权重 0，将所有原始节点视为终端。添加其他节点和边，彼此之间的距离最多为 \sqrt(2)。例如，您可以在所有连接的组件周围放置一个大矩形，并从每个节点以 0,45,90 度的角度递归添加 8 个节点，...距离 sqrt(2) 且边缘为权重1 图中的斯坦纳树问题，只要它们在矩形内。如果这些节点之一位于原始节点之一的距离 sqrt(2) 范围内，则将它们直接与权重为 1 的边连接。使用 SCIP-Jack 解决图中相应的 Steiner 树问题。