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

note: passing a graph won't work



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

def initialize(*nodes, attributes: {}, infos: nil)
  @nodes=[]
  # a node can be a Hash or a Node
  # so nodes really is a list of subgraphs
  build(*nodes, attributes: 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(:|)



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
 
# File 'lib/dr/base/graph.rb', line 378

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.merge!(g2)
      nodes=nodes.concat(new_nodes)
      new_nodesg.nodes.map(&:name)-nodes
    end
    g
  else
    g
  end
end

Instance Method Details

#-(other) ⇒ Object 



359
360
361
362
363
364
365
366
367
368
369
370
 
# File 'lib/dr/base/graph.rb', line 359

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

alias << build



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

def <<(node, **opts)
  build(node, **opts)
end

#[](node) ⇒ Object 



137
138
139
140
141
142
143
144
145
146
 
# File 'lib/dr/base/graph.rb', line 137

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



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/dr/base/graph.rb', line 180

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 



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

def all
  @nodes.sort
end

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

return all parents



286
287
288
289
 
# File 'lib/dr/base/graph.rb', line 286

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

#bottom ⇒ Object 



228
229
230
 
# File 'lib/dr/base/graph.rb', line 228

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



203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/dr/base/graph.rb', line 203

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 



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

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)



269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
 
# File 'lib/dr/base/graph.rb', line 269

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



291
292
293
294
 
# File 'lib/dr/base/graph.rb', line 291

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 



244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
 
# File 'lib/dr/base/graph.rb', line 244

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 



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

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

#inspect ⇒ Object 



158
159
160
 
# File 'lib/dr/base/graph.rb', line 158

def inspect
  "#{self.class}: #{map {|x| x.to_s(show_attr: false)}}"
end

#merge(graph) ⇒ Object Also known as: + 



237
238
239
 
# File 'lib/dr/base/graph.rb', line 237

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

#merge!(graph) ⇒ Object Also known as: |

allow a hash too



233
234
235
236
 
# File 'lib/dr/base/graph.rb', line 233

def merge!(graph)
  graph=Graph.new(graph, **{}) unless Graph===graph
  build(*graph.all, recursive: false)
end

#names ⇒ Object 



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

def names
  @nodes.map(&:name)
end

#new_node(node, **attributes) ⇒ Object

construct a node (without edges)



166
167
168
169
170
171
172
173
174
175
 
# File 'lib/dr/base/graph.rb', line 166

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 



225
226
227
 
# File 'lib/dr/base/graph.rb', line 225

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



337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
 
# File 'lib/dr/base/graph.rb', line 337

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 



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

def to_a
  return @nodes
end

#to_children ⇒ Object

alias to_children to_h



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

def to_children
  require 'dr/base/converter'
  Converter.to_hash(@nodes, methods:[:children], recursive: true, compact: true).map { |k,v| [k.name, v.map(&:name)]}.to_h
end

#to_h ⇒ Object 



147
148
149
150
 
# File 'lib/dr/base/graph.rb', line 147

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 



132
133
134
135
 
# File 'lib/dr/base/graph.rb', line 132

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 



263
264
265
 
# File 'lib/dr/base/graph.rb', line 263

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



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

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



318
319
320
321
322
323
324
325
 
# File 'lib/dr/base/graph.rb', line 318

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