nx.optimal_edit_paths not finding optimal
After debugging https://github.com/networkx/networkx/issues/8054 we found out a minimal example that reproduces the issue. Creating this separate issue to organize discussion.
This substitution cost function is triggering a corner case for the algorithm where it detects it has the same "cost" to perform an insertion operation than edit.t
Here is a minimum code snippet that reproduces the issue:
import networkx as nx
def node_subst_cost(node_1:dict, node_2:dict)-> float:
if node_2['i'] == 1:
return 0
elif node_2['i'] == 2 or node_1['i'] == 3:
return 2
else:
return 2.2
def clique(nodes):
G = nx.Graph()
for x in nodes:
G.add_node(x, i=x)
for y in nodes:
if x != y:
G.add_edge(x, y)
return G
example_graphs = [
clique([1,2,3]),
clique([3,2,1])
]
for eg in example_graphs:
edits, distance = nx.optimal_edit_paths(eg, example_graphs[0], node_subst_cost=node_subst_cost)
print(distance)
for x in edits:
for y in x:
print(y)
print('-')
print('______')Which outputs:
8.0
[(1, None), (2, 1), (3, 3), (None, 2)]
[((1, 2), None), ((1, 3), None), ((2, 3), (1, 3)), (None, (1, 2)), (None, (2, 3))]
-
______
4.0
[(3, 3), (2, 1), (1, 2)]
[((3, 2), (1, 3)), ((3, 1), (2, 3)), ((2, 1), (1, 2))]
-
______The algorithm is internally computing the edit distance matrix and then calling https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html to detect the best step. We can see that equivalent matrices are leading to different assignments with the same cost:
make_CostMatrix [[ 0. 2. 2.2 1. 19.6 19.6]
[ 0. 2. 2.2 19.6 1. 19.6]
[ 0. 2.2 2. 19.6 19.6 1. ]
[ 1. 19.6 19.6 0. 0. 0. ]
[19.6 1. 19.6 0. 0. 0. ]
[19.6 19.6 1. 0. 0. 0. ]]
assignment = [0 1 2 5 3 4] [2 0 1 3 4 5]
assignment cost = 4.0make_CostMatrix [[ 0. 2.2 2. 1. 19.6 19.6]
[ 0. 2. 2.2 19.6 1. 19.6]
[ 0. 2. 2.2 19.6 19.6 1. ]
[ 1. 19.6 19.6 0. 0. 0. ]
[19.6 1. 19.6 0. 0. 0. ]
[19.6 19.6 1. 0. 0. 0. ]]
assignment = [0 1 2 5 3 4] [2 0 1 3 4 5]
assignment cost = 4.0Algorithm is getting confused because it only costs 1 to insert a new node, I believe the bug is when handling insertions: instead of assigning a node of each graph, the algorithm requires another iteration to do that (which ends up increasing the cost).
Source: networkx/networkx