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

Returns a new instance of Graph.



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

def initialize(*nodes, attributes: {}, infos: nil)
  @nodes=[]
  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(:|)



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

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 



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

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

#-(other) ⇒ Object 



339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/dr/base/graph.rb', line 339

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 



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

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



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

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 



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

def all
  @nodes.sort
end

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

return all parents



266
267
268
269
 
# File 'lib/dr/base/graph.rb', line 266

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

#bottom ⇒ Object 



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

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



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

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 



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

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)



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

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



271
272
273
274
 
# File 'lib/dr/base/graph.rb', line 271

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, **unused) ⇒ Object 



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

def dump(mode: :graph, nodes_list: :roots, show_attr: true, **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(show_attr: show_attr) 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(&b) ⇒ Object 



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

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

#inspect ⇒ Object 



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

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

#new_node(node, **attributes) ⇒ Object

construct a node (without edges)



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

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 



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

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



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

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 



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

def to_a
  return @nodes
end

#to_h ⇒ Object Also known as: to_children 



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

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 



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

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 



243
244
245
 
# File 'lib/dr/base/graph.rb', line 243

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



280
281
282
283
284
285
286
287
288
289
290
291
292
 
# File 'lib/dr/base/graph.rb', line 280

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



298
299
300
301
302
303
304
305
 
# File 'lib/dr/base/graph.rb', line 298

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 



217
218
219
 
# File 'lib/dr/base/graph.rb', line 217

def |(graph)
  build(*graph.all, recursive: false)
end