Module: Legion::Extensions::Agentic::Integration::Map::Helpers::GraphTraversal

Defined in:
lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb

Class Method Summary collapse

Class Method Details

.bfs_component(locations, start, visited, component) ⇒ Object 



105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 105

def bfs_component(locations, start, visited, component)
  queue = [start]
  while (current = queue.shift)
    next if visited[current]

    visited[current] = true
    component << current
    loc = locations[current]
    next unless loc

    loc.neighbors.each_key { |nid| queue << nid unless visited[nid] }
  end
end

.bfs_reachable(locations, start, max_distance) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 30

def bfs_reachable(locations, start, max_distance)
  visited = { start => 0.0 }
  queue = [[0.0, start]]
  reachable = []

  until queue.empty?
    dist, current = queue.min_by { |d, _| d }
    queue.delete([dist, current])
    next if dist > max_distance

    reachable << { id: current, distance: dist.round(4) } unless current == start
    expand_neighbors(locations, current, dist, max_distance, visited, queue)
  end

  reachable.sort_by { |r| r[:distance] }
end

.build_path_result(_locations, prev, from, to, cost) ⇒ Object 



74
75
76
77
78
79
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 74

def build_path_result(_locations, prev, from, to, cost)
  return { found: false, reason: :no_path } if cost == Float::INFINITY

  path = reconstruct_path(prev, from, to)
  path.empty? ? { found: false, reason: :no_path } : { found: true, path: path, distance: cost.round(4) }
end

.connected_components(locations) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 47

def connected_components(locations)
  visited = {}
  components = []
  locations.each_key do |id|
    next if visited[id]

    component = []
    bfs_component(locations, id, visited, component)
    components << component
  end
  components
end

.dijkstra(locations, from, to) ⇒ Object 



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 12

def dijkstra(locations, from, to)
  dist = Hash.new(Float::INFINITY)
  prev = {}
  dist[from] = 0.0
  queue = [[0.0, from]]

  until queue.empty?
    d, u = queue.min_by { |x, _| x }
    queue.delete([d, u])
    break if u == to
    next if d > dist[u]

    relax_edges(locations, u, dist, prev, queue)
  end

  build_path_result(locations, prev, from, to, dist[to])
end

.expand_neighbors(locations, current, dist, max_distance, visited, queue) ⇒ Object 



91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 91

def expand_neighbors(locations, current, dist, max_distance, visited, queue)
  loc = locations[current]
  return unless loc

  loc.neighbors.each do |nid, edge_dist|
    new_dist = dist + edge_dist
    next if new_dist > max_distance
    next if visited.key?(nid) && visited[nid] <= new_dist

    visited[nid] = new_dist
    queue << [new_dist, nid]
  end
end

.reconstruct_path(prev, from, to) ⇒ Object 



81
82
83
84
85
86
87
88
89
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 81

def reconstruct_path(prev, from, to)
  path = []
  current = to
  while current
    path.unshift(current)
    current = prev[current]
  end
  path.first == from ? path : []
end

.relax_edges(locations, node, dist, prev, queue) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/legion/extensions/agentic/integration/map/helpers/graph_traversal.rb', line 60

def relax_edges(locations, node, dist, prev, queue)
  loc = locations[node]
  return unless loc

  loc.neighbors.each do |v, weight|
    alt = dist[node] + weight
    next unless alt < dist[v]

    dist[v] = alt
    prev[v] = node
    queue << [alt, v]
  end
end