DENSO IT LABORATORY,INC.

EN

TECH BLOG 技術ブログ

ホーム 　>　 技術ブログ 　>　 .NETグラフライブラリ QuickGraphを使う

増谷 修増谷 修

研究開発グループ

記事一覧

201312/9
  • プログラミング

.NETグラフライブラリ QuickGraphを使う

 

本エントリはC# Advent Calendar 2013 9日目のエントリです。

自己紹介ですが、デンソーアイティーラボラトリというところで研究開発をやっております。スコープは車とかITSとかそれにまつわるソフトウェア全般です。

研究のためのソフトウェア環境としては珍しくC#を使っておりますが、JavaやPythonよりもそういったリソースが少ないながら、質の高いライブラリが多いというのが実感です。今回はその中からQuickGraphという便利なライブラリの紹介です。かなり以前からCodePlexで公開されているので利用されている方も多いと思いますが、簡単に使えるように解説します。

QuickGraphを使おう

QuickGraphとは、グラフ型のデータ構造や各種アルゴリズムを備えた、.NET用のライブラリです。CodePlexのプロジェクトとして、2003年12月から公開されていました。

QuickGraph on CodePlex

グラフ解析の用途としては、我々が扱っているようなナビゲーションに関するものや、配管や工場のライン、送電網などのネットワークを扱った最大フローを求めるような問題、スケジューリングなどになります。ソーシャルネットワークの解析などでグラフマイニングを用いられる事が多いため、この応用事例が目立ちます。

５、６年前にこの手のライブラリを探していた当時はJavaが多く、オープンソースのJUNG や商用でビジュアライズの充実した yFilesなどが有名でした。現在はPythonのライブラリが充実しているようですね。

MatlabやRなど数値処理系の開発環境を使ってグラフアルゴリズムを扱うと好都合なことも多いと思いますが、特殊なVisitorパターンを用いたアルゴリズムを開発しようとすると、オブジェクト参照を基盤としていない、これらの言語では直観的でないプログラミングになりがちです。そういう時はC#,Javaなどの言語の方が分かりやすいですし、デバッグなどもし易いと思います。

実はC#に拘るのは少し別の理由だったりしますが、とにかくC#でグラフデータを扱いたいという動機で探してこのライブラリを見つけました。

QuickGraphの利点

いくつか利点があります。

  1. 高度に抽象化され、改変しやすい構造
  2. ジェネリックスを多用し既存のオブジェクトを改変せず利用できる
  3. 最小の計算コストでアルゴリズムを利用できる
  4. 珍しくポータブルクラスライブラリである（ピュア.NETでもある）
  5. 珍しくnuGetが提供されている

C#erとしては経験の浅い私には当初とっつきにくかったのですが、徐々にその良さがわかってきたというところです。

QuickGraphのCodePlexのページの解説は貧弱で、なかなかとっつきにくいので、各種のシナリオに沿って紹介するのをこの記事の目的とさせていただきます。

準備

nuget : QuickGraph　から最新版の取得ができます。

.NET,Silverlight, Windows Phone, Windows Storeアプリで活用できます。

各種定義

グラフ理論のベーシックなところは、たくさんの良い解説があると思うので省かせて頂きますが、QuickGraphで扱う概念のリストを書いておきます。

graphconcepts.png

お決まりになりますが、Edge（辺）はインターフェイスIEdge、Vertex（頂点）は型TVertexで定義されます。（有向グラフの場合）

  1. publicinterfaceIEdge<TVertex>
  2. {
  3.     TVertex Source { get; }
  4.     TVertex Target { get; }
  5. }

TVertexは既存のクラスであれば何でも良いわけで、特にQuickGraph用に特別なプロパティやメソッドを用意する必要はありません。何かを実装、継承する必要すらありません。

IEdgeはインターフェイスですが、必要なpublic要素は以上で全てです。最小の定義はこれだけです。これが利点１，２に貢献しています。

また、アルゴリズムは以下の形式となり、任意のTVertex,IEdgeを対象にできる柔軟性の高い記述が可能です。大ざっぱに言うとCollectionの処理と同様の使い方ということですね。

  1. publicinterfaceISomeGraphAlgorithm<TVertex,TEdge>
  2.     where TEdge : IEdge<TVertex>

使ってみる

グラフを作る

グラフをビルドするのは簡単です。

  1. var edges = newSEdge<int>[] { newSEdge<int>(1,2), newSEdge<int>(0,1) };

SEdgeというのはIEdgeを単純に実装しただけのクラスです。TVertexとしてintを利用しているので頂点の生成コードはいりません。

頂点は辺に内包されておりますので、グラフはSEdgeのコレクションで表現できます。ここでは配列になっています。

残念ながらこのままでは直接アルゴリズムを利用できません。以下のように隣接行列をビルドしAdjacencyGraphを生成する必要があります。

  1. var graph = edges.ToAdjacencyGraph<int, SEdge<int>>();

QuickGraphのソースを追ってみると、中で行われている本質的な処理はAdjacencyGraphクラスのコンストラクタの以下の部分だけです。（かなり要約していますが）

頂点から出ていく辺のディクショナリーの生成をしているだけで、隣接行列を作ったり、この段階では、特殊な処理を行っているわけではありません。

  1. privatereadonly IVertexEdgeDictionary<TVertex, TEdge> vertexEdges;
  3. foreach (var e in edges)
  4.     this.vertexEdges[e.Source].Add(e);

ほかにもいくつものグラフの生成方法がありますのでQuickGraphのドキュメントを参照ください。

 

グラフをイテレートする

これも特に説明するまでもありません。VerticesメンバはIEnumerableなのでコレクションとしてイテレートできます。

  1. foreach(var v in g.Vertices)
  2.     Console.WriteLine(v);

