FLATzブログ

［FLATzブログ］の記事一覧

モテるアルゴリズム講座　 第1回 グラフでモテたい

2010年03月05日（金）15:00｜amakata｜FLATzブログ, アルゴリズム, 技術情報｜ このエントリをdel.icio.usに追加このエントリをはてなブックマークに追加

天方です。


今日からモテるアルゴリズム講座を始めたいと思います。


それでは、第1回グラフでモテたいの講義を始めようと思います。
なんといってもアルゴリズムができるとかいうと、いろいろモテます。
この講座を通じて、皆さんもアルゴリズムをマスターしてモテてください。


本日は、モテるアルゴリズムを考える上で重要な
グラフのデータ構造について話をしたいと思います。


グラフというと、普通思い浮かべるのは棒グラフとか円グラフとかかもしれませんが、今回は違います。そんな反応をしていると婚期を逃します。


グラフというのは、点と枝かつながってできるものをグラフと言います。


グラフの例

グラフの例



グラフはいろいろな分野で使われていると思いますが、
あのGoogleも検索エンジンのページの順位付けのためにグラフの概念を利用していたいりします。


さて、グラフをコンピュータ上で扱おうとすると、そのデータ構造の持たせ方に悩みます。
グラフ用のライブラリを使えばそれほど大変でもないのですが、やはり自分で書いた方がモテます。


グラフをデータとして表現するにはいくつか方法があります。
では、上記の図で示したグラフをさまざまなデータ構造で表現してみようと思います。


まず、上の図の点と枝を数学的な表現を使って次のように表現することにします。


点の集合 V=\{v_1,v_2,v_3,v_4,v_5,v_6\}


枝の集合 E=\{e_1,e_2,e_3,e_4,e_5,e_6,e_7,e_8,e_9,e_{10}\}


その場合、点と枝の接続関係は次のようになります。


枝, 始点, 終点
e_1,v_1,v_2\\e_2,v_2,v_4\\e_3,v_3,v_4\\e_4,v_4,v_5\\e_5,v_5,v_6\\e_6,v_6,v_1\\e_7,v_1,v_3\\e_8,v_5,v_2\\e_9,v_3,v_6\\e_{10},v_1,v_1


ちなみに、向きがある枝でできたグラフを有向グラフと呼びます。
向きがない枝でできたグラフを無向グラフと呼びます。


こういったグラフを表現するデータ構造としては、枝の始点と終点の番号の組を持たせることでグラフを表現する方法があります。


それではこのグラフのデータ構造をRubyをつかって表現してみましょう。


例えば、上記の視点と終点をRubyの配列で表現すると下記のようになります。


start_vertex = [1,2,3,4,5,6,1,5,3,1]
end_vertex = [2,4,4,5,6,1,3,2,6,1]


これは、さきほど示した数学的な表現だと下記のような表現になります。
start\_vertex=[v_1,v_2,v_3,v_4,v_5,v_6,v_1,v_5,v_3,v_1]\\end\_vertex=[v_2,v_4,v_4,v_5,v_6,v_1,v_3,v_2,v_6,v_1] … ①


配列の添え字が、枝の添え字 – 1になります。


頂点間に枝があるかどうかを調べるには
頂点数をnとするとO(n)の計算量(時間的)がかかります。
また、計算量(空間的)は枝数をmとすると2mです。


そこで、各頂点毎に、出入りする枝を持つという手があります。


たとえば、下記の様な図のように一つの頂点に出入りする枝に注目します。


頂点v1に入る枝と出る枝の例

頂点v1に入る枝と出る枝の例



これはRubyで表現すると下記のようになります。


start_edge = [[1, 7, 10], [2], [3, 9], [4], [5, 8], [6]]
end_edge = [[6, 10], [1, 8], [7], [2, 3], [4], [5, 9]]


数学的な表現では下記のようになります。
start\_edge=[[e_1,e_7,e_{10}],[e_2],[e_3,e_9],[e_4],[e_5,e_8],[e_6]]\\end\_edge=[[e_6,e_{10}],[e_1,e_8],[e_7],[e_2,e_3],[e_4],[e_5,e_9]] … ②


これで、頂点と枝の両方から検索ができるデータ構造ができました。ここモテます。
でも、もうすこしハイクラスのモテを期待したい場合は、クラスを利用したほうがいいと思います。


さて、配列でグラフを表現できるとからモテモテだと思っていい気になってはいけません。
やはりグラフを表現する場合にもTPOがあります。
例えば、他のラフの表現方法としては、接続行列を使う方法もあります。


接続行列 M=\left\(<br /> \begin{array}{ccc}<br /> 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0\<br /> -1 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0\<br /> 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & 1 & 0\<br /> 0 & -1 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\<br /> 0 & 0 & 0 & -1 & 1 & 0 & 0 & 1 & 0 & 0\<br /> 0 & 0 & 0 & 0 &-1 & 1 & 0 & 0 & -1 & 0\<br /> \end{array}<br /> \right) … ③


縦の座標が頂点の添え字、横の座標が枝の添え字に対応し、
要素が1であれば、その頂点を始点、要素が-1であれば、その頂点を終点とすることを表現しています。
この場合、計算量(空間的)はnmです。頂点間に枝があるかを調べる計算量(時間的)はO(m)です。
ちなみに、接続行列だと、自己ループしている枝を表すことができません。
そういえば、さきほどの配列を用いた、枝の始点と終点の番号の組のデータ構造だと、枝がない頂点を表現できません。
そこらへんについて、「ちょっときみ、そのデータ構造だと、自己ループが表現できないので、今回の案件には使わない方がいいと思うよ」と
それとなく耳打ちできるとそれとなくモテます。


