Elenco e grafico di adiacenza

Question

Sto provando a creare un grafico per elenco di adiacenza, il che significa che ho bisogno di un elenco per tutti i nodi, e all'interno di ogni classe di nodi, ho anche bisogno di una struttura dati per contenere tutti i nodi adiacenti. Mi chiedo solo quale sarebbe la struttura migliore per farlo (una ricerca veloce per la classe nodo di destinazione). Un array funzionerebbe?

Answer 1

Ecco un modo per creare un grafico diretto in Ruby, dove ogni nodo mantiene i riferimenti ai suoi successori, ma i nodi possono essere referenziati per nome. Per prima cosa avremo bisogno di una classe per i nodi:

class Node 

    attr_reader :name 

    def initialize(name) 
    @name = name 
    @successors = [] 
    end 

    def add_edge(successor) 
    @successors << successor 
    end 

    def to_s 
    "#{@name} -> [#{@successors.map(&:name).join(' ')}]" 
    end 

end 

Ogni nodo mantiene i riferimenti ai suoi successori. Non sapendo che tipo di operazioni hai bisogno, non ho definito nessuno che faccia effettivamente attraversamento di grafici, ma ogni nodo che ha riferimenti ai suoi successori rende banale il percorso del grafico.

Ora creeremo una classe per rappresentare l'intero grafico:

class Graph 

    def initialize 
    @nodes = {} 
    end 

    def add_node(node) 
    @nodes[node.name] = node 
    end 

    def add_edge(predecessor_name, successor_name) 
    @nodes[predecessor_name].add_edge(@nodes[successor_name]) 
    end 

    def [](name) 
    @nodes[name] 
    end 

end 

Questa classe mantiene un hash dei suoi nodi, calettati per nome. Ciò rende facile il recupero di un nodo specifico.

Ecco un esempio di un grafico contenente un ciclo:

graph = Graph.new 
graph.add_node(Node.new(:a)) 
graph.add_node(Node.new(:b)) 
graph.add_node(Node.new(:c)) 
graph.add_edge(:a, :b) 
graph.add_edge(:b, :c) 
graph.add_edge(:c, :a) 
puts graph[:a] #=> a -> [b] 
puts graph[:b] #=> b -> [c] 
puts graph[:c] #=> c -> [a]