GitLab

Created by: 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