NetworkX

複雑ネットワークを解析するためのグラフアルゴリズムなどをまとめたPythonのパッケージNetworkXを使ってみた．
とりあえずNewmanのサイトからとってこれる，空手クラブのネットワークデータを読み込んで,Girvan-Newman algorithmにより，グラフがコミュニティに分かれていく様子を描画するプログラムを作ってみた.

import networkx as NX
import networkx.readwrite.gml as NRG
import networkx.centrality as NC
import pylab as P

def updateGraph(G):
  ebc = NC.edge_betweenness(G)
  max = 0
  medge = None
  for k , v in ebc.iteritems():
    if max < v :
      medge , max = k , v 
  G.delete_edge(medge)
  return G

def drawGraph(G ,pos, output):
  NX.draw(G ,pos)
  P.savefig(output)
  P.draw()
  P.close()

G = NRG.read_gml("karate.gml")
eNum = G.number_of_edges()
pos = NX.spring_layout(G)
for i in range(eNum):
  output = "img/karate%(id)02d.png" % {"id": i}
  drawGraph(G , pos,output)
  updateGraph(G)

生成したpngファイルをimagemagickでアニメーションgifにしたもの

make -j

GNU makeでmake -j [jobs]とオプションをつけると並列にビルドを行ってくれる．
cf: http://www.gnu.org/software/make/manual/html_node/Parallel.html#Parallel

テスト

入出力が公開されたので，前書いたのをテストしてみる．A,B,C,D,F,Hは一発で通る．Gはゴーストが1体しかいない盤面のときに交換チェックをするというバグがあってそれをとったら通った，実行時間は45秒ぐらい．Iはランダムっぽいデータだと正しい答えが出るんだけど，極端につぶれたような図形に対して精度がでないので保留．

CUDAインストール

研究室のPCにhttp://developer.nvidia.com/object/cuda.html:CUDAをインストールして走らせてみる．インストール時に手間取ったのはNVIDIA Linux display driverをインストールするところでXを止めてくださいとかいわれて止め方が分からず困ったんだけどinit3とかうてば止まるらしい．

とりあえず粒子数が65536のときのN体問題のコードを走らせたところ，CPU上だと83.2秒でGeForce 8600GTのほうだと1.6秒だった．大体50倍ぐらいの高速化が見込める．(本当はQuad Coreなので本来の1/4しかつかってないので，実際は10倍強ぐらい)