Class: DR::Graph

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*nodes, attributes: {}, infos: nil) ⇒ Graph 



110
111
112
113
114
 
# File 'lib/dr/base/graph.rb', line 110

def initialize(*nodes, attributes: {}, infos: nil)
  @nodes=[]
  # a node can be a Hash or a Node
  build(*nodes, attributes: {}, infos: infos)
end

Instance Attribute Details

#nodes ⇒ Object

Returns the value of attribute nodes.



108
109
110
 
# File 'lib/dr/base/graph.rb', line 108

def nodes
  @nodes
end

Class Method Details

.build(nodes, recursive: true) ⇒ Object

Graph.build(nodes,&b) allows to build a graph using &b if recursive is true each time we get new nodes we add them to the graph otherwise just run once if recursive=0 we even restrict the graph to the current nodes Note: to construct a graph from one node to a list it suffice to call nodes.map(&b).reduce(:|)



361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
 
# File 'lib/dr/base/graph.rb', line 361

def self.build(nodes, recursive: true)
  g=yield(*nodes)
  g=Graph.new(g) unless g.is_a?(Graph)
  new_nodes=g.nodes.map(&:name)-nodes
  if recursive==0 and !new_nodes.empty?
    g-(new_nodes)
  elsif recursive
    while !new_nodes.empty?
      g2=yield(*new_nodes)
      g2=Graph.new(g2) unless g2.is_a?(Graph)
      g|g2
      nodes=nodes.concat(new_nodes)
      new_nodesg.nodes.map(&:name)-nodes
    end
    g
  else
    g
  end
end

Instance Method Details

#+(graph) ⇒ Object 



223
224
225
 
# File 'lib/dr/base/graph.rb', line 223

def +(graph)
  clone.|(graph)
end

#-(other) ⇒ Object 



342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/dr/base/graph.rb', line 342

def -(other)
  if other.is_a? Graph
    #in this case we want to remove the edges
    other.each do |n|
      self[n].rm_child(*n.children)
    end
  else
    #we remove a list of nodes
    nodes=@nodes-to_nodes(*other)
    subgraph(*nodes)
  end
end

#[](node) ⇒ Object 



131
132
133
134
135
136
137
138
139
140
 
# File 'lib/dr/base/graph.rb', line 131

def [](node)
  if node.is_a?(Node) and node.graph == self
    return node
  elsif node.is_a?(Node)
    name=node.name
  else
    name=node
  end
  @nodes.find {|n| n.name == name}
end

#add_node(node, children: [], parents: [], attributes: {}, infos: nil, recursive: true) ⇒ Object

add a node (and its edges, recursively by default) TODO in case of a loop this is currently non terminating when recursive we would need to keep track of handled nodes



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/dr/base/graph.rb', line 171

def add_node(node, children: [], parents: [], attributes: {}, infos: nil, recursive: true)
  if infos.respond_to?(:call)
    info=infos.call(node)||{}
    children.concat([*info[:children]])
    parents.concat([*info[:parents]])
    attributes.merge!(info[:attributes]||{})
  end
  if node.is_a?(Node) and node.graph != self
    children.concat(node.children)
    parents.concat(node.parents)
  end
  graph_node=new_node(node,**attributes)
  if recursive
    graph_node.add_child(*children.map { |child| add_node(child) })
    graph_node.add_parent(*parents.map { |parent| add_node(parent) })
  else
    #just add the children
    graph_node.add_child(*children.map { |child| new_node(child) })
  end
  graph_node
end

#all ⇒ Object 



208
209
210
 
# File 'lib/dr/base/graph.rb', line 208

def all
  @nodes.sort
end

#ancestors(*nodes, ourselves: true) ⇒ Object

return all parents



269
270
271
272
 
# File 'lib/dr/base/graph.rb', line 269

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

#bottom ⇒ Object 



214
215
216
 
# File 'lib/dr/base/graph.rb', line 214

def bottom
  @nodes.select{ |n| n.children.length == 0}.sort
end

#build(*nodes, attributes: {}, infos: nil, recursive: true) ⇒ Object

build from a list of nodes or hash



194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'lib/dr/base/graph.rb', line 194

def build(*nodes, attributes: {}, infos: nil, recursive: true)
  nodes.each do |node|
    case node
    when Hash
      node.each do |name,children|
        add_node(name,children: [*children], attributes: attributes, infos: infos, recursive: recursive)
      end
    else
      add_node(node, attributes: attributes, infos: infos, recursive: recursive)
    end
  end
  self
end

#clone ⇒ Object 



119
120
121
 
# File 'lib/dr/base/graph.rb', line 119

def clone
  Graph.new.build(*all, recursive: false)
end

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

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



252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/dr/base/graph.rb', line 252

