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_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