class ExoBasic::DFS
Public Class Methods
get_available(node, others, edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 68 def self.get_available(node, others, edges_map) to_search = Set.new(others) for i in to_search.to_a if to_search.include?(i) found = DFS.search_helper!(node, i, [], Set.new, edges_map) if found to_remove = Set.new(found) to_search -= to_remove end end end to_search end
has_loop(node, edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 57 def self.has_loop(node, edges_map) !DFS.has_loop_helper(node, edges_map).empty? end
has_loop_helper(node, edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 36 def self.has_loop_helper(node, edges_map) children = edges_map[node] visited = Set.new found = false found_path = [] if children.nil? [] else for i in children if !visited.include?(i) found = DFS.search_helper!(node, i, [node], visited, edges_map) if found found_path = found break end end end found_path end end
loop_map(edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 61 def self.loop_map(edges_map) edges_map.keys.map do |node| [node, DFS.has_loop_helper(node, edges_map)] end .to_h end
search(to, from, edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 32 def self.search(to, from, edges_map) DFS.search_helper!(to, from, [], Set.new, edges_map) end
search_helper!(target, curr, path, visited, edges_map)
click to toggle source
# File lib/exobasic/data/dfs.rb, line 5 def self.search_helper!(target, curr, path, visited, edges_map) children = edges_map[curr] visited.add(curr) path.push(curr) if target == curr path else found = false if !children.nil? for i in children if !visited.include?(i) found = DFS.search_helper!(target, i, path, visited, edges_map) if found break end end end end if !found path.pop end found end end