optimize_edit_paths(G1, G2, node_match=None, edge_match=None, node_subst_cost=None, node_del_cost=None, node_ins_cost=None, edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, upper_bound=None, strictly_decreasing=True, roots=None, timeout=None)
Graph edit path is a sequence of node and edge edit operations transforming graph G1 to graph isomorphic to G2. Edit operations include substitutions, deletions, and insertions.
Graph edit distance is defined as minimum cost of edit path.
The two graphs G1 and G2 must be of the same type.
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.
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.
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.
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.
Maximum edit distance to consider.
If True, return consecutive approximations of strictly decreasing cost. Otherwise, return all edit paths of cost less than or equal to the previous minimum cost.
Tuple where first element is a node in G1 and the second is a node in G2. These nodes are forced to be matched in the comparison to allow comparison between rooted graphs.
Maximum number of seconds to execute. After timeout is met, the current best GED is returned.
GED (graph edit distance) calculation: advanced interface.
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.similarity.optimize_graph_edit_distance
networkx.algorithms.similarity.optimal_edit_paths
networkx.algorithms.similarity
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them