ダイクストラ法 - Bug's Groove
前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。 実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。 s -> y -> t (8) s -> y -> t -> x (9) s -> y (5) s -> y -> z (7) 教科書のヒープソート (6章) にもあったように、優先度付きキュー
PHP で Google 第一回 Google の PageRank を PHP で実装 - 横転プログラミング
Google の検索エンジンがページのランク付けのために PageRank という指標を使っているというのは聞いたことがあるかと思います。 今日はそのアルゴリズムを PHP で軽めに実装してみました。 ちなみに PHP で実装しても何もいいことがないので、やめたほうがいいでしょう。 まず PageRank というのは簡単に説明すると、 Google が考案したページのランク付けアルゴリズムでページへリンクがそのサイトの評価だという視点でランク付けを行うために作られたものです。 詳細については Google の秘密 - PageRank 徹底解説 を参考にしてみて下さい。 その内部アルゴリムですが、おおざっぱにいえば下の箇条書きにあるよう生成された確率行列の、最大固有値（確率行列はだいたいの場合において1）の固有ベクトルをべき乗法で求めることになります。 なぜ確率行列の主固有ベクトルを求める
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
ipm.dvi
Spectra of graphs Andries E. Brouwer Willem H. Haemers 2 Contents 1 Graph spectrum 9 1.1 Matrices associated to a graph . . . . . . . . . . . . . . . . . . . 9 1.2 The spectrum of a graph . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Characteristic polynomial . . . . . . . . . . . . . . . . . . 11 1.3 The spectrum of an undirected graph . . . . . . . . . . . . . . . . 11 1.3.1 Regular gr
Visualizing the London Underground in 3D with Ubigraph - smly’s notepad
モントリオール, 東京, ロンドンの地下鉄の駅と路線の関係をグラフとして可視化してみました. この結果には別に意味はないのですが, アルゴリズムのデバッグなんかには結構役に立ってくれそうだなと思いました. デモムービーでは次のようなことを行っています. typo がかなり多い. (00:05) モントリオールの地下鉄をグラフ表示 (01:15) GREEN の路線を緑色に色付けし, 強調表示 (01:48) 東京の地下鉄をグラフ表示 (02:59) 日比谷線を赤色に色付けし, 強調表示 (04:35) ロンドンの地下鉄をグラフ表示 (05:55) Square が名前に付く駅を探す (06:10) Square が名前に付く駅を緑で色付け (07:42) Euston Square から Sloane Square までの最短経路を緑色に色付けし, 強調表示右側のウィンドウで動いていたプロ
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
Google PageRank (ruby script/class)
Kodama's home / tips. Japanese description. Google PageRank (ruby script/class) This ruby script get a Google PageRank for a URL. Download: gprank.rb. Containing module is very simple, so it will be easily used in your script. Note update 2007-07-10. Because the format of query/reply for the PageRank server is changed. Note The script gprank.rb does not complete inperfect URL. Therefore, where a b
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Large-scale graph computing at Google