将节点从小图插入到大图

Question

好的，这是场景。我有一个我称之为 G的大图，其中包含每个节点（x 和 y 坐标）以及连接边的位置信息。图 G 是基本事实。现在我有一个较小的图，我称之为“sub”，其中包含表示包含 x 和 y 位置误差的测量值的节点。我需要将 sub 的节点投影到 G 上，这会保留沿 G 的明显正确路径。（请参阅附加的图像和代码）。

我有代码可以将任何单个节点投影到图形上，但是单个节点的放置通常会导致从投影节点 a 到投影节点 f 的路径包含沿 G 的短进出不连续性（不是在这个特定示例中，我的真正问题是更大、更复杂的图，这会一直导致这些不连续性）。我的投影方法可能是问题所在，因为我只是检查距离被测节点最近的两个节点，然后在这两个节点之间投影该节点。在这个例子中，右上角的红色节点可能会被投影到右上角的黑色对角边上，而不是垂直边上。

我觉得必须有一种方法可以对 G 上的路径子进行某种最小二乘拟合，但我似乎无法找到类似这样的任何细节。

是否存在算法来做到这一点？

如果我的措辞不好，我很抱歉，我对使用图表很陌生，不确定常见的命名法是什么。

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import collections as mc

def GetPlottingData(graph):
    lines = []
    for edge in graph.edges():

        x0 = graph.nodes[edge[0]]['x']
        y0 = graph.nodes[edge[0]]['y']
        x1 = graph.nodes[edge[1]]['x']
        y1 = graph.nodes[edge[1]]['y']

        lines.append([(x0, y0), (x1, y1)])

    node_x = []
    node_y = []
    for node in graph.nodes():
        x = graph.nodes[node]['x']
        y = graph.nodes[node]['y']
        node_x.append(x)
        node_y.append(y)

    return lines, node_x, node_y

G = nx.Graph()

nodes = [('A', {'x': -2, 'y': 0}),
         ('B', {'x': -1, 'y': 0}),
         ('C', {'x': 1, 'y': 0}),
         ('D', {'x': 2, 'y': 0}),
         ('E', {'x': 3, 'y': 0}),
         ('F', {'x': 1, 'y': 1}),
         ('G', {'x': 2, 'y': 1}),
         ('H', {'x': 3, 'y': 1}),
         ('I', {'x': 3, 'y': 2}),
         ('J', {'x': 4, 'y': 3}),
         ('K', {'x': 4, 'y': 1.5})]

edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('C', 'F'), ('D', 'G'),
         ('E', 'H'), ('F', 'G'), ('G', 'H'), ('G', 'I'), ('H', 'I'), ('H', 'K'),
         ('K', 'J'), ('I', 'J')]

G.add_nodes_from(nodes)
G.add_edges_from(edges)

sub_nodes = [('a', {'x': -1.8, 'y': .2}),
             ('b', {'x': .7, 'y': .1}),
             ('c', {'x': 1.6, 'y': 1.1}),
             ('d', {'x': 2.9, 'y': 0.9}),
             ('e', {'x': 3.4, 'y': 1.3}),
             ('f', {'x': 4.1, 'y': 2.3})]

sub_edges = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('e', 'f')]

sub = nx.Graph()
sub.add_nodes_from(sub_nodes)
sub.add_edges_from(sub_edges)

main_lines, main_x, main_y = GetPlottingData(G)
sub_lines, sub_x, sub_y = GetPlottingData(sub)

fig, ax = plt.subplots()
fig.set_size_inches((8, 8))

main_lc = mc.LineCollection(main_lines, colors='black')
sub_lc = mc.LineCollection(sub_lines, colors='red')
ax.add_collection(main_lc)
ax.add_collection(sub_lc)

ax.scatter(main_x, main_y, color='black')
ax.scatter(sub_x, sub_y, color='red')
ax.autoscale()
ax.tick_params('both', labelsize=12)
ax.set_xlabel('X', size=13)
ax.set_ylabel('Y', size=13)
ax.ticklabel_format(useOffset=False)