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

Returns a new instance of Graph.



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

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



361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
 
# File 'lib/dr/base/graph.rb', line 361

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 



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

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

#-(other) ⇒ Object 



342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/dr/base/graph.rb', line 342

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 



131
132
133
134
135
136
137
138
139
140
 
# File 'lib/dr/base/graph.rb', line 131

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



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/dr/base/graph.rb', line 171

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 



208
209
210
 
# File 'lib/dr/base/graph.rb', line 208

def all
	@nodes.sort
end

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

return all parents



269
270
271
272
 
# File 'lib/dr/base/graph.rb', line 269

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

#bottom ⇒ Object 



214
215
216
 
# File 'lib/dr/base/graph.rb', line 214

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



194
195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'lib/dr/base/graph.rb', line 194

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 



119
120
121
 
# File 'lib/dr/base/graph.rb', line 119

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)



252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/dr/base/graph.rb', line 252

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



274
275
276
277
 
# File 'lib/dr/base/graph.rb', line 274

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 



227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/dr/base/graph.rb', line 227

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 



115
116
117
 
# File 'lib/dr/base/graph.rb', line 115

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

#inspect ⇒ Object 



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

def inspect
	"#{self.class}: #{map {|x| x.to_s}}"
end

#new_node(node, **attributes) ⇒ Object

construct a node (without edges)



157
158
159
160
161
162
163
164
165
166
 
# File 'lib/dr/base/graph.rb', line 157

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 



211
212
213
 
# File 'lib/dr/base/graph.rb', line 211

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



320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/dr/base/graph.rb', line 320

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 



123
124
125
 
# File 'lib/dr/base/graph.rb', line 123

def to_a
	return @nodes
end

#to_h ⇒ Object Also known as: to_children 



141
142
143
144
 
# File 'lib/dr/base/graph.rb', line 141

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 



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

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 



246
247
248
 
# File 'lib/dr/base/graph.rb', line 246

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



283
284
285
286
287
288
289
290
291
292
293
294
295
 
# File 'lib/dr/base/graph.rb', line 283

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



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

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



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

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