Method: IPXACT::GraphPathFinder#resolve

Defined in:
lib/ipxact/pathfinder/graph_pathfinder.rb

#resolve(start, _end) ⇒ Array<Integer>

Searches an optimal path between the start and _end elements, which should be defined in the Hash structured used for instanciating the IPXACT::GraphPathFinder instance. Optimal should be understood as “the cheapest path given the cost of each connection”. Additionally, validates the latter Hash structure before executing the search algorithm.

Parameters:

  • start (String) —

    a String that corresponds to an element that was registered when the pathfinder was created. The latter will be used as the start node by the pathfinder algorithm.

  • _end (String) —

    a String that corresponds to an element that was registered when the pathfinder was created. The latter will be used as the target node by the pathfinder algorithm.

Returns:

  • (Array<Integer>) —

    an Array of Integers corresponding to connection indices for the optimal data path between the start and _end elements, or an empty Array if the start and _end elements are identical.

Raises:

  • an exception if the Hash structure for the connections is empty.

  • an exception unless all the node names are unique.

  • an exception if the start or end element does not exist.

  • an exception if no optimal data path could be found.



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/ipxact/pathfinder/graph_pathfinder.rb', line 85

def resolve(start, _end)
  raise "Empty connection table!" if @hash.empty?
  return [] if start == _end
  raise "Duplicate connection node found!" if @hash[:nodes].uniq.size != @hash[:nodes].size
  raise "The source or target node does not exist!" unless @hash[:nodes].include?(start) && @hash[:nodes].include?(_end)

  @interconnect_table = (0..@hash[:nodes].size - 1).collect do |i|
    (0..@hash[:nodes].size - 1).collect do |j|
      result_hash = { 
        :connection =>
          @hash[:connections].any?{|connection| connection[:link] == [j,i]},
        :total => Float::INFINITY,
        :previous => nil
      }
      if @hash[:connections].any?{|connection| connection[:link] == [j,i]}
        result = @hash[:connections].select{|connection| connection[:link] == [j,i]}.first[:cost] || 1
        result_hash.merge!({:cost => result})
      end

      result_hash
    end
  end

  start_index = @hash[:nodes].index(start)
  end_index = @hash[:nodes].index(_end)
  @interconnect_table[start_index][start_index][:total] = 0


  rec_resolve([start_index, start_index], end_index, 0)

  last_writer_index = nil
  @interconnect_table[end_index].each_with_index do |el, i|
    last_writer_index = i if el[:total] < Float::INFINITY
  end
  raise "Destination could not be reached!" if last_writer_index.nil?
  
  
  dump_trajectory(end_index).reverse

end