Class: ExoBasic::DFS

Inherits:
Object
  • Object
show all
Defined in:
lib/exobasic/data/dfs.rb

Class Method Summary collapse

Class Method Details

.get_available(node, others, edges_map) ⇒ Object 



68
69
70
71
72
73
74
75
76
77
78
79
80
 
# 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) ⇒ Object 



57
58
59
 
# 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) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# 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) ⇒ Object 



61
62
63
64
65
66
 
# 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) ⇒ Object 



32
33
34
 
# 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) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# 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