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 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/etna/directed_graph.rb', line 42

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 



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/etna/directed_graph.rb', line 21

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] }.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