Class: IPXACT::Tools::GraphPathFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/ipxact_tools/graph_pathfinder.rb

Overview

GraphPathFinder instances handle graph-based pathfinding requests within a given IPXACT architecture. It is responsible for translating the IPXACT architecture into a list of connections and transition weights, which may then be queried for optimal paths between two nodes from the connection graph. As such, even though the path finder is pretty generic, it should not be used directly for IPXACT-related work.

Examples:

@pathfinder = IPXACT::Tools::GraphPathFinder.new({
  :nodes => ['component_a', 'component_b', 'component_c']
  :connections =>
    [
      {:link => [0,1]},
      {:link => [1,2], :cost => 2},
      {:link => [2,0]}
    ]
})
@data_path = @pathfinder.resolve('component_a', 'component_b')

Author:

  • Guillaume Godet-Bar

Instance Method Summary collapse

Constructor Details

#initialize(hash) ⇒ GraphPathFinder

The initializer is essentially used for passing a structured connection Hash.

Parameters:

  • hash (Hash) —

    the connection Hash, which should be structured as follows:

    :nodes - An Array of node names (String).

    :connections - An Array of connection elements, which are defined as

    :link - A 2-element Array, which describes an oriented
        connection between two nodes. The nodes are
        expressed using their index in the :nodes
        Array.
:cost - A positive Integer expressing the cost of
        the transition (in the sense of a
        Branch-And-Bound algorithm) (optional,
        default: 1).



58
59
60
 
# File 'lib/ipxact_tools/graph_pathfinder.rb', line 58

def initialize(hash)
  @hash = hash
end

Instance Method Details

#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 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_tools/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