質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
Anaconda

Anacondaは、Python本体とPythonで利用されるライブラリを一括でインストールできるパッケージです。環境構築が容易になるため、Python開発者間ではよく利用されており、商用目的としても利用できます。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

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

TKng1998
TKng1998

総合スコア1

Anaconda

Anacondaは、Python本体とPythonで利用されるライブラリを一括でインストールできるパッケージです。環境構築が容易になるため、Python開発者間ではよく利用されており、商用目的としても利用できます。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

2回答

0グッド

0クリップ

335閲覧

投稿2022/11/11 07:16

編集2022/11/14 05:05

前提

環境[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、置換は1、作成は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

該当のソースコード

python

1import numpy as np 2import networkx as nx 3import scipy as sp 4import matplotlib.pyplot as plt 5 6G1 = nx.Graph() 7G1.add_nodes_from([("Owner1", {"attribute":"Owner1"},{"label":"Owner1"}), 8("M1", {"attribute":"M1"},{"label":"M1"}), 9("M2", {"attribute":"M2"},{"label":"M2"}), 10("R0", {"attribute":"R0"},{"label":"R0"})]) 11G1.add_edges_from([("Owner1","R0"), ("Owner1", "M1"), 12("M1", "M2")]) 13print(G1.nodes()) 14print(G1.edges()) 15nx.nx_agraph.view_pygraphviz(G1, prog='fdp') 16 17G2 = nx.Graph() 18G2.add_nodes_from([("C1", {"attribute":"C1"},{"label":"C1"}), 19("S1", {"attribute":"S1"},{"label":"S1"}), 20("S2", {"attribute":"S2"},{"label":"S2"}), 21("R0R", {"attribute":"R0R"},{"label":"R0R"}), 22("M3", {"attribute":"M3"},{"label":"M3"})]) 23G2.add_edges_from([("C1", "R0R"), 24("S1", "S2"), ("C1", "S1"), 25("M3", "S2")]) 26print(G2.nodes()) 27print(G2.edges()) 28 29nx.nx_agraph.view_pygraphviz(G2, prog='fdp') 30 31nx.graph_edit_distance(G1, G2,node_subst_cost=(G1.nodes[G1], G2.nodes[G2]), node_del_cost=1, node_ins_cost=1)

こちらの2つのグラフのGEDは2です。(作成✖️2[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]

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答2

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 # 最小コスト )

投稿2022/11/17 12:11

fixk

総合スコア70

TKng1998❤️を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

TKng1998

2022/11/17 12:15

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

2023/01/02 17:57

現在、ベストアンサーの最後の文の属性による重み付けの計算をしているのですが、こちらのコードを実行しても結果が出ません。エラーもなく、何が間違っているのかがわからない状態です。 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

2023/01/02 19:02

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

2023/01/06 04:58

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

2023/01/06 08:19

こちらのコードがうまく行きません。 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

2023/01/06 08:45

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

2023/01/06 14:14

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

1

ベストアンサー

削除、置換、作成が行われる際の重みづけをできるようにする。
(普段は削除は1、置換は1、作成は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を変えるのであれば無名関数を使って、下記のように書くか

Python

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

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

Python

1def node_subst_cost(node1, node2): 2 return 1 3 4def node_del_cost(node): 5 return 2 6 7def node_ins_cost(node): 8 return 2 9 10nx.graph_edit_distance(G1, G2, 11 node_subst_cost=node_subst_cost, 12 node_del_cost=node_del_cost, 13 node_ins_cost=node_ins_cost)

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

Python

1def node_subst_cost(node1, node2): 2 if node2["attribute"] == "M3": 3 return 100 4 else: 5 return 1 6 7def node_del_cost(node): 8 return 2 9 10def node_ins_cost(node): 11 if node["attribute"] == "M3": 12 return 100 13 else: 14 return 2 15 16nx.graph_edit_distance(G1, G2, 17 node_subst_cost=node_subst_cost, 18 node_del_cost=node_del_cost, 19 node_ins_cost=node_ins_cost)

投稿2022/11/15 18:48

fixk

総合スコア70

TKng1998👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

TKng1998

2022/11/16 08:01

・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という形で自動的に対応するのでしょうか? ・また1、2つ目のGEDの結果が7と出るのですが、自分の想像では7ではなく、ノードの追加2とエッジの追加1で3かと思ったのですが、なぜ7になるのでしょうか? (予想)→GEDはグラフの名前(R0RやC1など)を合わせることもしっかり考えているということでしょうか?それであれば挿入(4回する)で結果は7になります。 ・エッジも同じようにしたい場合はノードと同じように 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) これだと6になります。 これは自分で計算すると7ではないか?と思うのですが、違うのでしょうか?
fixk

2022/11/16 10:11

> 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が渡されることがお分かりいただけるかと思います。 > また1、2つ目のGEDの結果が7と出るのですが、自分の想像では7ではなく、ノードの追加2とエッジの追加1で3かと思った> のですが、なぜ7になるのでしょうか? > (予想)→GEDはグラフの名前(R0RやC1など)を合わせることもしっかり考えているということでしょうか?それであれば挿入(4回する)で結果は7になります。 おおむねおっしゃる通りです。nodeの名前を考えないのはデフォルトのnode_subst_costが0の場合で、挿入?はわかりませんが、置換のコストを0から1にしているので、名前を合わせる分のコストが+4されています。 > これだと6になります。 > これは自分で計算すると7ではないか?と思うのですが、違うのでしょうか? どういった計算をされたのかがわからないので、計算のどこが誤っているかは分かりませんが、一例として ・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

2022/11/17 09:52

ありがとうございます。 とてもわかりやすい回答をありがとうございます。 最後の質問なのですが、グラフ編集距離のどのような編集を達成することができるかについての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

2022/11/17 12:07

> 最後の質問なのですが、グラフ編集距離のどのような編集を達成することができるかについての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 # 最小コスト )

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Anaconda

Anacondaは、Python本体とPythonで利用されるライブラリを一括でインストールできるパッケージです。環境構築が容易になるため、Python開発者間ではよく利用されており、商用目的としても利用できます。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。