フォードファルカーソン法をRubyで実装 - yasuhisa's blog
グラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。 繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。 # -*- coding: utf-8 -*- require "pp" class DirectedGraph attr_reader :nodes attr_reader :weights attr_reader :edges
Network Flow
ネットワーク 定義 G：有向グラフ V：点の集合 E(G)={e=(u,v)|u,v∈V}：Gにおける辺の集合 cap(e)：各辺eの容量 s：湧出点、入口, t：流入点、出口 (s,t∈V) N=(G,cap,s,t)：ネットワーク f:E(G)→R+（辺集合E(G)から非負実数集合への関数） δ-(v)：vを終点とするNの辺の集合 δ+(v)：vを始点とするNの辺の集合 ただし、fは次の二つを満たす
西尾泰和のブログ: GRINEditを使ってソースコードの可視化
控えめな Brainfuck コードを色づけする GM を見て、唐突に思いついたので作ってみました。 可視化する対象のコードは、 竹迫さんのTAKESAKO @ Yet another Cybozu Labs: Brainf*ckで100までの素数を列挙してみるテストと、奥さんのKazuho@Cybozu Labs: brainf*ck でマジメに素数探索。 まず、竹迫さんのコードの全体像。 そして一部拡大した物がこれ。 各頂点が1つの命令で、太い辺が命令の隣接関係、 細い辺が括弧の対応関係です。+が赤、-が青、.が緑になっています。 竹迫さんのコードは実は数字を作って表示するだけのコードなので、 大局的な構造がありません。 大まかに見ると「小さなループが所々にある1本の紐」です。 可視化する際も、頂点を徐々にy座標を増やしながら作るだけでこんな風に ほとんどもつれずに表示されました。 い
kuma tora page
このドキュメントはワードの文書より自動生成したものです。 見た目がおかしいですが、あまり気にしないでね。ぽっ。
ETBダイアグラム
「ETBダイヤグラム」と僕（檜山）が勝手に呼んでいる図式法／図解法を説明 する。呼称はともかくとして、このような図式は新規なものではなくて、既に よく使われている。図式をベースにしたプログラミング、設計（デザイン）、 コンフィギュレーションなどへの応用が期待できる。 関連記事：「圏論」インデックス 1. はじめに Chimairaアーキテクチャでは、図式による説明や計算をヘビーに使うつもり だ。図式（視覚的な表現）を使えば、言葉や記号による説明／計算よりも簡便 で直感的になる（こともある）からだ。 それと、図式をベースにしたプログラミング、設計（デザイン）、コンフィ ギュレーションなどを実現したいという目論見もある。そのためには、図式法／ 図解法を明確に定義する必要がある。 と、そういうわけで、ある図式法について解説する。なお、この記事の注釈、 ノートは“読み流し／読み飛ばし”しても差しつ
点と線の部屋
平成１６年２月２３日 第一部 第五十四章 「アフィン平面と射影平面」 新規公開 平成１６年１月４日 第一部 第五十二章 第三節 「4次のアフィン平面」 追加 第一部 第五十三章 「麻雀の組合せの問題（ラテン方陣とアフィン平面）」 新規公開 第二部 第三十三章 「有限体クラスの拡張」 新規公開 平成１５年２月１１日 第二部 第三十二章 「有限体クラス」 新規公開 平成１５年２月３日 第一部 第五十二章 「体とアフィン平面」 新規公開 平成１５年１月１３日 第一部 第三十一章 第三節を不備訂正のため大幅に変更し、また一部を第四節に分離独立させた 平成１４年１１月３日 第一部 第五十一章 「再構成問題 その１」 新規公開 平成１４年７月１５日 第一部 第五十章 「最短経路問題」 新規公開 平成１４年５月１３日 第一部 第四十九章 「弦グラフ その１」 新規公開 平成１４年２月４日
Graph Classes and Algorithms
[概要] 計算機で扱う問題は，多くの場合グラフ上の問題として定式化できる． 計算量の理論により，これまで多くの問題が``手に負えない''ことが示されてきた． 一方でこうした問題に対する現実的なアプローチがいくつか提案されてきた． 本稿ではグラフに制限を加えるアプローチについて解説する．DNA の切片間の関係などは， モデル化すると特別なグラフになる．こうしたグラフ上では， これまで手に負えないとされてきた問題が効率良く解けることがある． 本稿では，代表的なグラフクラスと，関連したアルゴリズムの最近の研究動向を解説する． [キーワード] アルゴリズム，グラフクラス，計算の複雑さ，理想グラフ [お断り] このページは，電子情報通信学会に掲載予定の同名の解説論文を加筆修正したものです． せっかく書いたので，より広く公開して，かつ，ときどきは更新して行こうかと思っています． リンクも少しずつ充実さ
VCG Overview
Description Windows Availability Features Examples Availability Mailing List Publications Related Work Description The VCG tool reads a textual and readable specification of a graph and visualizes the graph. If not all positions of nodes are fixed, the tool layouts the graph using several heuristics as reducing the number of crossings, minimizing the size of edges, centering of nodes. The specific
コード構造を視覚化せよ！！（Graphviz & Doxygen）
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Skip Graph の concurrent JOIN を考える - その3 - higepon blog
http://sxt.freeservers.com/intro_.htm
Graph Theory Lessons