Quick question: Do not quite understand simple output

[davidlee321]

This simple example shows a different edit distance compared to networkX's GED. Would be great if someone could help me understand the difference. From my understanding of GED, the edit distance should be 1, not 2.

import networkx
import gmatch4py as gm

g1=nx.complete_bipartite_graph(2,3) 
g2=nx.complete_bipartite_graph(2,3)
g2.add_edge(0, 1)
adj=[(v, neighbors) for v, neighbors in g1.adjacency()]
print(adj)
adj=[(v, neighbors) for v, neighbors in g2.adjacency()]
print(adj)
ged=gm.GraphEditDistance(1,1,1,1) # all edit costs are equal to 1
result=ged.compare([g1,g2],None) 
print(result)

[(0, {2: {}, 3: {}, 4: {}}), (1, {2: {}, 3: {}, 4: {}}), (2, {0: {}, 1: {}}), (3, {0: {}, 1: {}}), (4, {0: {}, 1: {}})]
[(0, {2: {}, 3: {}, 4: {}, 1: {}}), (1, {2: {}, 3: {}, 4: {}, 0: {}}), (2, {0: {}, 1: {}}), (3, {0: {}, 1: {}}), (4, {0: {}, 1: {}})]

[[0. 2.]
 [2. 0.]]

ged_nx = nx.graph_edit_distance(g1, g2)
print(ged_nx)

1.0

[jacquesfize]

Dear @davidlee321,

It depends on the algorithm heuristic used to compute the edit distance. Here, the algorithm heuristic is different from the one used by networkX.

Best, @Jacobe2169