class DR::Graph
Attributes
Public Class Methods
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(:|)
# 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
note: passing a graph won't work
# 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
Public Instance Methods
# 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
alias << build
# File lib/dr/base/graph.rb, line 218 def <<(node, **opts) build(node, **opts) end
# 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 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
# 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
# File lib/dr/base/graph.rb, line 222 def all @nodes.sort end
return all parents
# 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
# File lib/dr/base/graph.rb, line 228 def bottom @nodes.select{ |n| n.children.length == 0}.sort end
build from a list of nodes or hash
# 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
# File lib/dr/base/graph.rb, line 121 def clone Graph.new.build(*all, recursive: false) end
return the connected set containing nodes (following the direction given)
# 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
return all childern
# 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
# 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
# File lib/dr/base/graph.rb, line 117 def each(&b) @nodes.each(&b) end
# File lib/dr/base/graph.rb, line 158 def inspect "#{self.class}: #{map {|x| x.to_s(show_attr: false)}}" end
# File lib/dr/base/graph.rb, line 237 def merge(graph) clone.|(graph) end
allow a hash too
# File lib/dr/base/graph.rb, line 233 def merge!(graph) graph=Graph.new(graph, **{}) unless Graph===graph build(*graph.all, recursive: false) end
# File lib/dr/base/graph.rb, line 128 def names @nodes.map(&:name) end
construct a node (without edges)
# 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
# File lib/dr/base/graph.rb, line 225 def roots @nodes.select{ |n| n.parents.length == 0}.sort end
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
# 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
# File lib/dr/base/graph.rb, line 125 def to_a return @nodes end
alias to_children
to_h
# 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
# 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
# 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
# File lib/dr/base/graph.rb, line 263 def to_nodes(*nodes) nodes.map {|n| self[n]}.compact end
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
# 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
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
# 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