Rubyの実用的なグラフ理論

これは「実用的なコンピュータサイエンス」シリーズの次回の記事で、Rubyを使用して実際の問題を解決するために古典的なコンピュータサイエンスの概念を適用する方法を学びます。

今日はグラフ理論についてお話します 。

二分木について聞いたことがあるかもしれませんが、次のようになります。

重要なのは、バイナリツリーはグラフの特殊なバージョンにすぎないため、グラフがどれほど普及しているかを知ることができるはずです。

グラフ理論の基礎の概要から始めましょう。次に、いくつかの実用的な使用法と、これをRubyで実装する方法を見ていきます。

グラフの基礎

グラフは2つの要素で構成されています：

• ノード（または頂点）
• エッジ

1つのノードは、マップを表すグラフ内の都市や通りなど、グラフ内の1つの要素を表します。エッジはノード間の接続を表します。

コンピュータサイエンスや数学の本を見ると、次の式で定義されたグラフが表示されます：G(V, E) 。

ここでG グラフ、Vを意味します 頂点とEのセットです はエッジのセットです。

グラフは有向または無向にすることができます。つまり、一方向（有向グラフ）または両方向（無向グラフ）にしか移動できません。

最も人気のあるタイプのグラフは、有向非巡回グラフです。 （DAG）。非周期的とは、ループがなく、後戻りする方法がないことを意味します。

グラフの使用

基本の概要を説明したので、グラフの一般的な使用法をいくつか見てみましょう。

グラフを使用すると、次のようなことができます。

• 2つの場所の間の最短（または最長）のパスを見つける
• 2つのものが互いに関連しているかどうかを確認します
• レコメンデーションエンジンを構築する
• 依存関係を分析する

別の例には、目的地への最適なルートを見つけることが含まれます（GPSデバイスを考えてください）。

グラフの実装と使用方法

独自のグラフ実装を作成することもできますが、この記事では、すでに実装されているRGLgemに固執します。

RGLを使用して基本的なグラフを作成するには：

require 'rgl/adjacency'

graph = RGL::DirectedAdjacencyGraph.new

graph.add_edge 1,2
graph.add_edge 3,4
graph.add_edge 1,4
graph.add_edge 4,3

このコードは次のグラフを生成します：

次のようなグラフのグラフィック表現を取得できます：

require 'rgl/dot'

graph.print_dotted_on

次に、そのメソッドの出力をドット言語を処理できるサイトにコピーします。このように。

または、マシンにGraphvizをインストールして、イメージをローカルで生成することもできます。

グラフができたので、グラフをトラバースして情報を調べたいと思うかもしれません。

グラフを検索するための2つの基本的なアルゴリズムがあります ：

• 幅優先探索（BFS）
• 深さ優先探索（DFS）

BFSでは最初に最も近いノードを取得し、DFSではすべてのノードを可能な限り深くします。これらのアルゴリズムは、スタックデータ構造を使用して実装できます。

RGL gemは、すでにこれらのアルゴリズムを実装しています：

require 'rgl/traversal'

graph.bfs_iterator.to_a
# [1, 2, 4, 3]

graph.dfs_iterator.to_a
# [1, 4, 3, 2]

グラフをもう一度見て、これらのアルゴリズムが目だけを使用して行ったパスをたどります（または、必要に応じて指を使用することもできます）。それはあなたが何が起こっているのかを理解するのに役立ちます。

加重グラフ

グラフに重みの形でさらに情報を追加して、グラフをより便利にすることができます。

重みはエッジに与えられます。エッジは2つのノード間のパスです。 （「頂点」とも呼ばれます）。これらの重みは、あるポイントから別のポイントに移動するためのコストを表します。

たとえば、グラフ形式の国の地図があり、特定の目的地にできるだけ短い時間で到達したい場合、重みは2つの都市間の距離を表します。

または、コンピュータネットワークがある場合、重みは特定のネットワークに到達するのに必要なホップ数を表す場合があります。

「コンピュータネットワークでは、ホップは送信元と宛先の間のパスの一部です。データパケットは、送信元と宛先の間を移動するときに、ブリッジ、ルーター、およびゲートウェイを通過します。パケットが次のネットワークデバイスに渡されるたびに、ホップが発生します。」 –ウィキペディア

加重グラフのコード例は次のとおりです。

graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"

edge_weights =
{
  ["New York", "Los Angeles"] => 2445,
  ["Los Angeles", "Chicago"] => 2015,
  ["Los Angeles", "Houston"] => 1547,
  ["Chicago", "Houston"] => 939,
  ["Seattle", "Los Angeles"] => 1548
}

edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }

これで、ある地点から別の地点への最短経路を検索できます。そして、それはまさに次のセクションのトピックです！

最短経路を見つける

グラフ内の最短経路を見つけるための一般的なアルゴリズムは、「ダイクストラの最短経路」アルゴリズムです。

重み付きグラフが与えられると、ダイクストラのアルゴリズムを使用してこの質問を解決できます。

「ポイントAからポイントBに移動する最速の方法は何ですか？」

RGLgemを使用したコード例を次に示します。

p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston")
# ["New York", "Los Angeles", "Houston"]

これは、グラフで利用可能な情報を使用して、ニューヨークからヒューストンへの最短経路を示しています。

概要

グラフのデータ構造とは何か、そしてそれをRGLgemで使用する方法を学びました。

また、DFS、BFS、ダイクストラなど、グラフを操作するための一般的なアルゴリズムについても学びました。

この投稿を共有することを忘れないでください より多くの人が楽しめるように便利だと思ったら🙂