NetworkXのGEDを実行する際の重み付け（cost）を増やしたい。

Question

前提

環境[python3.9,networkxも最新です,anaconda]
上記の環境でグラフの類似率を求めるプログラミングを実行しています。
https://networkx.org/documentation/stable/reference/algorithms/similarity.html#

↑NetworkXの公式サイトの類似グラフのgraph_edit_distanceの詳細サイトを参考にプログラミングを組みました。
GEDという手法を用いるのですが、その内容を理解しないといけないので参考URLを置いておきます。
https://nw.tsuda.ac.jp/lec/EditDistance/

そこで削除、置換、作成が行われる際の重みづけができるのですが、そのコード通りに実行してもエラーが出てしまいます。

実現したいこと

削除、置換、作成が行われる際の重みづけをできるようにする。
（普段は削除は１、置換は1、作成は１だと思いますが、costを増やしたいです。）

発生している問題・エラーメッセージ

>>> nx.graph_edit_distance(G1, G2,node_del_cost=1,node_ins_cost=2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/tokut/opt/anaconda3/lib/python3.9/site-packages/networkx/algorithms/similarity.py", line 190, in graph_edit_distance
    for vertex_path, edge_path, cost in optimize_edit_paths(
  File "/Users/tokut/opt/anaconda3/lib/python3.9/site-packages/networkx/algorithms/similarity.py", line 1089, in optimize_edit_paths
    del_costs = [node_del_cost(G1.nodes[u]) for u in pending_u]
  File "/Users/tokut/opt/anaconda3/lib/python3.9/site-packages/networkx/algorithms/similarity.py", line 1089, in <listcomp>
    del_costs = [node_del_cost(G1.nodes[u]) for u in pending_u]
TypeError: 'int' object is not callable

該当のソースコード

import numpy as np
import networkx as nx
import scipy as sp
import matplotlib.pyplot as plt

G1 = nx.Graph()
G1.add_nodes_from([("Owner1", {"attribute":"Owner1"},{"label":"Owner1"}),
("M1", {"attribute":"M1"},{"label":"M1"}),
("M2", {"attribute":"M2"},{"label":"M2"}),
("R0", {"attribute":"R0"},{"label":"R0"})])
G1.add_edges_from([("Owner1","R0"), ("Owner1", "M1"),
("M1", "M2")])
print(G1.nodes())
print(G1.edges())
nx.nx_agraph.view_pygraphviz(G1, prog='fdp')

G2 = nx.Graph()
G2.add_nodes_from([("C1", {"attribute":"C1"},{"label":"C1"}),
("S1", {"attribute":"S1"},{"label":"S1"}),
("S2", {"attribute":"S2"},{"label":"S2"}),
("R0R", {"attribute":"R0R"},{"label":"R0R"}),
("M3", {"attribute":"M3"},{"label":"M3"})])
G2.add_edges_from([("C1", "R0R"),
("S1", "S2"), ("C1", "S1"),
("M3", "S2")])
print(G2.nodes())
print(G2.edges())

nx.nx_agraph.view_pygraphviz(G2, prog='fdp')

nx.graph_edit_distance(G1, G2,node_subst_cost=(G1.nodes[G1], G2.nodes[G2]), node_del_cost=1, node_ins_cost=1)

こちらの2つのグラフのGEDは２です。（作成✖️２[nodeとedges]）

こちらにdeleteとinsertの重み付けをしたいのですが、公式サイトでは

上記の通り、costの大きさ、値をどこに書いていればいいのかが書いてません。公式サイトの例題ではrootの例題になっており、説明がありません。
そこで自分で作ってみたのですが、うまくいきません。

試したこと

様々な記載方法を試しましたが、実行する際にエラーが出てしまいます。

https://data-analysis-stats.jp/%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92/networkx%E3%81%AE%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E9%A1%9E%E4%BC%BC%E5%BA%A6/
上記のサイトを利用してラベル付きのGED測定はできたのですが、重み付けの記事がなく、どうやってうまくcostを自分のやりたいように増やせるかがわかりません。

補足情報（FW/ツールのバージョンなど）

環境[python3.9,networkxも最新です,anaconda]

Answer 1

コメントによる返信ですとインデントがうまく反映できないため、回答の方にインデント含めた例を提示させていただきます。

(
    [# 編集のリストの開始
        (# 最小コストを達成する編集1個目の開始
            [ # 編集1個目のnodeの編集についてのリスト
                ('Owner1', 'C1'), # "Owner1"を"C1"に置換
                ('M1', 'S1'),
                ('M2', 'S2'),
                ('R0', 'R0R'),
                (None, 'M3') # "M3"nodeを追加
            ], 
            [ # 編集1個目のedgeの編集についてのリスト
                (('Owner1', 'M1'), ('C1', 'S1')), # "Owner1"と"M1"を繋ぐ辺を"C1"と"S1"を繋ぐ辺に置換
                (('M1', 'M2'), ('S1', 'S2')), 
                ('Owner1', 'R0'), ('C1', 'R0R')),
                (None, ('S2', 'M3')) # "S2"と"M3"を繋ぐ辺を追加
             ]
         ), # 最小コストを達成する編集1個目の終了
     
        (# 最小コストを達成する編集2個目の開始
            [ # 編集2個目のnodeの編集についてのリスト
                ('M1', 'C1'),
                ('Owner1', 'S1'),
                ('R0', 'S2'),
                ('M2', 'R0R'),
                (None, 'M3')
            ], 
            [ # 編集2個目のedgeの編集についてのリスト
                (('Owner1', 'M1'), ('C1', 'S1')),
                (('Owner1', 'R0'), ('S1', 'S2')),
                (('M1', 'M2'), ('C1', 'R0R')),
                (None, ('S2', 'M3'))
            ]
         ), # 最小コストを達成する編集2個目の終了
     
        (# 最小コストを達成する編集3個目の開始
            [ # 編集3個目のnodeの編集についてのリスト
                ('M2', 'C1'),
                ('M1', 'S1'),
                ('Owner1', 'S2'),
                (None, 'R0R'),
                ('R0', 'M3')
            ],
            [ # 編集3個目のedgeの編集についてのリスト
                (('M1', 'M2'), ('C1', 'S1')),
                (('Owner1', 'M1'), ('S1', 'S2')),
                (None, ('C1', 'R0R')),
                (('Owner1', 'R0'), ('S2', 'M3'))
            ]
         ), # 最小コストを達成する編集3個目の終了
     
        (# 最小コストを達成する編集4個目の開始
            [ # 編集4個目のnodeの編集についてのリスト
                ('R0', 'C1'),
                ('Owner1', 'S1'),
                ('M1', 'S2'),
                (None, 'R0R'),
                ('M2', 'M3')
            ],
            [ # 編集4個目のedgeの編集についてのリスト
                (('Owner1', 'R0'), ('C1', 'S1')),
                (('Owner1', 'M1'), ('S1', 'S2')),
                (None, ('C1', 'R0R')),
                (('M1', 'M2'), ('S2', 'M3'))
            ]
        ) # 最小コストを達成する編集4個目の終了
     ], #編集のリストの終了 
 2.0 # 最小コスト
 )

Comments

[TKng1998]

ありがとうございます。
本当に助かりました。

[TKng1998]

現在、ベストアンサーの最後の文の属性による重み付けの計算をしているのですが、こちらのコードを実行しても結果が出ません。エラーもなく、何が間違っているのかがわからない状態です。
elseを使うと実行完了後、値の結果が出ないことはわかっています。

port networkx as nx
#前処理後
G1 = nx.Graph()
G1.add_nodes_from([
("userinfo", {"attribute":"entity"}),
("store", {"attribute":"entity"}),
("product", {"attribute":"entity"}),
("Order_document", {"attribute":"entity"}),
("loginCO2", {"attribute":"control"}),
("SELECT", {"attribute":"control"}),
("order_CRUD", {"attribute":"control"}),
("order_RECEIVE2", {"attribute":"control"}),
("login2", {"attribute":"boundary"}),
("menu2", {"attribute":"boundary"}),
("cart_confirm2", {"attribute":"boundary"})])

G1.add_edges_from([
("loginCO2", "login2"),
("loginCO2","menu2"), ("loginCO2", "userinfo"),
("menu2","SELECT"), ("SELECT", "cart_confirm2"),
("SELECT", "order_CRUD"),
("SELECT","store"), ("SELECT", "product"),
("order_CRUD","Order_document"), ("order_CRUD", "cart_confirm2"),
("cart_confirm2","order_RECEIVE2"),("Order_document","order_RECEIVE2")
])
G2 = nx.Graph()
G2.add_nodes_from([
("userinfo", {"attribute":"entity"}),
("team", {"attribute":"entity"}),
("folder", {"attribute":"entity"}),
("note", {"attribute":"entity"}),
("loginCO2", {"attribute":"control"}),
("SELECT", {"attribute":"control"}),
("Foldernote_CRUD", {"attribute":"control"}),
("Note_RECEIVE", {"attribute":"control"}),
("note_confirm2", {"attribute":"boundary"}),
("menu2", {"attribute":"boundary"}),
("login2", {"attribute":"boundary"})
])

G2.add_edges_from([
("loginCO2", "login2"),
("loginCO2", "menu2"),
("loginCO2", "userinfo"),
("loginCO2", "team"),
("SELECT","menu2"), ("SELECT", "note_confirm2"),
("SELECT","folder"), ("SELECT", "note"),
("SELECT","Foldernote_CRUD"), ("Foldernote_CRUD", "folder"),
("note_confirm2","Foldernote_CRUD"),
("Foldernote_CRUD","note"), ("note", "Note_RECEIVE"),("note_confirm2", "Note_RECEIVE"),
])

def node_subst_cost(node1, node2):
return 1

def node_ins_cost(node):
if node["attribute"] == "control":
return 3
else:
return 1

def node_del_cost(node):
if node["attribute"] == "control":
return 3
else:
return 1

nx.graph_edit_distance(G1, G2,
node_subst_cost=node_subst_cost,
node_del_cost=node_del_cost,
node_ins_cost=node_ins_cost)

[fixk]

私の環境で同じコードを実行したところ、15.0という結果が得られました。値の結果が出ないという部分をもう少し詳しく教えてください。nx.graph_edit_distance()の戻り値がNoneということでしょうか。

[TKng1998]

今、確認した所、うまくいきました。
素早い回答、ありがとうございます。

[TKng1998]

こちらのコードがうまく行きません。
Eroor内容はこちらです。
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-16-819cefa46de3> in <module>
87 return 1
88
---> 89 nx.graph_edit_distance(G1, G2,
90 node_subst_cost=node_subst_cost,
91 node_del_cost=node_del_cost,

3 frames
<ipython-input-16-819cefa46de3> in node_del_cost(node)
78
79 def node_del_cost(node):
---> 80 if node["attribute"] == "control":
81 return 3
82 elif node["attribute"] == "boundary":

KeyError: 'attribute'

G1,G2の内容によってはこのようなエラーが出てしまいますが、その理由がわかりません。

コード本文は
#stock mo

import networkx as nx

G1 = nx.Graph()
G1.add_nodes_from([
("userinfo", {"attribute":"entity"}),
("store", {"attribute":"entity"}),
("product", {"attribute":"entity"}),
("Order_document", {"attribute":"entity"}),
("cart", {"attribute":"entity"}),
("loginCO2", {"attribute":"control"}),
("SELECT", {"attribute":"control"}),
("order_CRUD", {"attribute":"control"}),
("order_RECEIVE2", {"attribute":"control"}),
("Cart_RECEIVE", {"attribute":"control"}),
("login2", {"attribute":"boundary"}),
("menu2", {"attribute":"boundary"}),
("cart_confirm2", {"attribute":"boundary"}),
("cart_confirm", {"attribute":"boundary"}),
("Customer", {"attribute":"human"})])

G1.add_edges_from([
("Customer", "login2"),
("Customer","menu2"), ("Customer", "risyu_confirm2"),
("Customer","cart_confirm"), ("loginCO2", "login2"),
("loginCO2","menu2"), ("loginCO2", "userinfo"),
("menu2","SELECT"), ("SELECT", "cart_confirm2"),
("SELECT","cart_confirm"), ("SELECT", "order_CRUD"),
("SELECT","store"), ("SELECT", "product"),
("order_CRUD","Order_document"), ("order_CRUD", "cart_confirm2"),
("order_CRUD", "cart"),
("cart_confirm2","order_RECEIVE2"),("Order_document","order_RECEIVE2"),
("cart_confirm","order_RECEIVE2"),
("cart_confirm", "Cart_RECEIVE"),
("Cart_RECEIVE","cart")])

G2 = nx.Graph()
G2.add_nodes_from([
("userinfo", {"attribute":"entity"}),
("team", {"attribute":"entity"}),
("folder", {"attribute":"entity"}),
("note", {"attribute":"entity"}),
("loginCO2", {"attribute":"control"}),
("SELECT", {"attribute":"control"}),
("Foldernote_CRUD", {"attribute":"control"}),
("Note_RECEIVE", {"attribute":"control"}),
("login2", {"attribute":"boundary"}),
("menu2", {"attribute":"boundary"}),
("note_confirm2", {"attribute":"boundary"}),
("Customer", {"attribute":"human"})])

G2.add_edges_from([
("Customer", "login2"),
("Customer","menu2"), ("Customer", "note_confirm2"),
("loginCO2", "login2"),
("loginCO2","menu2"), ("loginCO2", "userinfo"),
("loginCO2", "team"),
("menu2","SELECT"), ("SELECT", "note_confirm2"),
("SELECT","folder"), ("SELECT", "note"),
("SELECT","Foldernote_CRUD"), ("Foldernote_CRUD", "folder"),
("Foldernote_CRUD","note"), ("note", "Note_RECEIVE"),
("note_confirm2","Note_RECEIVE")])

def node_subst_cost(node1, node2):
return 1

def node_ins_cost(node):
if node["attribute"] == "control":
return 3
elif node["attribute"] == "boundary":
return 2
elif node["attribute"] == "entity":
return 2
else:
return 1

def node_del_cost(node):
if node["attribute"] == "control":
return 3
elif node["attribute"] == "boundary":
return 2
elif node["attribute"] == "entity":
return 2
else:
return 1
nx.graph_edit_distance(G1, G2,
node_subst_cost=node_subst_cost,
node_del_cost=node_del_cost,
node_ins_cost=node_ins_cost)

[fixk]

エラーメッセージに書いてありますように、nodeに"attribute"というkeyがない為にエラーが出ています。
今回の場合であれば、G1に("Customer", "risyu_confirm2")という辺を追加していますが、"risyu_confirm2"はG1.add_nodes_from()でノードを追加する際に引数に渡しておらず"attribute"を持っていないのでエラーが出ます。
エラーメッセージやトレースバックを見ることで解決できるエラーもたくさんあるので、まずはエラーメッセージをよく読むことをおすすめします。

[TKng1998]

ありがとうございます．
今後はエラーメッセージをよく読むようにします．
助かりました．

Answer 2

削除、置換、作成が行われる際の重みづけをできるようにする。
（普段は削除は１、置換は1、作成は１だと思いますが、costを増やしたいです。）

とありますが、ドキュメントには

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.

と記載されており、デフォルトでは削除、追加はコスト1、置換はコスト0のようです。
また、ドキュメントに書いてありますように、node_subst_cost, node_del_cost, node_ins_costが受け取るのはcallableなオブジェクトです。callableとは関数などのように()をつけて呼び出せるものです。ですので引数としてcallableなオブジェクトを渡してあげれば良いです。
具体的には、一律でcostを変えるのであれば無名関数を使って、下記のように書くか

nx.graph_edit_distance(G1, G2,
                       node_subst_cost=lambda node1, node2:1,
                       node_del_cost=lambda node:2,
                       node_ins_cost=lambda node:2)

事前に関数を定義して以下のように書くことができます。

def node_subst_cost(node1, node2):
    return 1

def node_del_cost(node):
    return 2

def node_ins_cost(node):
    return 2

nx.graph_edit_distance(G1, G2,
                       node_subst_cost=node_subst_cost,
                       node_del_cost=node_del_cost,
                       node_ins_cost=node_ins_cost)

また、nodeの属性によって柔軟にコストを変えたい場合（以下の例ではG1からG2への変換についてG2のM3 nodeを追加またはM3 nodeに置換する場合のコストを大きくしたい場合を考えています）、以下のように書くことができます。

def node_subst_cost(node1, node2):
    if node2["attribute"] == "M3":
        return 100
    else:
        return 1

def node_del_cost(node):
    return 2

def node_ins_cost(node):
    if node["attribute"] == "M3":
        return 100
    else:
        return 2

nx.graph_edit_distance(G1, G2,
                       node_subst_cost=node_subst_cost,
                       node_del_cost=node_del_cost,
                       node_ins_cost=node_ins_cost)

Comments

[TKng1998]

・1,2つ目に書いてある置換のコードの
python
nx.graph_edit_distance(G1, G2,
node_subst_cost=lambda node1, node2:1,

def node_subst_cost(node1, node2):
return 1
と書いてあるnode1,node2というのは
G1のノード全て→node1,G2のノード全て→node2という形で自動的に対応するのでしょうか？
・また１、２つ目のGEDの結果が７と出るのですが、自分の想像では７ではなく、ノードの追加２とエッジの追加１で３かと思ったのですが、なぜ７になるのでしょうか？
（予想）→GEDはグラフの名前（R0RやC1など）を合わせることもしっかり考えているということでしょうか？それであれば挿入（４回する）で結果は７になります。

・エッジも同じようにしたい場合はノードと同じように

nx.graph_edit_distance(G1, G2,
edge_subst_cost=lambda node1, edge2:1,
edge_del_cost=lambda edge:2,
edge_ins_cost=lambda edge:2)
これだと６になります。
これは自分で計算すると７ではないか？と思うのですが、違うのでしょうか？

[fixk]

> G1のノード全て→node1,G2のノード全て→node2という形で自動的に対応するのでしょうか？
おっしゃる通りです。ドキュメントにも
> 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]).
と書かれており、第一引数にはG1のnodeが、第二引数にはG2のnodeが渡されることがお分かりいただけるかと思います。

> また１、２つ目のGEDの結果が７と出るのですが、自分の想像では７ではなく、ノードの追加２とエッジの追加１で３かと思った> のですが、なぜ７になるのでしょうか？
> （予想）→GEDはグラフの名前（R0RやC1など）を合わせることもしっかり考えているということでしょうか？それであれば挿入（４回する）で結果は７になります。
おおむねおっしゃる通りです。nodeの名前を考えないのはデフォルトのnode_subst_costが0の場合で、挿入？はわかりませんが、置換のコストを0から1にしているので、名前を合わせる分のコストが+4されています。

> これだと６になります。
> これは自分で計算すると７ではないか？と思うのですが、違うのでしょうか？
どういった計算をされたのかがわからないので、計算のどこが誤っているかは分かりませんが、一例として
・G1に"M3"を追加（コスト1）
・G1の"M2"を"S2"に置換（コスト0）
・G1の"S2"と"M3"を繋ぐ辺を追加（コスト2）
・G1の"Owner1"を"C1"に、"M1"を"S1"に、"R0"を"R0R"にそれぞれ置換（コスト0）
・G1の"Owner1"と"M1"を繋ぐ辺を"C1"と"S1"を繋ぐ辺に置換（コスト1）
・G1の"M1"と"M2"を繋ぐ辺を"S1"と"S2"を繋ぐ辺に置換（コスト1）
・G1の"Owner1"と"R0"を繋ぐ辺を"C1"と"R0R"を繋ぐ辺に置換（コスト1）
以上より合計のコストは6になります。
どのような編集をすることで該当のグラフ編集距離を達成することができるかはoptimal_edit_paths関数を使うことでも確認することができます。
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.similarity.optimal_edit_paths.html#networkx.algorithms.similarity.optimal_edit_paths

[TKng1998]

ありがとうございます。
とてもわかりやすい回答をありがとうございます。
最後の質問なのですが、グラフ編集距離のどのような編集を達成することができるかについてのoptimal_edit_paths関数は最短距離の編集だけを表示してますよね？
簡単な距離だけでもこのように長いので読みづらくて、、

([([('Owner1', 'C1'), ('M1', 'S1'), ('M2', 'S2'), ('R0', 'R0R'), (None, 'M3')], [(('Owner1', 'M1'), ('C1', 'S1')), (('M1', 'M2'), ('S1', 'S2')), (('Owner1', 'R0'), ('C1', 'R0R')), (None, ('S2', 'M3'))]), ([('M1', 'C1'), ('Owner1', 'S1'), ('R0', 'S2'), ('M2', 'R0R'), (None, 'M3')], [(('Owner1', 'M1'), ('C1', 'S1')), (('Owner1', 'R0'), ('S1', 'S2')), (('M1', 'M2'), ('C1', 'R0R')), (None, ('S2', 'M3'))]), ([('M2', 'C1'), ('M1', 'S1'), ('Owner1', 'S2'), (None, 'R0R'), ('R0', 'M3')], [(('M1', 'M2'), ('C1', 'S1')), (('Owner1', 'M1'), ('S1', 'S2')), (None, ('C1', 'R0R')), (('Owner1', 'R0'), ('S2', 'M3'))]), ([('R0', 'C1'), ('Owner1', 'S1'), ('M1', 'S2'), (None, 'R0R'), ('M2', 'M3')], [(('Owner1', 'R0'), ('C1', 'S1')), (('Owner1', 'M1'), ('S1', 'S2')), (None, ('C1', 'R0R')), (('M1', 'M2'), ('S2', 'M3'))])], 2.0)

[fixk]

> 最後の質問なのですが、グラフ編集距離のどのような編集を達成することができるかについてのoptimal_edit_paths関数は最短距離の編集だけを表示してますよね？
おっしゃる通りです。ドキュメントにも
> Returns all minimum-cost edit paths transforming G1 to G2.
と記載があり、最小コストの編集のみを表示しています。ここで気を付けていただきたいことは、最小コストの編集は必ずしも一通りではありません。Returns "all" minimum-costとありますように、最小コストを達成する編集は複数ある場合はそれらの編集の全てが戻り値になります。
戻り値としては、2つの要素のtupleが返されます。tupleのindex=0の要素は編集そのもので、index=1の要素は最小コストです。
編集の部分は読みづらいですが、分解してみると多少は読みやすくなります。編集の部分は編集をtupleでまとめたリストになっており、
[(最小コストを達成する編集1個目), (最小コストを達成する編集2個目), (最小コストを達成する編集3個目), ..., (最小コストを達成する編集n個目)]
といった構造です。
それぞれの編集を見ていきます。例えば最小コストを達成する編集1個目のtupleは
([(nodeの編集1個目), (nodeの編集2個目), ..., (nodeの編集m個目)],
[(edgeの編集1個目), (edgeの編集2個目), ..., (edgeの編集k個目)])
といった構造になっています。
添付していただいた例で個人的にわかりやすく分解してみたので参考にしていただければ幸いです。

(
[# 編集のリストの開始
(# 最小コストを達成する編集1個目の開始
[ # 編集1個目のnodeの編集についてのリスト
('Owner1', 'C1'), # "Owner1"を"C1"に置換
('M1', 'S1'),
('M2', 'S2'),
('R0', 'R0R'),
(None, 'M3') # "M3"nodeを追加
],
[ # 編集1個目のedgeの編集についてのリスト
(('Owner1', 'M1'), ('C1', 'S1')), # "Owner1"と"M1"を繋ぐ辺を"C1"と"S1"を繋ぐ辺に置換
(('M1', 'M2'), ('S1', 'S2')),
('Owner1', 'R0'), ('C1', 'R0R')),
(None, ('S2', 'M3')) # "S2"と"M3"を繋ぐ辺を追加
]
), # 最小コストを達成する編集1個目の終了

(# 最小コストを達成する編集2個目の開始
[ # 編集2個目のnodeの編集についてのリスト
('M1', 'C1'),
('Owner1', 'S1'),
('R0', 'S2'),
('M2', 'R0R'),
(None, 'M3')
],
[ # 編集2個目のedgeの編集についてのリスト
(('Owner1', 'M1'), ('C1', 'S1')),
(('Owner1', 'R0'), ('S1', 'S2')),
(('M1', 'M2'), ('C1', 'R0R')),
(None, ('S2', 'M3'))
]
), # 最小コストを達成する編集2個目の終了

(# 最小コストを達成する編集3個目の開始
[ # 編集3個目のnodeの編集についてのリスト
('M2', 'C1'),
('M1', 'S1'),
('Owner1', 'S2'),
(None, 'R0R'),
('R0', 'M3')
],
[ # 編集3個目のedgeの編集についてのリスト
(('M1', 'M2'), ('C1', 'S1')),
(('Owner1', 'M1'), ('S1', 'S2')),
(None, ('C1', 'R0R')),
(('Owner1', 'R0'), ('S2', 'M3'))
]
), # 最小コストを達成する編集3個目の終了

(# 最小コストを達成する編集4個目の開始
[ # 編集4個目のnodeの編集についてのリスト
('R0', 'C1'),
('Owner1', 'S1'),
('M1', 'S2'),
(None, 'R0R'),
('M2', 'M3')
],
[ # 編集4個目のedgeの編集についてのリスト
(('Owner1', 'R0'), ('C1', 'S1')),
(('Owner1', 'M1'), ('S1', 'S2')),
(None, ('C1', 'R0R')),
(('M1', 'M2'), ('S2', 'M3'))
]
) # 最小コストを達成する編集4個目の終了
], #編集のリストの終了
2.0 # 最小コスト
)