大規模グラフアルゴリズムの最先端
2. 挨拶 • 自己紹介 – 秋葉拓哉 / @iwiwi – 東京大学 コンピュータ科学専攻 M1 – アルゴリズム系の研究室 – プログラミングコンテストが好き – 2009 年にインターンさせてもらって以来アルバイト アリ本 （グラフの話もあるよ） 1 3. いろんなグラフ 道路・交通ネットワーク • 頂点：交差点，駅など • 辺：道，路線など やりたいことの例 • 案内，交通管制 • 輸送や災害のための解析 • 地理情報と絡めたサービス • … 2 4. いろんなグラフ ソーシャルネットワーク • 頂点：人 • 辺：人間関係 やりたいことの例 • 「知り合いかも？」とか • 重要度・影響度の解析 • コミュニティ解析 • 情報の伝播力の解析 • … (MentionMap で作成) 映画 3
やねうらお―よっちゃんイカを買いに行ったついでに家を買う男 - グラフ理論ならこれを読め！
うちの会社では「グラフ理論を小学校のうちに学んでおかないから、そういうことになるんジャイ！(｀ω´)」とか冗談とも本気とも取れないような会話が平気で行き交う。それほどグラフ理論は大切な分野なのにプログラマには見過ごされがちだ。ただ、グラフ理論にはいい本が少ない。そこで、グラフ理論ならこれを読め！という本を紹介する。まずは、入門書としては、左の本がお勧め。 大学の教科書としてよく採用されているのが左の「最適化とグラフ理論 技術者のための高等数学」値段も手ごろだし、高校卒業程度の知識でも読めると思う。 「そんな入門書ではなくて、もっと詳しい本は無いか？」とid:Ozyさんに聞かれて私が勧めたのは、シュプリンガー・フェアラーク東京シリーズの「グラフ理論」 このシリーズは黄色い表紙とお馬さんのマークが目印だ。 これより詳しい本となると日本語で読めるものは発売されていないと思う。「グラフ同型判定問題
ベルマンフォード法 - nokunoの日記
アリ本より。グラフの最短経路を求めるベルマンフォード法の実装を行いました。 #include #define MAX_E 20 #define MAX_V 7 #define INF 100000 struct edge {int from, to, cost; }; edge es[MAX_E] = { {0, 1, 2}, {0, 2, 5}, {1, 2, 4}, {1, 3, 6}, {1, 4, 10}, {2, 3, 2}, {3, 5, 1}, {4, 5, 3}, {4, 6, 5}, {5, 6, 9}, {1, 0, 2}, {2, 0, 5}, {2, 1, 4}, {3, 1, 6}, {4, 1, 10}, {3, 2, 2}, {5, 3, 1}, {5, 4, 3}, {6, 4, 5}, {6, 5, 9}, }; int d[MAX_V]; void s
Category:Graph families - Wikipedia
This category contains articles about collections of graphs either defined by some specific property, or decorated by some additional combinatorial information, and sufficiently notable to have a name. See Families of sets for related families of non-graph combinatorial objects, graphs for individual graphs and graph families parametrized by a small number of numeric parameters, and graph theory f
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
perlでダイクストラ法 - uncertain world
なんとなくダイクストラ法を使う機会がありそうなので、勉強がてらに。 ダイクストラ法は、2点間の最短距離を求めるアルゴリズムです。 カーナビとかにも使われているらしいです。 以下、さんぷるこーど。 #!/usr/bin/perl use strict; use Dumpvalue; my @nodes = ( { id => 0, point => [0,0], edges => {1=>5,3=>6,4=>9}, distance => 0, done => 1, from => undef, }, { id => 1, point => [2,0], edges => {0=>5,2=>5,3=>2,4=>2,5=>6}, distance => 0, done => undef, from => undef, }, { id => 2, point => [4,0], edges =>
R でグラフ理論 - RjpWiki
RjpWiki はオープンソースの統計解析システム R に関する情報交換を目的とした Wiki ですgraph [vignette: y; demo: n] グラフデータ構造を取り扱うパッケージ. † ↑ RBGL [vignette: y; demo: n] Interface to boost C++ graph library (based on graph objects from the graph package). † ↑ gRain [vignette: y; demo: y] An alternative interface to graphs. Uses the graph and RBGL and implements additional graph operations. † ↑ dynamicGraph [vignette: n; demo: y] Provid
アルゴリズム設計 講義資料 2005
Algorithm Design Course Materials 2013 Oct 7: Introduction and Computational Complexity Oct 15: Search Trees Oct 21: Combinatorial Optimization Oct 28: Heuristic Search Nov 5: Text Search Nov 11: Data Compression Nov 18: Memory Management Nov 25: Graph Algorithms 1/2 Dec 2: Graph Algorithms 2/2 Dec 9: Computational Geometry Dec 16: Concurrency Control Jan 15: Canceled Jan 20: Clustering Course Pro
Graph: Boost: 篠田孝祐
C++ 用のライブラリ．汎用的なライブラリの少なかった？ C++ にとって，これのおかげで開発がしやすくなったといっても過言ではない．たぶん．ここではBoostに関する詳しい説明は省くので，下記の参考書などを参考にしてもらいたい． 本ページでは，Boostを用いたネットワークの中心性の計算を方法について説明する． ネットワークの中心性とは，ある要素集合と，個々の要素間の関係性から構成されるネットワークにおいて，そのネットワークにおける各要素の重要性を示す指標として，様々なものが提示されている．このネットワークの中心性は，ネットワーク分析や複雑系ネットワークにおいて重要な要素であるが，私自身が始めた当時，大規模なネットワークを対象としたライブラリやツールは提供されていなかった．そこで，実際にネットワークデータをプログラムで扱おうと作成しはじめて見たところ，データ構造や管理，探索など結構面倒で
Table of Contents: Boost Graph Library(BGL)
目次: the Boost Graph Library BGL への序章 歴史 刊行物 謝辞 クイック・ツアー 基本的なグラフ理論の復習 チュートリアル Property Maps The adjacency_list class 例題 ファイル依存関係の例 Kevin Bacon の６次数 Graph Coloring Sparse Matrix Ordering BGL 拡張 Constructing graph algorithms with BGL Converting Existing Graphs to BGL Boost Graph インタフェイス Graph Incidence Graph Bidirectional Graph Adjacency Graph Vertex List Graph Edge List Graph Vertex and Edge List Gr
Welcome to igraph's new home
igraph – The network analysis package igraph is a collection of network analysis tools with the emphasis on efficiency, portability and ease of use. igraph is open source and free. igraph can be programmed in R, Python, Mathematica and C/C++. igraph R package python-igraph IGraph/M igraph C library python-igraph 0.9.6, the fourth bugfix release of the 0.9 series, has arrived. The preferred way of
GraphML Primer
Editors: Ulrik Brandes ulrik.brandes@uni-konstanz.de, Markus Eiglsperger eiglsper@web.de, Jürgen Lerner lerner@inf.uni-konstanz.de Abstract GraphML Primer is a non-normative document intended to provide an easily readable description of the GraphML facilities, and is oriented towards quickly understanding how to create GraphML documents. This primer describes the language features through examples
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: 技術者のための高等数学 6: E. クライツィグ (著), Kreyszig,Erwin (原名), 義保,田村 (翻訳): 本