Class: HierarchicalGraph

Inherits:
Object
  • Object
show all
Includes:
Enumerable, TSort
Defined in:
lib/hierarchical_graph.rb,
lib/hierarchical_graph/node.rb,
lib/hierarchical_graph/version.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

VERSION = 
'1.0.2'

Instance Method Summary collapse

Constructor Details

#initialize ⇒ HierarchicalGraph

Returns a new instance of HierarchicalGraph.



9
10
11
12
13
14
15
 
# File 'lib/hierarchical_graph.rb', line 9

def initialize
  @nodes = {}
  @parent_to_children = {}
  @child_to_parents = {}
  @ancestors_cache = {}
  @descendants_cache = {}
end

Instance Method Details

#[](id) ⇒ Object 



17
18
19
 
# File 'lib/hierarchical_graph.rb', line 17

def [](id)
  nodes[id]
end

#add_node(id, attributes = {}) ⇒ Object 



33
34
35
36
37
38
39
40
 
# File 'lib/hierarchical_graph.rb', line 33

def add_node(id, attributes={})
  validate_not_present! id

  clear_cache
  parent_to_children[id] = Set.new
  child_to_parents[id] = Set.new
  nodes[id] = Node.new self, id, attributes
end

#add_relation(parent_id:, child_id:) ⇒ Object 



57
58
59
60
61
62
63
64
65
 
# File 'lib/hierarchical_graph.rb', line 57

def add_relation(parent_id:, child_id:)
  validate_present! parent_id, child_id

  clear_cache
  parent_to_children[parent_id] << child_id
  child_to_parents[child_id] << parent_id

  nil
end

#ancestors_of(id) ⇒ Object 



89
90
91
92
93
94
95
 
# File 'lib/hierarchical_graph.rb', line 89

def ancestors_of(id)
  validate_present! id

  ancestors_cache[id] ||= parents_of(id).flat_map do |parent|
    ancestors_of(parent.id) + [parent]
  end.uniq(&:id)
end

#children_of(id) ⇒ Object 



83
84
85
86
87
 
# File 'lib/hierarchical_graph.rb', line 83

def children_of(id)
  validate_present! id

  parent_to_children[id].map { |node_id| nodes[node_id] }
end

#descendants_of(id) ⇒ Object 



97
98
99
100
101
102
103
 
# File 'lib/hierarchical_graph.rb', line 97

def descendants_of(id)
  validate_present! id

  children_of(id).flat_map do |child|
    [child] + descendants_of(child.id)
  end.uniq(&:id)
end

#each(&block) ⇒ Object 



21
22
23
 
# File 'lib/hierarchical_graph.rb', line 21

def each(&block)
  nodes.each_value(&block)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


25
26
27
 
# File 'lib/hierarchical_graph.rb', line 25

def empty?
  nodes.empty?
end

#parents_of(id) ⇒ Object 



77
78
79
80
81
 
# File 'lib/hierarchical_graph.rb', line 77

def parents_of(id)
  validate_present! id

  child_to_parents[id].map { |node_id| nodes[node_id] }
end

#remove_node(id) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/hierarchical_graph.rb', line 42

def remove_node(id)
  validate_present! id

  parent_to_children[id].each { |child_id| child_to_parents[child_id].delete id }
  child_to_parents[id].each { |parent_id| parent_to_children[parent_id].delete id }

  parent_to_children.delete id
  child_to_parents.delete id

  nodes.delete id
  clear_cache

  nil
end

#remove_relation(parent_id:, child_id:) ⇒ Object 



67
68
69
70
71
72
73
74
75
 
# File 'lib/hierarchical_graph.rb', line 67

def remove_relation(parent_id:, child_id:)
  validate_present! parent_id, child_id

  clear_cache
  parent_to_children[parent_id].delete child_id
  child_to_parents[child_id].delete parent_id

  nil
end

#roots ⇒ Object 



29
30
31
 
# File 'lib/hierarchical_graph.rb', line 29

def roots
  select(&:root?)
end

#to_s ⇒ Object Also known as: inspect 



105
106
107
 
# File 'lib/hierarchical_graph.rb', line 105

def to_s
  "<#{self.class.name} nodes:[#{map(&:to_s).join(', ')}]>"
end