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(:|)



370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/dr/base/graph.rb', line 370

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 



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

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

#-(other) ⇒ Object 



351
352
353
354
355
356
357
358
359
360
361
362
 
# File 'lib/dr/base/graph.rb', line 351

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 



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 



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

def all
	@nodes.sort
end

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

return all parents



278
279
280
281
 
# File 'lib/dr/base/graph.rb', line 278

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

#bottom ⇒ Object 



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

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)



261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
 
# File 'lib/dr/base/graph.rb', line 261

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



283
284
285
286
 
# File 'lib/dr/base/graph.rb', line 283

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 



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'lib/dr/base/graph.rb', line 236

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

#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 



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

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



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
 
# File 'lib/dr/base/graph.rb', line 329

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 



255
256
257
 
# File 'lib/dr/base/graph.rb', line 255

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



292
293
294
295
296
297
298
299
300
301
302
303
304
 
# File 'lib/dr/base/graph.rb', line 292

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



310
311
312
313
314
315
316
317
 
# File 'lib/dr/base/graph.rb', line 310

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

allow a hash too



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

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