Skip to main content
`Ctrl`+`K`

# optimal_edit_paths

optimal_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)

  Returns all minimum-cost edit paths transforming G1 to G2.

  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.

  Parameters:
    G1, G2: graphs

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

    node_match callable

      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 callable

      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.

    node_subst_cost, node_del_cost, node_ins_cost callable

      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 callable

      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.

    upper_bound numeric

      Maximum edit distance to consider.

  Returns:
    edit_paths list of tuples (node_edit_path, edge_edit_path)

      - node_edit_path : list of tuples `(u, v)` indicating node transformations between `G1` and `G2`. `u` is `None` for insertion, `v` is `None` for deletion.

      - edge_edit_path : list of tuples `((u1, v1), (u2, v2))` indicating edge transformations between `G1` and `G2`. `(None, (u2,v2))` for insertion and `((u1,v1), None)` for deletion.

    cost numeric

      Optimal edit path cost (graph edit distance). When the cost is zero, it indicates that `G1` and `G2` are isomorphic.

  See also

  `graph_edit_distance`, `optimize_edit_paths`

  Notes

  To transform `G1` into a graph isomorphic to `G2`, apply the node and edge edits in the returned `edit_paths`. In the case of isomorphic graphs, the cost is zero, and the paths represent different isomorphic mappings (isomorphisms). That is, the edits involve renaming nodes and edges to match the structure of `G2`.

  References

  [1]

  Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, Patrick Martineau. An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. 4th International Conference on Pattern Recognition Applications and Methods 2015, Jan 2015, Lisbon, Portugal. 2015, <10.5220/0005209202710278>. <hal-01168816> https://hal.archives-ouvertes.fr/hal-01168816

  Examples

      >>> G1 = nx.cycle_graph(4)
      >>> G2 = nx.wheel_graph(5)
      >>> paths, cost = nx.optimal_edit_paths(G1, G2)
      >>> len(paths)
      40
      >>> cost
      5.0