class DR::Graph

Attributes

nodes[RW]

Public Class Methods

build(nodes, recursive: true) { |*nodes| ... } click to toggle source

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
new(*nodes, attributes: {}, infos: nil) click to toggle source

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

+(graph)
Alias for: merge
-(other) click to toggle source
# 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) click to toggle source

alias << build

# File lib/dr/base/graph.rb, line 218
def <<(node, **opts)
  build(node, **opts)
end
[](node) click to toggle source
# 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) click to toggle source

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
all() click to toggle source
# File lib/dr/base/graph.rb, line 222
def all
        @nodes.sort
end
ancestors(*nodes, ourselves: true) click to toggle source

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
bottom() click to toggle source
# 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) click to toggle source

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
clone() click to toggle source
# 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) click to toggle source

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
descendants(*nodes, ourselves: true) click to toggle source

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
dump(mode: :graph, nodes_list: :roots, show_attr: true, out: [], **_opts) click to toggle source
# 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) click to toggle source
# File lib/dr/base/graph.rb, line 117
def each(&b)
        @nodes.each(&b)
end
inspect() click to toggle source
# File lib/dr/base/graph.rb, line 158
def inspect
        "#{self.class}: #{map {|x| x.to_s(show_attr: false)}}"
end
merge(graph) click to toggle source
# File lib/dr/base/graph.rb, line 237
def merge(graph)
        clone.|(graph)
end
Also aliased as: +
merge!(graph) click to toggle source

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
Also aliased as: |
names() click to toggle source
# File lib/dr/base/graph.rb, line 128
def names
        @nodes.map(&:name)
end
new_node(node,**attributes) click to toggle source

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
roots() click to toggle source
# File lib/dr/base/graph.rb, line 225
def roots
        @nodes.select{ |n| n.parents.length == 0}.sort
end
subgraph(*nodes, complement: false) click to toggle source

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
to_a() click to toggle source
# File lib/dr/base/graph.rb, line 125
def to_a
        return @nodes
end
to_children() click to toggle source

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
to_h() click to toggle source
# 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) click to toggle source
# 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) click to toggle source
# File lib/dr/base/graph.rb, line 263
def to_nodes(*nodes)
        nodes.map {|n| self[n]}.compact
end
unneeded(*nodes, needed: nil) click to toggle source

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
unneeded_descendants(*nodes, needed:[]) click to toggle source

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
|(graph)
Alias for: merge!