中断可能なダイクストラ最短経路アルゴリズム - Faith and Brave - C++で遊ぼう
【graph】 interest in resumable dijkstra? Boost.Graphに、中断可能なダイクストラ最短経路アルゴリズムが提案されています。 提案されている実装としては、最短経路アルゴリズムに渡すevent visitorに、do_interrupt()メンバ関数を追加してその関数がtrueを返したら内部のループをbreakするというものです。 他の案としては、Boost 1.51.0から入る予定のBoost.Contextや、N3328 Resumable Functionsで提案されているawait (C#にあるアレ)があったらそれ使いたい、という話がでてます。 Boost.Contextで中断可能なアルゴリズムは、前にやりました： Boost.Context アルゴリズムを中断可能にする
Boost.Graph 一筆書き - Faith and Brave - C++で遊ぼう
オイラー閉路というのを求めると、グラフの一筆書きの経路を得ることができます。 Boost.Graphにはオイラー閉路のためのアルゴリズムは用意されていないので、以下のページを参考にBoost.Graphベースで書いてみました。 無向オイラー路 - Spaghetti Source 今回一筆書きするのは、「サンタクロースの家」と呼ばれるグラフです。 サンタクロースの家を一筆書きするコード： #include <iostream> #include <deque> #include <string> #include <shand/graph/euler_path.hpp> #include <boost/graph/adjacency_list.hpp> enum {A, B, C, D, E, N}; const std::string name = "ABCDE"; int main()
Boost.Graph 最小全域木を作る - Faith and Brave - C++で遊ぼう
グラフに含まれるすべての頂点を含む最小の部分グラフを、最小全域木(minimum spanning tree)と言います。 Boost.Graphには、最小全域木を作るためのアルゴリズムとして、以下の2つの関数が用意されています。 boost::kruskal_minimum_spanning_tree() : クラスカル法 boost::prim_minimum_spanning_tree() : プリム法 これらを以下のグラフに適用すると 以下のような最小全域木(赤線部分)が手に入ります。 それぞれの使い方は以下のようになります。 boost::kruskal_minimum_spanning_tree() クラスカル法によって最小全域木を求めるboost::kruskal_minimum_spanning_tree()関数は、Output Iteratorで最小全域木の辺記述子(ed
Boost.Graph 最短単純路 - Faith and Brave - C++で遊ぼう
辺に重みのないグラフから最短経路を求めると、「最短単純路」という通過する辺が最も少ない経路が得られます。 Boost.Graphのboost::dijkstra_shortest_paths()は重みのないグラフを与えるとコンパイルエラーになるので、辺の重みを全て1に設定することで代用できます。 #include <iostream> #include <vector> #include <deque> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_
Boost.Graph Bundleプロパティ - Faith and Brave - C++で遊ぼう
Boost.Graphのグラフ構造には、Property Mapによって頂点・辺・グラフに任意のプロパティを持たせることができます。 ただ、プロパティが増えてくると管理しきれなくなってくるので、ひとまとめにしたくなります。 そこで、Boost.GraphにはBundleプロパティという機能が用意されています。これは、グラフ構造のプロパティ指定のところにユーザー定義クラスを指定するという機能です。 以下のサンプルでは、 頂点のBundleプロパティとして「名前」「人口」「郵便番号一覧」を持つCity(街)クラス。 辺のBundleプロパティとして「名前」と「距離」を持つHighway(高速道路)クラス。 グラフのBundleプロパティとして「名前」を持つCountry(国)クラス を設定しています。 そして、最短経路の計算の際に、Highwayクラスのdistanceメンバ変数を辺の重みとし
Boost.Graph トポロジカルソート - Faith and Brave - C++で遊ぼう
閉路を持たない有向グラフ(DAG : Directed Acyclic Graph)に順序を付けるトポロジカルソートのために、Boost.Graphにboost::topological_sort()関数が用意されています。 topological_sort()関数は、グラフに対するconst参照と、結果を返すためのOutput Iteratorを引数にとります。 以下の有向グラフに、トポロジカルソートを適用してみます： #include <iostream> #include <vector> #include <iterator> #include <utility> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> #include <boost/range/al
Boost.Graph 2つのグラフが同型かを調べる - Faith and Brave - C++で遊ぼう
Boost.Graphには、boost::isomorphism()(アイソモルフィズムと読む)という、2つのグラフが同型かを調べる関数が用意されています。 以下の2つのグラフが同型かどうかを調べてみます。この2つは、頂点の順番等は異なってますが、同じ形のグラフです。 g1: g2: #include <iostream> #include <vector> #include <utility> #include <boost/graph/isomorphism.hpp> #include <boost/graph/adjacency_list.hpp> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph; const int vertex_count = 12; Graph
Boost.Context アルゴリズムを中断可能にする - Faith and Brave - C++で遊ぼう
既存のアルゴリズム関数の実行を中断可能にしてみました。 対象は、Boost.Graphの最短経路計算アルゴリズムです。 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/assign/list_of.hpp> #include <functional> #include "continuation.hpp" typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, int> > G
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
