class ShortestPathsMeasure

Return the list of shortest path (Dijkstra) in Archipelago

Public Instance Methods

compute(archipelago) click to toggle source
# File lib/gimuby/genetic/archipelago/measure/shortest_paths_measure.rb, line 6
def compute(archipelago)
  nodes = archipelago.get_nodes
  shortest_paths_length = []
  nodes.each do |node1|
    nodes.each do |node2|
      if node2 > node1
        length = get_shortest_path_length(archipelago, node1, node2)
        unless length.nil?
          shortest_paths_length.push(length)
        end
      end
    end
  end
  shortest_paths_length
end

Private Instance Methods

get_shortest_path_length(archipelago, node1, node2) click to toggle source
# File lib/gimuby/genetic/archipelago/measure/shortest_paths_measure.rb, line 24
def get_shortest_path_length(archipelago, node1, node2)
  next_nodes = [node1]
  current_neighbor_distance = 0
  nodes_distances = {node1 => current_neighbor_distance}
  while next_nodes.length != 0
    current_node = next_nodes.shift
    current_neighbor_distance = nodes_distances[current_node] + 1
    neighbors = archipelago.get_neighbors(current_node)
    neighbors.each do |neighbor_node|
      already_processed = nodes_distances.has_key?(neighbor_node)
      unless already_processed
        next_nodes.push neighbor_node
        nodes_distances[neighbor_node] = current_neighbor_distance
      end
    end
    if nodes_distances.has_key?(node2)
      return nodes_distances[node2]
    end
  end
  nil
end