Travailler avec un graphe orienté utilisant RGL dans Ruby

Question

J'ai implémenté un graphe orienté dans Ruby en utilisant RGL, j'ai juste du mal à trouver comment, pour un noeud donné, trouver uniquement les noeuds avec des connexions entrantes et les noeuds avec des connexions sortantes . Peut-être qu'il me manque quelque chose de simple.

Answer 1

Il ressemble à Directed Edges ont:

Attributs
la source
[RW] cible

[RW] Est-ce que l'aide? Je ne suis pas sûr de comprendre votre question.

Answer 2

Je viens de rencontrer ce problème. Utilisation de la reverse method pourrait fonctionner, mais il pourrait ne pas être l'approche la plus élégante:

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 

La réponse est plus qu'il ne semble pas encore mis en œuvre.

La façon dont il est censé fonctionner est d'inclure le module RGL :: Bidirectionnel avec votre classe de graphes orientés, cela vous donnera la méthode chaque-importante each_in_neighbor. Donc, quelque chose comme cela devrait fonctionner (mais ne fonctionne pas):

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] 

Je n'ai pas creusé dans le code pour voir combien de travail ce serait, mais ce pourrait être une meilleure option en fonction de vos besoins. Editer: J'ai oublié de mentionner que les attributs source et cible ne sont pas accessibles à un nœud au degré. Mais une approche alternative pourrait consister à collecter toutes les arêtes d'intérêt du graphique et à les comparer pour voir si l'un d'entre eux a comme cible votre nœud d'intérêt.

Answer 3

RGL :: DirectedAdjacencyGraph implémente uniquement les connexions sortantes de manière efficace. Si vous souhaitez également avoir un accès efficace aux arêtes entrantes, vous devez implémenter le concept défini par RGL :: BidirectionalGraph aussi efficacement. Cela devrait être fait en implémentant la méthode RGL :: BidirectionalGraph # each_in_neighbor dans votre implémentation de graphe orienté spécifique. Supposons que vous stockiez les voisins in-voisins pour chaque sommet dans une liste similaire à DirectedAdjacencyGraph pour les voisins externes. Ensuite, la méthode pourrait comme ceci:

# 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 

En utilisant cette approche, vous devez gérer deux dictionnaires de sommet lors de l'insertion ou le retrait des bords et Vertice.