3

RGLを使用してRubyに有向グラフを実装しましたが、特定のノードについて、着信接続のあるノードと発信接続のあるノードのみを見つける方法を理解するのが難しいだけです。おそらく私は単純なものを見逃しています。

4

3 に答える 3

3

私はちょうどこの問題に遭遇しました。最もエレガントなアプローチではないかもしれませんが、逆の方法を使用するとうまくいくかもしれません。

require 'rgl/adjacency'
require 'rgl/bidirectional'

class RGL::DirectedAdjacencyGraph
    def in_degree(v)
    rdg = self.reverse
    rdg.adjacent_vertices(v).size
  end

  def out_degree(v)
    self.adjacent_vertices(v).size
  end
end

dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]

p dg.in_degree(2)
#=> 2
p dg.out_degree(2)
#=> 1

p dg.in_degree(1)
#=> 0
p dg.out_degree(3)
#=> 0

より長い答えは、まだ実装されていないようだということです。

RGL::Bidirectional モジュールを有向グラフ クラスに含めることで動作するはずです。これにより、すべての重要な each_in_neighbor メソッドが提供されます。したがって、次のようなものが機能するはずです（ただし機能しません）：

require 'rgl/adjacency'
require 'rgl/bidirectional'

class RGL::DirectedAdjacencyGraph
  include RGL::BidirectionalGraph
end

dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]

dg.vertices
#=> [5, 6, 1, 2, 3, 4]

p dg.adjacent_vertices(2)
#=> [3, 4]

p dg.each_in_neighbor(2)
#=>  NotImplementedError :(
#=> Should be:  [1]

これがどれだけの作業になるかを確認するためにコードを掘り下げていませんが、ニーズによっては、それがより良いオプションになる可能性があります。

編集:ソース属性とターゲット属性は、次数ノードにアクセスできないことに言及するのを忘れていました。しかし、別のアプローチとして、グラフから関心のあるすべてのエッジを収集し、それらを比較して、関心のあるノードがターゲットとして含まれているかどうかを確認することもできます。

于 2010-09-24T17:57:17.927 に答える
2

RGL::DirectedAdjacencyGraphは、発信接続のみを効率的に実装します。入力エッジへの効率的なアクセスも必要な場合は、RGL::BidirectionalGraphで定義された概念を効率的に実装する必要があります。これは、特定の有向グラフの実装でメソッド RGL::BidirectionalGraph#each_in_neighbor を実装して行う必要があります。

DirectedAdjacencyGraphがアウト ネイバーに対して行うように、各頂点のイン ネイバーもリストに格納するとします。次に、メソッドは次のようになります。

# Iterator providing access to the in-edges (for directed graphs) or incident
# edges (for undirected graphs) of vertex _v_. For both directed and
# undirected graphs, the target of an out-edge is required to be vertex _v_
# and the source is required to be a vertex that is adjacent to _v_.
def each_in_neighbor (v, &block)
  in_neighbors = (@vertice_dict_for_in_neighbors[v] or
                  raise NoVertexError, "No vertex #{v}.")
  in_neighbors.each(&block)
end

このアプローチを使用すると、エッジと頂点を挿入または削除するときに、2 つの頂点ディクショナリを管理する必要があります。

于 2011-01-09T16:40:54.593 に答える
0

有向辺には次のような特徴があります。

属性
[RW] ソース
[RW] ターゲット

それは役に立ちますか？私はあなたの質問を理解しているかどうか確信が持てません。

于 2010-02-02T20:48:13.727 に答える