また頂点から出る辺を辿るにはこうです：

  1. foreach(var v in g.Vertices)
  2.     foreach(var e in g.OutEdges(v))
  3.         Console.WriteLine(e);

このように当たり前の事は直感的にできるようになっています。

もう少し複雑なイテレートをやろうとした場合は、そのためのアルゴリズムが用意されています。幅優先探索を例にすると以下のようなステップになります。

  1. publicvoid search<TVertex>(AdjacencyGraph<TVertex,IEdge<TVertex> g, TVertex target)
  2. {
  3.     var bfs = newBreadthFirstSearchAlgorithm<TVertex, IEdge<TVertex>>(g);
  4.     var predecessors = newList<IEdge<TVertex>>();
  5.     bfs.TreeEdge += newEdgeAction<TVertex, IEdge<TVertex>>((e)=> predecessors.Add(e));
  6.     bfs.Compute(target);
  7.     foreach (var e in predecessors)
  8.     {
  9.         Hoge(e);
  10.     }
  11. }

グラフgと始点targetが与えられます。BreadthFirstSearchAlgorithmというまんまの名前のクラスがあるのでgで生成します。

predecessorsはただのエッジのリストです。これをオブザーバとしてTreeEdgeメンバへEdgeActionという形でリスンさせます。

Computeとすると、targetから幅優先探索が行われ、predecessorsに順に辺が格納されていきます。

そして順序づけられたpredecessorsに対して何か処理を行うことができます。

イテレートする際に行う処理をデリゲートで渡すことができるため、ノードだけ収集したい場合など柔軟に対応できます。

 

最短のパスを求める

目的地までの最短経路を求める問題は、ダイクストラ法がよく知られていますが、QuickGraphではこれもまんまの名前で、DijkstraShortestPathAlgorithmというクラスがあります。

このクラスをまずグラフとコストを示すデリゲートにて生成します。コストは関数で記述できるのでエッジの状態から都度再計算するような事もできます。

次にVertexPredecessorRecorderObserverというオブザーバークラスにdijkstraにアタッチします。

（オブザーバーが無いと後で最短パスを取ることができません。）

Computeで探索を行い、結果がオブザーバーにセットされますから、これをtargetを指定して取り出します。

  1. publicIEnumerable<TEdge> findShortestPath(TVertex source, TVertex target)
  2. {
  3.     var dijkstra = newDijkstraShortestPathAlgorithm<TVertex, TEdge>(graph, (e) => 1);
  4.     var predecessorObserver = newVertexPredecessorRecorderObserver<TVertex, TEdge>();
  5.     predecessorObserver.Attach(dijkstra);
  6.     dijkstra.Compute(source);
  7.     IEnumerable<TEdge> path;
  8.     predecessorObserver.TryGetPath(target, out path);
  9.     return path;
  10. }

Computeの段階で最小スパニング木が求められ、TryGetPathの段階で指定されたターゲットへの最短経路が求められるわけです。

Observerパターンにより、辺の列を取るだけでよいばあい、各辺までの距離を求める場合、など必要な処理のみを行わせることができるので、利点３に貢献します。

頂点が２次元空間上の点に当てはめるとすると以下のような頂点クラスを定義します。

  1. publicclassGeographicVertex
  2. {
  3.     publicdouble gx;
  4.     publicdouble gy;
  5. }

すると、必然的に上記のラムダ式は以下のように置き換えることができます。

  1. (e) => Math.Sqrt(Math.Pow(e.Source.gx – e.Target.gx, 2) + Math.Pow(e.Source.gy – e.Target.gy, 2));

このような形で、A*アルゴリズムによる最短経路探索、Floyd Warshall法による全点間の最短経路探索、最小スパニング木、最大フロー問題、強連結成分など、アルゴリズムの教科書に出てきたような問題はほぼ解くことができます。

 

応用

このように柔軟性が高いライブラリですので、様々な用途で使うことができると思います。またグラフ解析そのものの研究などを行うことも可能で、独自のアルゴリズムをこの枠組みで作れば、非常に効率が良い研究ができるのではないでしょうか？

記事一覧へ

増谷 修Osamu Masutani

研究開発グループ

記事一覧

アーカイブ

20253/31
東京科学大と共同研究講座を開設
20253/4
テクノロジー・オブ・ザ・イヤー 優秀賞 を受賞しました
20252/4
2024年のクリスマスパーティが開催されました
202412/27
「よく似た音」を利用し、異音検知する教師なしモデルの高精度化と学習計算量の削減を実現する手法を...
20247/18
マルチコンディション学習で多言語対応の合成音声評価が可能になるメカニズムを解明［GCCE 2022］
20246/3
汎用GPUの新たな演算量削減と精度維持を両立する手法を提案[ICLR2024]
20244/5
イベントカメラの出力をもとに少ない計算量で高速に動きを認識 [CVPR2023]
20213/26
NLP2021 スポンサー賞選考の報告
20193/15
CollabTech Seminar in MIRU2019
201812/27
開発ー強化ー合宿

メンバー一覧

研究開発グループ
太刀岡 勇気

研究開発グループ
長田　惇

研究開発グループ
関川 雄介

研究開発グループ
マルチリサーチャ
吉田　悠一

研究開発グループ
シニアリサーチャ
鈴木　幸一郎

研究開発グループ
シニアリサーチャ
塚原　裕史

研究開発グループ
シニアリサーチャ
佐藤　育郎

研究開発グループ
坂倉 義明

研究開発グループ
増谷 修

研究開発グループ
山本 光穂

研究開発グループ
欅 惇志

研究開発グループ
宇土 敬祐

研究開発グループ
社員一同

カテゴリ

このページのトップへ