Help us understand the problem. What is going on with this article?

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

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

AtCoderのABC160のDで出題されたグラフの問題が解けなかったので、pythonの勉強がてらグラフ構造のクラスとそれをmaatplotlibで描画をやってみました。

(AtCoderに参加してみて反省)
AtCoder初参加で覚えていたらよかったと思ったコード(次回への反省1)

グラフ構造を表現するライブラリには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]

適当に5つのノードを繋いだ無向グラフを実際作ってみる

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)#ノード1とつながっているノード

cap1.PNG

作ったグラフ構造の可視化

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)

cap2.PNG

※なんかMatplotlibDeprecationWarningっていうのが出ているけど今は無視。axesの使い方が適切じゃないのかな。

最後に

これからやっと幅優先探索の勉強を始めるぞ!

参考

[Matplotlib] 注釈と矢印

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

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

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

HAOPI
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした