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 



63
64
65
66
67
68
69
70
71
72
 
# File 'lib/etna/directed_graph.rb', line 63

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

#as_normalized_hash(root, include_root = true) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/etna/directed_graph.rb', line 28

def as_normalized_hash(root, include_root = true)
  q = [root]
  {}.tap do |result|
    if include_root
      result[root] = []
    end

    seen = Set.new

    until q.empty?
      n = q.shift
      next if seen.include?(n)
      seen.add(n)

      parentage = full_parentage(n)

      @children[n].keys.each do |child_node|
        q << child_node

        if result.include?(n)
          result[n] << child_node
        end

        parentage.each do |grandparent|
          result[grandparent] << child_node if result.include?(grandparent)
        end

        result[child_node] = []
      end
    end

    result.values.each(&:uniq!)
  end
end

#descendants(parent, include_root = true) ⇒ Object 



125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/etna/directed_graph.rb', line 125

def descendants(parent, include_root = true)
  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] ||= (include_root ? [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

#full_parentage(n) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/etna/directed_graph.rb', line 10

def full_parentage(n)
  [].tap do |result|
    q = @parents[n].keys.dup
    seen = Set.new

    until q.empty?
      n = q.shift
      next if seen.include?(n)
      seen.add(n)

      result << n
      q.push(*@parents[n].keys)
    end

    result.uniq!
  end
end

#paths_from(root, include_root = true) ⇒ Object 



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/etna/directed_graph.rb', line 104

def paths_from(root, include_root = true)
  [].tap do |result|
    parents_of_map = descendants(root, include_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, include_root = true) ⇒ Object 



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
 
# File 'lib/etna/directed_graph.rb', line 74

def serialized_path_from(root, include_root = true)
  seen = Set.new
  [].tap do |result|
    result << root if include_root
    seen.add(root)
    path_q = paths_from(root, include_root)
    traversables = path_q.flatten

    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) && traversables.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