def connected(*nodes, down:true, up:true, ourselves: true)
  nodes=to_nodes(*nodes)
  onodes=nodes.dup
  found=[]
  while !nodes.empty?
    node=nodes.shift
    found<<node
    new_nodes=Set[node]
    new_nodes.merge(node.children) if down
    new_nodes.merge(node.parents) if up
    new_nodes-=(found+nodes)
    nodes.concat(new_nodes.to_a)
  end
  found-=onodes if !ourselves
  return found
end

#descendants(*nodes, ourselves: true) ⇒ Object

return all childern



274
275
276
277
 
# File 'lib/dr/base/graph.rb', line 274

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

#dump(mode: :graph, nodes_list: :roots, show_attr: true, out: [], **_opts) ⇒ Object 



227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/dr/base/graph.rb', line 227

def dump(mode: :graph, nodes_list: :roots, show_attr: true, out: [], **_opts)
  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
  case mode
  when :graph; n.each do |node| node.to_graph(show_attr: show_attr, out: out) end
  when :list; n.each do |i| out << "- #{i}" end
  when :dot;
    out << "digraph gems {"
    #out << n.map {|node| node.to_dot}.inject(:+).uniq!.join("\n")
    n.map {|node| node.to_dot(out: out)}
    out << "}"
  end
  return out
end

#each(&b) ⇒ Object 



115
116
117
 
# File 'lib/dr/base/graph.rb', line 115

def each(&b)
  @nodes.each(&b)
end

#inspect ⇒ Object 



152
153
154
 
# File 'lib/dr/base/graph.rb', line 152

def inspect
  "#{self.class}: #{map {|x| x.to_s}}"
end

#new_node(node, **attributes) ⇒ Object

construct a node (without edges)



157
158
159
160
161
162
163
164
165
166
 
# File 'lib/dr/base/graph.rb', line 157

def new_node(node,**attributes)
  n=case node
  when Node
    node.graph == self ? node : new_node(node.name, **node.attributes)
  else
    @nodes.find {|n| n.name == node} || Node.new(node, graph: self)
  end
  n.update_attributes(attributes)
  n
end

#roots ⇒ Object 



211
212
213
 
# File 'lib/dr/base/graph.rb', line 211

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

#subgraph(*nodes, complement: false) ⇒ 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 [missing edges] in case the components are connected



320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/dr/base/graph.rb', line 320

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

#to_a ⇒ Object 



123
124
125
 
# File 'lib/dr/base/graph.rb', line 123

def to_a
  return @nodes
end

#to_h ⇒ Object Also known as: to_children 



141
142
143
144
 
# File 'lib/dr/base/graph.rb', line 141

def to_h
  h=to_hash(methods: [:children])
  Hash[h.map {|k,v| [k.name, v.map(&:name)]}]
end

#to_hash(methods: [:children,:parents,:attributes], compact: true, recursive: true) ⇒ Object 



126
127
128
129
 
# File 'lib/dr/base/graph.rb', line 126

def to_hash(methods: [:children,:parents,:attributes], compact: true, recursive: true)
  require 'dr/base/converter'
  Converter.to_hash(@nodes, methods: methods, recursive: recursive, compact: compact)
end

#to_nodes(*nodes) ⇒ Object 



246
247
248
 
# File 'lib/dr/base/graph.rb', line 246

def to_nodes(*nodes)
  nodes.map {|n| self[n]}.compact
end

#unneeded(*nodes, needed: nil) ⇒ Object

from a list of nodes, return all nodes that are not descendants of other nodes in the graph needed: the nodes whose descendants we keep, by default the complement of nodes



283
284
285
286
287
288
289
290
291
292
293
294
295
 
# File 'lib/dr/base/graph.rb', line 283

def unneeded(*nodes, needed: nil)
  nodes=to_nodes(*nodes)
  if needed
    needed=to_nodes(needed)
  else
    needed=@nodes-nodes
  end
  unneeded=[]
  nodes.each do |node|
    unneeded << node if (ancestors(node) & needed).empty?
  end
  unneeded
end

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

like unneeded(descendants(*nodes)) return all dependencies that are not needed by any more other nodes (except the ones we are removing) If some dependencies should be kept (think manual install), add them to the needed parameter



301
302
303
304
305
306
307
308
 
# File 'lib/dr/base/graph.rb', line 301

def unneeded_descendants(*nodes, needed:[])
  nodes=to_nodes(*nodes)
  needed=to_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

#|(graph) ⇒ Object

allow a hash too



219
220
221
222
 
# File 'lib/dr/base/graph.rb', line 219

def |(graph)
  graph=Graph.new(graph) unless Graph===graph
  build(*graph.all, recursive: false)
end