pythonで自前のグラフ構造のクラスとその描画を作る
AtCoderのABC160のDで出題されたグラフの問題が解けなかったので、pythonの勉強がてらグラフ構造のクラスとそれをmaatplotlibで描画をやってみました。
（AtCoderに参加してみて反省）
AtCoder初参加で覚えていたらよかったと思ったコード（次回への反省１）
グラフ構造を表現するライブラリにはNetworkXがあるようだが、今回は使用しない。
（そもそもAtCoderでは使えない？）
スマートな表現方法はたくさんあるだろうが、
素人がざっと考えてできる範囲での実装なので、作り込めていないのはご容赦ください。
グラフ構造のクラス
構想
クラスにはノードをキーとして、そのエッジの先をバリューとして持つ辞書をメンバ変数として持つこととする。
メソッドとしては、以下のものを準備する。
①ノードを追加する
②エッジの追加する
③ノードの表示する
④ノードをリストとして返す
⑤指定ノードにつながるノードを返す
クラスの定義
#グラフ構造の作成
class cglaph():
def __init__(self):
#ノードの初期化
self.nodes={}
def addnode(self,num):#①ノードを追加
for i in self.nodes.keys():
if i==num:
return(False)
else:
self.nodes[num]=list()
return(True)
def addedge(self,ag1,ag2):#②エッジを追加
node1=min(ag1,ag2)
node2=max(ag1,ag2)
addok=False
for i in self.nodes.keys():
if i==node1:
for j in self.nodes.keys():
if j==node2:
addok=True
if addok:
self.nodes[node1].append(node2)
self.nodes[node2].append(node1)
def printnodes(self): #③ノードを表示
print("■Glaph:")
print("vertice:neighbors")
for k,v in self.nodes.items():
print(k,":",v)
def getnodes(self):#④ノードのリストを返す
keylist=list()
for i in self.nodes.keys():
keylist.append(i)
return keylist
def getedge(self, node):#⑤指定ノードのエッジ（つながっているノード）を返す。
return self.nodes[node]
適当に５つのノードを繋いだ無向グラフを実際作ってみる
G=cglaph()
G.addnode(1)#ノードの追加
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#エッジの追加
G.addedge(1,4)
G.addedge(5,3)
G.printnodes()#ノードの一覧表示
nodelist=G.getnodes()#ノードリストを取得
print ("NODE LIST:",nodelist)
G.getedge(1)#ノード１とつながっているノード
作ったグラフ構造の可視化
matplotlibのお勉強がてら、作ったグラフを可視化してみる。
ノードの描画位置をどうしたら良いのがわからなかったため、
ランダムな位置にノードを配置することとした。
今後いい感じの位置に配置できるやり方を考えてみたい。
※そもそもNetworkXとmatplotlibを使えば手をかける必要はないようですが。
import matplotlib.pyplot as plt
import random
random.seed(0)
#ノード位置はどうしたら良いのかわからないため、ランダム
N=len(nodelist)
x=[random.randint(0, 100) for i in range(N)]
y=[random.randint(0, 100) for i in range(N)]
print("x:",x)
print("y:",y)
#グラフ作成
plt.figure(1)
#ノード描画
plt.scatter(x,y)
#ノード位置にノード名を付ける
ax=plt.axes()
for i in range(N):
ax.annotate(nodelist[i],(x[i],y[i]),size=20)
#エッジを描画 ここがスマートじゃない
for i in range(N):
edges=G.getedge(i+1)
for j in edges:
plt.plot((x[i],x[j-1]),(y[i],y[j-1]), color='red')
plt.xlim(0, 100)
plt.ylim(0, 100)
※なんかMatplotlibDeprecationWarningっていうのが出ているけど今は無視。axesの使い方が適切じゃないのかな。
最後に
これからやっと幅優先探索の勉強を始めるぞ！