他に隣接行列で表現する方法もあります。


隣接行列 A=\left\(<br /> \begin{array}{ccc}<br /> 1 & 1 & 1 & 0 & 0 & 0 \<br /> 0 & 1 & 0 & 0 & 0 & 0 \<br /> 0 & 0 & 0 & 1 & 0 & 1 \<br /> 0 & 0 & 0 & 0 & 1 & 0 \<br /> 0 & 1 & 0 & 0 & 0 & 1 \<br /> 1 & 0 & 0 & 0 & 0 & 0 \<br /> \end{array}<br /> \right) … ④


これは、縦の座標を始点の頂点の添え字に対応させ、横の座標を終点の頂点の添え字に対応させて表現したもので、1なら接続している、0なら接続していないという表現です。この場合、計算量(空間的)はn^2です。頂点間に枝があるかを調べる計算量(時間的)はO(1)です。
みなさん、もうお気づきとは思いますが、隣接行列では、同じ始点、終点をもつ複数の枝を表すことができなくなります。


さて、４種類ほど表現方法を扱いましたが、それぞれの表現では、表現できるパターンの制約や、グラフを参照、更新する場合の計算量（時間的、空間的）などが違います。
シチュエーションや、相手の好みによって、表現方法を変えるとモテまくります。


みなさんもグラフでモテてみませんか？

続きを読む

第1回プログラマーズカフェナイト＠原宿 を開催しました！

2010年03月02日（火）14:30｜hisasue｜FLATzブログ｜ このエントリをdel.icio.usに追加このエントリをはてなブックマークに追加

久末です。


先日(2月22日)、プログラマーズカフェナイト@原宿というイベントを弊社で行いました。



今回はLTをメインに行いました。


プログラマーズカフェナイトの様子

プログラマーズカフェナイトの様子 Photo by 三鷹PGカフェ



さて、今回のLT発表者は以下の方々です。


プログラマーズカフェナイト – 紅茶屋くいっぱのあれこれ日記


webプログラマが楽にiPhoneアプリを開発する方法
@jishiha


3分でできるGoogle App Engine
@bluerabbit777jp


ExtJS & HTML5
@Tommy1969


お手軽 GoogleAppEngine / Java + slim3
404 shin1のつぶやき ないわー Not Found: 第１回プログラマーズカフェナイト＠原宿に参加した #pgcafe
@shin1ogawa


ギークハウスの話
@youchan


月曜日にもかかわらず40名募集のところに47名ほどの応募があり、最終的には30名程度、Ustreamの試聴が30名を超えるイベントになりました。


LT発表者のみなさん、参加者のみなさん、お手伝いのみなさん、ありがとうございます。


三鷹プログラマーズカフェとは？


プログラマーズカフェナイトは三鷹プログラマーズカフェの派生イベントと述べましたが、
三鷹プログラマーズカフェをご存じない方のために簡単にご紹介を。


三鷹プログラマーズカフェは、毎週木曜日、15〜18時に、三鷹産業プラザ地下1階で開催しているイベントです。
プログラマ(とは限らないのですが)が集まって話ができる「場」を提供しています。


プログラマーズカフェは会話が主体で、勉強会やセミナーと違って特定の目的がありません。
ですから、


  • 自分で作ったプログラムやサービス
  • 最近近話題になっている技術やサービス
  • 仕事のこと
  • 三鷹のこと
  • プログラマーズカフェ自体のこと
  • 世間話

といった話だけでなく、ちょっと公開できないようなこぼれ話や、プログラムなどとは全く関係のない話など、話題はあらぬ方向へ散らばっていきます。
それが面白いかどうか、役に立つかどうかはその人次第ですが、よくわからないものに積極的に興味を持てる人ならおもしろさを感じられるかもしれません。


三鷹プログラマーズカフェの主催は以下の三方です。



時間があったらこちらにも是非参加してください。


三鷹プログラマーズカフェと私


私(久末)は、昨年まで弊社が三鷹駅付近にあった関係で、三鷹プログラマーズカフェの最初のイベントから参加することができました。
以来、できるだけ毎回参加しています。何が参ｌ


なぜプログラマーズカフェナイト＠原宿なのか


三鷹プログラマーズカフェは公式には15時〜18時なのですが、実際は、18時以降も
三鷹産業プラザ内のCafe Hi Famigliaさんで、話が盛り上がったりしています。


とはいえ、公式には、平日の午後に開催ということで一般の会社務めの方には現実的に難しいのも事実。
そこで、たまたま弊社が三鷹から原宿に引っ越し、イベントができるスペースがあるということで、
夜のカフェをやろうという話をプログラマーズカフェの方々に持ちかけました。
すると主催のkuippaさんをはじめ、プログラマーズカフェに参加している数名に賛同していただき開催に至りました。
以下が今回の実行委員会的なメンバー。



次回


さて、実は、次回については、既に話を始めています。
興味のある方は是非参加してください。
告知は


三鷹プログラマーズカフェ (pgcafe) on Twitter
http://twitter.com/pgcafe


で行いますので、気になる方はフォローしてください。


最後に、弊社で開催と言っていますが、ここのオフィスはそもそも株式会社シナップさんのオフィスで弊社がオフィスシェアをさせていただいている場所です。
この素敵なオフィス空間を無償でイベントに使わせてくださったシナップさんにも感謝します。

続きを読む

Page 1 of 8712345»...Last »

このページの先頭へ