networkxにおける条件に合う頂点の削除

課題

プログラム内で定義したグラフから条件に合う頂点を削除しよう！

今回の条件

• networkxを利用する
• グラフはプログラム内で定義する
• 辺が一つしかない不安定な状況をなくす

最初に考えたプログラム

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
G.add_edges_from([(1,2),(2,4),(3,2),(4,5),(6,10),(7,6),(8,6),(9,8),(10,8),(1,9),(8,1)])

#n=G.number_of_nodes()
#[次数が0の頂点]もしくは[次数が1の頂点とその頂点に接続する辺]を削除する
for v in G:
    #print(G.degree(v))
    #print("v=",v)
    G_deg=G.degree(v)
    if G_deg==0 or G_deg==1:
        G.remove_node(v)
        #print("G_deg=",G_deg)


#グラフの出力
nx.draw_networkx(G)
plt.show()

よしできたと思い実行してみました。

エラー

Traceback (most recent call last):
  File "remove.py", line 10, in <module>
    for v in G:
RuntimeError: dictionary changed size during iteration

一筋縄ではいかず。。。
原因を探るためネットで調べてみました。

原因1

まずエラーの意味は,「iterate しているオブジェクトを変更することはできない」というエラーだそうです。
つまり、for v in G:でループを回しながらの削除はできないということなのでしょうか。

改良1

for v in G内で削除ができないのなら、条件にあう頂点をリストアップしてからfor v in Gの外で一気に削除してしまおうと考えました。

改良1のプログラム

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
G.add_edges_from([(1,2),(2,4),(3,2),(4,5),(6,10),(7,6),(8,6),(9,8),(10,8),(1,9),(8,1)])

node_be=G.number_of_nodes() #削除前の頂点数
edge_be=G.number_of_edges() #削除前の辺数

#[次数が0の頂点]もしくは[次数が1の頂点とその頂点に接続する辺]を削除する
G_rem=[]
#条件に合う頂点をリストアップする
for v in G:
    G_deg=G.degree(v)
    #print("G_deg[",v,"]=",G_deg)
    if G_deg<=1:
       #print("v=",v)
       G_rem.append(v)

#条件に合う頂点を削除する
G.remove_nodes_from(G_rem)

node_af=G.number_of_nodes() #削除後の頂点数
edge_af=G.number_of_edges() #削除後の辺数

#グラフの出力
nx.draw_networkx(G)
plt.show()

これで実行してみました。

実行したグラフ

\\次数が1の頂点が残っている///

原因2

for v in G:で一回見ただけでvはどんどん大きくなって次数が1になってもスルーしてしまっているみたいです。つまり、一回やって終わりではだめで何回も見返さなくてはならないのです！

改良2

for v in G:を何回も繰り返すために2重ループをしてみることにしました。
頂点数分だけ何回もforを回してみます。

改良したプログラム

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
G.add_edges_from([(1,2),(2,4),(3,2),(4,5),(6,10),(7,6),(8,6),(9,8),(10,8),(1,9),(8,1)])

node_be=G.number_of_nodes() #削除前の頂点数
edge_be=G.number_of_edges() #削除前の辺数

#[次数が0の頂点]もしくは[次数が1の頂点とその頂点に接続する辺]を削除する
G_rem=[]
#条件に合う頂点をリストアップする
for i in range(node_be):
    for v in G:
        G_deg=G.degree(v)
        #print("G_deg[",v,"]=",G_deg)
        if G_deg<=1:
            #print("v=",v)
            G_rem.append(v)
    #条件に合う頂点を削除する
    G.remove_nodes_from(G_rem)

node_af=G.number_of_nodes() #削除後の頂点数
edge_af=G.number_of_edges() #削除後の辺数

#グラフの出力
nx.draw_networkx(G)
plt.savefig("output.png")
plt.show()

実行したグラフ

次数1の頂点はなくなりました！

最後に

いろいろ段階を踏まなくては簡単に頂点が削除できないことがわかりました。
最後までありがとうございました。