プログラミングコンテストチャレンジブックの二部グラフ判定をpythonで

2017年3月12日プログラミング, python

懐かしくて思わず買ってしまいました。プログラミングなんて無縁の生活を送っているのに、なんで理系本買ってるんだかっていうね!

しかもソースコードC++\(^o^)/ C言語やったことあるから平気かな~と思ってましたがダメでした。「vectorって何や/(^o^)\」な状態。

1年ぶりにプログラミングをやってみようかと思ってpythonを調べてみたら、pythonのグラフ理論はnetworkxっていうモジュールを使うのが主流みたい。

しかし、モジュールを使ってしまったらアルゴリズムのお勉強にならないので、書籍通りに書いてみます。

書籍だと、グローバル変数を使ってる部分が端折られていてわかりにくい面があるので、コピペオンリーで実際に動くものを書いてみます。また、書籍がせっかくCっぽく書いてくれてるみたいなので、似たようなところはそのままにします。

# -*- coding:utf-8 -*-
def dfs(v, c):
    '''
    深さ優先探索を利用して、ノードvに色c(1 or -1)を塗っていく関数。
    隣接ノードと異なる色が塗れなくなったらFalseを返す。
    '''
    color[v] = c;
    for i in range(len(G[v])):
        if color[G[v][i]] == c:
            return False
        if color[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False
    return True

def solve():
    '''二部グラフ判定p93を解く。
    隣接ノード同士がすべて異なる色でぬれたらYes
    塗れなかったらNo を返す'''
    for i in range(V):
        if color[i] == 0:
            if not dfs(i, 1):
                print "No!"
                return
    print "Yes"


#グラフ作る部分はとりあえず手動で


if __name__ == "__main__":
    #例1
    ##V = 3   #ノードの数
    ##E = 6   #エッジの数(無向グラフは2本 per エッジ)
    ##G = {0:[1,2],1:[0,2],2:[0,1]} #隣接リスト

    #例2
    V = 4
    E = 8
    G = {0:[1,3],1:[0,2],2:[1,3],3:[0,2]}

    #color[i]:ノードi(0<= i <= V)につける色
    #V = 2 -> color = {0:0, 1:0}
    #V = 4 -> color = {0:0, 1:0, 2:0, 3:0}
    color_key = range(V)
    color_initvalue = [0 for x in range(V)]
    color = dict(zip(color_key, color_initvalue))

    solve()
    print color

以前はnumpy使ってガンガン計算していたのに、プログラミングを久しくやっていないと基本的なメソッドすら忘れすぎてて自分で笑っちゃうくらいでした…。リストやディクショナリどころか、for文の文法の使い方すら忘れてたという…w

できるだけ書籍通りにやろうと思って、グローバル変数使ってるところはグローバル変数使う方針。

グラフの実装部分は、書籍でも人間がいちいち作るプログラムサンプルだったので、このコードでは一先ず予め入力させることにしました。

グラフの隣接リストをpythonでどう実装しようかなぁって迷ったんですが、できるだけ書籍とアルゴリズムを変えたくなかったので、以下のように、ディクショナリのなかにリストを入れる形にしました。

G = {0:[1,2], 1:[2,3] }

pythonのリストを使ってしまうと、temp = []; temp[0] = 1;みたいな感じだとエラー起きちゃうんですよね。リストは要素がないところへアクセスすることができないようでして、書籍とほぼ同じように実装するならディクショナリの方が相性が良さそうです。

変数colorをディクショナリで最初に用意して、初期値0を代入してるのも同じ感じの理由です。

pythonの「networkxモジュールはどうやって実装してるんだ?」と気になって、Graphクラスのコードを読んでみたところ、例えば今回の変数G

G = {0:[1,2],1:[0,2],2:[0,1]}

は以下のような形でディクショナリで実装されていました。

G = {0:{1:{},2:{}},
     1:{0:{},2:{}},
     2:{0:{},1:{}}}

一応networkxモジュールを読むと、コンストラクタでself.adj={}で初期化されて、この変数に隣接リストが作られてるようです。書籍のグラフ作成サンプルはp92に書かれているのですが、このモジュールを使って近いことをするのなら、以下みたいな感じかな?

# -*- coding:utf-8 -*-
import networkx as nx
G = nx.Graph()
G.add_edge(0,1)
G.add_edge(0,2)

G.add_edge(1,2)
G.add_edge(1,2)

G.add_edge(2,0)
G.add_edge(2,1)

#隣接リストがどのようにできてるかチェック
print G.adj #ディクショナリのまま
print nx.to_dict_of_lists(G) #リストの形式に変換

出力をチェックしてみると、G.adjの方は以下

{0: {1: {}, 2: {}}, 1: {0: {}, 2: {}}, 2: {0: {}, 1: {}}}

to_dict_of_list形式だと、以下出力です。

{0: [1, 2], 1: [0, 2], 2: [0, 1]}

self.adjはモロに内部の変数なので直接使うのはよろしくないかもですね…。networkxにあるコードはそんな難しくなくて理解することができたので、もうグラフ作る部分は自分でやらずにnetworkx使ってしまっていいかな~。

とりあえずto_dict_of_listのエイリアスを変数に貼れば同じコードで通りそうなので、グラフ作る部分でnetworkxを軽めに使ったものを置いておきます。

# -*- coding:utf-8 -*-
import networkx as nx
import matplotlib.pyplot as plt

def dfs(v, c):
    '''
    深さ優先探索を利用して、ノードvに色c(1 or -1)を塗っていく関数。
    隣接ノードと異なる色が塗れなくなったらFalseを返す。
    '''
    color[v] = c;
    for i in range(len(G[v])):
        if color[G[v][i]] == c:
            return False
        if color[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False
    return True

def solve():
    '''二部グラフ判定p93を解く。
    隣接ノード同士がすべて異なる色でぬれたらYes
    塗れなかったらNo を返す'''
    for i in range(V):
        if color[i] == 0:
            if not dfs(i, 1):
                print "No!"
                return
    print "Yes"


if __name__ == "__main__":

    #ランダムネットワーク(二項分布の確率)でグラフを作る
    V = 4 #ノード数
    tmpG = nx.binomial_graph(V,0.4) #グラフ
    E = tmpG.size() * 2 #エッジ数
    G = nx.to_dict_of_lists(tmpG) #計算に使うためlistにする

    #color[i]:ノードi(0<= i <= V)につける色
    #V = 2 -> color = {0:0, 1:0}
    #V = 4 -> color = {0:0, 1:0, 2:0, 3:0}
    color_key = range(V)
    color_initvalue = [0 for x in range(V)]
    color = dict(zip(color_key, color_initvalue))

    #二部グラフ判定をする
    solve()
    print color

    #plot
    nx.draw(tmpG)
    plt.show()

networkxのドキュメントを読んでみたところ、案の定Generatorが用意されていまして、二項分布でエッジを貼る関数があったのでこれ使って無向グラフ作りました。

ランダムでグラフを作ったので、どんなグラフが表示させたいな~と思ってドキュメントみてたら、draw()関数で簡単にいけるみたいなので、ついでに表示させてみました。

matplotlib(とnumpy)というモジュールを入れてないと使えないっぽいです。これで V = 1000の時も一応実験できますね。この場合draw()してもわけわからんくなると思いますがw

二部グラフ系のアルゴリズムもBipartiteというヤツが用意されているので、自分でわざわざ書かなくてもたぶんココにありそうですね。

線形代数で使うグラフラプラシアンをnumpy使って返す関数とかもありました。線形代数系のグラフはそこまで充実してないみたいだけれど、結構ちゃんとしているライブラリ。

なんか… もう一回コード見なおしてみても、やっぱりグローバル変数使ってるコードってすごく気持ち悪いというか読みにくいですね…。

 

勢いでBellman Ford法もpythonでやってみました。
https://yutorinote.com/python-bellman-ford/