Class: DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/etna/directed_graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DirectedGraph

Returns a new instance of DirectedGraph.



2
3
4
5
 
# File 'lib/etna/directed_graph.rb', line 2

def initialize
  @children = {}
  @parents = {}
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



7
8
9
 
# File 'lib/etna/directed_graph.rb', line 7

def children
  @children
end

#parents ⇒ Object (readonly)

Returns the value of attribute parents.



8
9
10
 
# File 'lib/etna/directed_graph.rb', line 8

def parents
  @parents
end

Instance Method Details

#add_connection(parent, child) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
 
# File 'lib/etna/directed_graph.rb', line 10

def add_connection(parent, child)
  children = @children[parent] ||= {}
  child_children = @children[child] ||= {}

  children[child] = child_children

  parents = @parents[child] ||= {}
  parent_parents = @parents[parent] ||= {}
  parents[parent] = parent_parents
end

#descendants(parent) ⇒ Object 



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/etna/directed_graph.rb', line 71

def descendants(parent)
  seen = Set.new

  seen.add(parent)
  queue = @children[parent].keys.dup
  parent_queue = @parents[parent].keys.dup

  # Because this is not an acyclical graph, the definition of descendants needs to be stronger;
  # here we believe that any path that would move through --any-- parent to this child would not be considered
  # descendant, so we first find all those parents and mark them as 'seen' so that they are not traveled.
  while next_parent = parent_queue.pop
    next if seen.include?(next_parent)
    seen.add(next_parent)
    parent_queue.push(*@parents[next_parent].keys)
  end

  queue = queue.nil? ? [] : queue.dup
  paths = {}

  while child = queue.pop
    next if seen.include? child
    seen.add(child)
    path = (paths[child] ||= [parent])

    @children[child].keys.each do |child_child|
      queue.push child_child

      unless paths.include? child_child
        paths[child_child] = path + [child]
      end
    end
  end

  paths
end

#paths_from(root) ⇒ Object 



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/etna/directed_graph.rb', line 50

def paths_from(root)
  [].tap do |result|
    parents_of_map = descendants(root)
    seen = Set.new

    parents_of_map.to_a.sort_by { |k, parents| [-parents.length, k.inspect] }.each do |k, parents|
      unless seen.include?(k)
        if @children[k].keys.empty?
          result << parents + [k]
        else
          @children[k].keys.dup.sort.each do |c|
            result << parents + [k, c]
          end
        end
      end

      parents.each { |p| seen.add(p) }
    end
  end
end

#serialized_path_from(root) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/etna/directed_graph.rb', line 21

def serialized_path_from(root)
  seen = Set.new
  [].tap do |result|
    result << root
    seen.add(root)
    path_q = paths_from(root)

    until path_q.empty?
      next_path = path_q.shift
      next if next_path.nil?

      until next_path.empty?
        next_n = next_path.shift
        next if next_n.nil?
        next if seen.include?(next_n)

        if @parents[next_n].keys.any? { |p| !seen.include?(p) }
          next_path.unshift(next_n)
          path_q.push(next_path)
          break
        else
          result << next_n
          seen.add(next_n)
        end
      end
    end
  end
end