Working with a directed graph using RGL in Ruby

I've implemented a directed graph in Ruby using RGL, just having difficulty figuring out how to, for a given node, find only the nodes with incoming connections and the nodes with outgoing 开发者_JS百科connections. Perhaps I'm missing something simple.

I just ran into this problem. Using the reverse method might work, though it might not be the most elegant approach:

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

The longer answer is that it doesn't appear to be implemented yet.

The way it's supposed to work is by including the RGL::Bidirectional module with with your directed graph class, this will give you the all important each_in_neighbor method. So something like this should work (but doesn't):

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]

I haven't dug into the code to see how much work this would be, but that might be a better option depending upon your needs.

Edit: I forgot to mention that the source and target attributes are not accessible to an in-degree node. But an alternate approach could be to collect all the edges of interest from the graph and compare them to see if any of them have your node of interest as a target.

RGL::DirectedAdjacencyGraph only implements outgoing connections efficiently. If you also want to have efficient access to the incoming edges you should implement the concept defined by RGL::BidirectionalGraph as efficiently. That should be done implementing the method RGL::BidirectionalGraph#each_in_neighbor in your specific directed graph implementation.

Suppose you store the in-neighbors for each vertex also in a list like DirectedAdjacencyGraph does for the out-neighbors. Then the method could like this:

# 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

Using this approach you have to manage two vertex dictionaries when inserting or removing edges and vertice.

It looks like Directed Edges have:

Attributes
[RW] source
[RW] target

Does that help? I'm not quite sure I understand your question.