Graph Edit Distance - Python

NetworkX

NetworkX (NX) is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

https://networkx.lanl.gov/

similarity

https://www.kite.com/python/docs/networkx.similarity

The graph edit distance is the number of edge/node changes needed to make two graphs isomorphic.
The default algorithm/implementation is sub-optimal for some graphs.
The problem of finding the exact Graph Edit Distance (GED) is NP-hard so it is often slow. 

graph edit distance

https://www.kite.com/python/docs/networkx.similarity.graph_edit_distance

Returns GED (graph edit distance) between graphs G1 and G2.
Graph edit distance is a graph similarity measure analogous to Levenshtein distance for strings.
It is defined as minimum cost of edit path (sequence of node and edge edit operations) transforming graph G1 to graph isomorphic to G2.

Signature

graph_edit_distance (
G1,
G2,
node_match: __class__=None,
edge_match: __class__=None,
node_subst_cost: __class__=None,
node_del_cost: __class__=None,
node_ins_cost: __class__=None,
edge_subst_cost: __class__=None,
edge_del_cost: __class__=None,
edge_ins_cost: __class__=None,
upper_bound: __class__=None
)

Parameters   

G1, G2: graphs The two graphs G1 and G2 must be of the same type.

node_match : A function that returns True if node n1 in G1 and n2 in G2 should be considered equal during matching.
The function will be called like node_match(G1.nodes[n1], G2.nodes[n2]). That is, the function will receive the node attribute dictionaries for n1 and n2 as inputs.
Ignored if node_subst_cost is specified. If neither node_match nor node_subst_cost are specified then node attributes are not considered.

edge_match : A function that returns True if the edge attribute dictionaries for the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be considered equal during matching.
The function will be called like edge_match(G1[u1][v1], G2[u2][v2]). That is, the function will receive the edge attribute dictionaries of the edges under consideration.
Ignored if edge_subst_cost is specified. If neither edge_match nor edge_subst_cost are specified then edge attributes are not considered.

>>> Operações básicas de edição e seus custos <<<

node_subst_cost, node_del_cost, node_ins_cost : Functions that return the costs of node substitution, node deletion, and node insertion, respectively.
The functions will be called like node_subst_cost(G1.nodes[n1], G2.nodes[n2]), node_del_cost(G1.nodes[n1]), node_ins_cost(G2.nodes[n2]). That is, the functions will receive the node attribute dictionaries as inputs.
The functions are expected to return positive numeric values. Function node_subst_cost overrides node_match if specified.
If neither node_match nor node_subst_cost are specified then default node substitution cost of 0 is used (node attributes are not considered during matching).
If node_del_cost is not specified then default node deletion cost of 1 is used.
If node_ins_cost is not specified then default node insertion cost of 1 is used.

edge_subst_cost, edge_del_cost, edge_ins_cost : Functions that return the costs of edge substitution, edge deletion, and edge insertion, respectively.
The functions will be called like edge_subst_cost(G1[u1][v1], G2[u2][v2]), edge_del_cost(G1[u1][v1]), edge_ins_cost(G2[u2][v2]). That is, the functions will receive the edge attribute dictionaries as inputs.
The functions are expected to return positive numeric values. Function edge_subst_cost overrides edge_match if specified.
If neither edge_match nor edge_subst_cost are specified then default edge substitution cost of 0 is used (edge attributes are not considered during matching).
If edge_del_cost is not specified then default edge deletion cost of 1 is used. If edge_ins_cost is not specified then default edge insertion cost of 1 is used.

>>> Limite máximo para a distância <<<  

upper_bound : Maximum edit distance to consider. Return None if no edit distance under or equal to upper_bound exists.

Examples

 G1 = nx.cycle_graph(6)
 G2 = nx.wheel_graph(7)
 nx.graph_edit_distance(G1, G2) 7.0

optimal_edit_paths

https://www.kite.com/python/docs/networkx.similarity.optimal_edit_paths

Retorna não só a distância mas também a sequencia de operações de edição para essa distância

optimize_graph_edit_distance

https://www.kite.com/python/docs/networkx.similarity.optimize_graph_edit_distance

Generator of consecutive approximations of graph edit distance.