Class: DR::Graph

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/drain/base/graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(g = nil) ⇒ Graph

Returns a new instance of Graph.



85
86
87
88
89
90
91
92
93
 
# File 'lib/drain/base/graph.rb', line 85

def initialize(g=nil)
  @nodes=[]
  if g #convert a hash to a graph
    g.each do |name,children|
      n=build(name)
      n.add_child(*children)
    end
  end
end

Instance Attribute Details

#nodes ⇒ Object

Returns the value of attribute nodes.



83
84
85
 
# File 'lib/drain/base/graph.rb', line 83

def nodes
  @nodes
end

Instance Method Details

#all ⇒ Object 



117
118
119
 
# File 'lib/drain/base/graph.rb', line 117

def all
  @nodes.sort
end

#ancestors(*nodes) ⇒ Object

return all parents



157
158
159
 
# File 'lib/drain/base/graph.rb', line 157

def ancestors(*nodes)
  connected(*nodes, up:true, down:false)
end

#build(node, children: [], parents: [], **keywords) ⇒ Object 



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/drain/base/graph.rb', line 94

def build(node, children: [], parents: [], **keywords)
  graph_node=
  case node
  when Node
    match = @nodes.find {|n| n == node} and return match
    Node.new(node.name, graph: self, **keywords.merge({attributes: node.attributes||keywords[:attributes]}))
    node.children.each do |c|
      build(c,**keywords)
    end
  else
    match = @nodes.find {|n| n.name == node}
    match || Node.new(node, graph: self, **keywords)
  end
  graph_node.add_child(*children.map { |child| build(child) })
  graph_node.add_parent(*parents.map { |child| build(child) })
  return graph_node
end

#connected(*nodes, down: true, up: true) ⇒ Object

return the connected set containing nodes (following the direction given)



144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/drain/base/graph.rb', line 144

def connected(*nodes, down:true, up:true)
  r=Set.new()
  nodes.each do |node|
    unless r.include?(node)
      new_nodes=Set.new()
      new_nodes.merge(node.children) if down
      new_nodes.merge(node.parents) if up
      r.merge(connected(*new_nodes, down:down,up:up))
    end
  end
  return r
end

#descendants(*nodes) ⇒ Object

return all childern



161
162
163
 
# File 'lib/drain/base/graph.rb', line 161

def descendants(*nodes)
  connected(*nodes, up:false, down:true)
end

#dump(mode: :graph, nodes_list: :roots, **unused) ⇒ Object 



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/drain/base/graph.rb', line 123

def dump(mode: :graph, nodes_list: :roots, **unused)
  n=case nodes_list
    when :roots; roots
    when :all; all
    when Symbol; nodes.select {|n| n.attributes[:nodes_list]}
    else nodes_list.to_a
  end
  sout = ""
  case mode
  when :graph; n.each do |node| sout+=node.to_graph end
  when :list; n.each do |i| sout+="- #{i}\n" end
  when :dot;
    sout+="digraph gems {\n"
    sout+=n.map {|node| node.to_dot}.inject(:+).uniq!.join("\n")
    sout+="}\n"
  end
  return sout
end

#each ⇒ Object 



111
112
113
 
# File 'lib/drain/base/graph.rb', line 111

def each
  @nodes.each
end

#roots ⇒ Object 



120
121
122
 
# File 'lib/drain/base/graph.rb', line 120

def roots
  @nodes.select{ |n| n.parents.length == 0}.sort
end

#subgraph(*nodes) ⇒ Object

return the subgraph containing all the nodes passed as parameters, and the complementary graph. The union of both may not be the full graph [edges] in case the components are not connected



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
# File 'lib/drain/base/graph.rb', line 193

def subgraph(*nodes)
  subgraph=Graph.new()
  compgraph=Graph.new()
  @nodes.each do |node|
    if nodes.include?(node)
      n=subgraph.build(node.name)
      node.children.each do |c|
        n.add_child(c) if nodes.include?(c)
      end
    else
      n=compgraph.build(node.name)
      node.children.each do |c|
        n.add_child(c) unless nodes.include?(c)
      end
    end
  end
  return subgraph, compgraph
end

#to_a ⇒ Object 



114
115
116
 
# File 'lib/drain/base/graph.rb', line 114

def to_a
  return @nodes
end

#unneeded(*nodes) ⇒ Object

from a list of nodes, return all nodes that are not descendants of other nodes in the graph



167
168
169
170
171
172
 
# File 'lib/drain/base/graph.rb', line 167

def unneeded(*nodes)
  tokeep.merge(@nodes-nodes)
  nodes.each do |node|
    unneeded << node unless ancestors(node).any? {|c| tokeep.include?(c)}
  end
end

#unneeded_descendants(*nodes, needed: []) ⇒ Object

return all dependencies that are not needed by any more nodes. If some dependencies should be kept (think manual install), add them to the unneeded parameter



176
177
178
179
180
181
 
# File 'lib/drain/base/graph.rb', line 176

def unneeded_descendants(*nodes, needed:[])
  needed-=nodes #nodes to delete are in priority
  deps=descendants(*nodes)
  deps-=needed #but for children nodes, needed nodes are in priority
  unneeded(*deps)
end