pythonで自前のグラフ構造のクラスとその描画を作る

#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の使い方が適切じゃないのかな。

#最後に
これからやっと幅優先探索の勉強を始めるぞ！

###参考
[Matplotlib] 注釈と矢印

散布図の各要素に文字を付ける。

Pythonでネットワークを分析・可視化しよう！必要手順まとめ

Pythonの辞書(dict)のforループで要素を取り出す方法