Ok here is the scenario. I have a large graph I'm calling G which contains position information for each node (x and y coordinates) as well as connecting edges. Graph G is ground truth. Now I have a smaller graph I am calling 'sub' which contains nodes which represent measurements that contain position error in both x and y. I need to project the nodes of sub onto G which preserves the obvious correct path along G. (See attached image and code).
I have code to project any individual node onto the graph but the placement of individual nodes typically causes the path from projected node a to projected node f to contain short in and out discontinuities along G (not in this particular example, my real problem is a much larger and more complicated graph which causes these discontinuities all the time). My method of projection could be the problem in that I just check for the two closest nodes to the measured node and then project that node between those two. In this example, the top right red node would probably be projected onto the top-right black diagonal edge instead of on the vertical edge.
I feel like there must be a way to do some sort of least squares fitting of path sub onto G, but I can't seem to find any details for something like this.
Does an algorithm exist to do this?
I'm sorry if I am not wording this well, I am very new to working with graphs and am not sure what the common nomenclature is.
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)