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