Class: BlifUtils::NetlistGraph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/blifutils/layering.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(vertices = [], model = nil) ⇒ Graph

Returns a new instance of Graph.



31
32
33
34
35
 
# File 'lib/blifutils/layering.rb', line 31

def initialize (vertices = [], model = nil)
	@vertices = vertices
	@fromModel = model
	check unless @vertices.empty?
end

Instance Attribute Details

#fromModel ⇒ Object (readonly)

Returns the value of attribute fromModel.



29
30
31
 
# File 'lib/blifutils/layering.rb', line 29

def fromModel
  @fromModel
end

#vertices ⇒ Object

Returns the value of attribute vertices.



28
29
30
 
# File 'lib/blifutils/layering.rb', line 28

def vertices
  @vertices
end

Class Method Details

.create_from_model(model) ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/blifutils/layering.rb', line 86

def self.create_from_model (model)
	vertices = BlifUtils::NetlistGraph::Vertice.get_vertices_from_model(model)
	###vertices.each{|ver| puts "#{ver.component} #{ver.component.class.name} #{ver.component.label}"}
	# Update successors and predecessors references to components by references to Vertices
	vertices.each do |vertice|
		(0 ... vertice.successors.length).each do |i|
			next if vertice.successors[i] == :output
			successorVertice = vertices.select{|vever| vever.component == vertice.successors[i]}
			if successorVertice.empty? then
				abort "ERROR: While elaborating netlist graph: successor #{vertice.successors[i]} of component #{vertice.component} has no reference in the graph."
			end
			if successorVertice.length > 1 then
				abort "ERROR: While elaborating netlist graph: successor #{vertice.successors[i]} of component #{vertice.component} has more than one reference in the graph."
			end
			vertice.successors[i] = successorVertice[0]
		end
		(0 ... vertice.predecessors.length).each do |i|
			next if vertice.predecessors[i] == :input
			predecessorVertice = vertices.select{|vever| vever.component == vertice.predecessors[i]}
			if predecessorVertice.empty? then
				abort "ERROR: While elaborating netlist graph: predecessor #{vertice.predecessors[i]} of component #{vertice.component} has no reference in the graph."
			end
			if predecessorVertice.length > 1 then
				abort "ERROR: While elaborating netlist graph: predecessor #{vertice.predecessors[i]} of component #{vertice.component} has more than one reference in the graph."
			end
			vertice.predecessors[i] = predecessorVertice[0]
		end
	end
	newGraph = BlifUtils::NetlistGraph::Graph.new(vertices, model)
	return newGraph
end

Instance Method Details

#assign_layers_to_vertices ⇒ Object 



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
 
# File 'lib/blifutils/layering.rb', line 224

def assign_layers_to_vertices
	@vertices.each{|vertice| vertice.layer = nil}
	v_remainder_set = @vertices.collect{|vert| vert}
	u_new_set = []
	u_set_length = 0
	z_set = []
	currentLayer = 1
	while u_set_length != @vertices.length do
		selectedVertice = nil
		v_remainder_set.each do |vertice| 
			unless vertice.successors.collect{|suc| suc.layer != nil and suc.layer < currentLayer}.include?(false)
				selectedVertice = vertice
				break
			end
		end
		if selectedVertice.nil? then
			currentLayer += 1
			z_set += u_new_set
			u_new_set = []
		else
			selectedVertice.layer = currentLayer	
			u_set_length += 1
			u_new_set << selectedVertice
			v_remainder_set.delete(selectedVertice)
		end
	end
end

#check ⇒ Object 



147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
 
# File 'lib/blifutils/layering.rb', line 147

def check
	# Check that each component is in only one vertice
	allComponents = @vertices.collect{|vertice| vertice.component}
	allComponents.each do |component|
		if allComponents.select{|compo| compo == component}.length > 1 then
			abort "ERROR: Checking graph: component #{component} has more than one corresponding vertice."
		end
	end

	@vertices.each do |vertice|
		# Check that each successor has the current vertice as predecessor
		vertice.successors.each do |successor|
			next if successor == :output
			predecessorVertices = successor.predecessors.select{|prede| prede == vertice}
			if predecessorVertices.empty? then
				abort "ERROR: While elaborating netlist graph: successor #{successor.component} of component #{vertice.component} has no reference to component #{vertice.component} as predecessor."
			end
			if predecessorVertices.length > 1 then
				abort "ERROR: While elaborating netlist graph: successor #{successor.component} of component #{vertice.component} has more than one reference to component #{vertice.component} as predecessor."
			end
		end

		# Check that each predecessor has the current vertice as successor
		vertice.predecessors.each do |predecessor|
			next if predecessor == :input
			successorVertices = predecessor.successors.select{|succe| succe == vertice}
			if successorVertices.empty? then
				abort "ERROR: While elaborating netlist graph: predecessor #{predecessor.component} of component #{vertice.component} has no reference to component #{vertice.component} as successor."
			end
			if successorVertices.length > 1 then
				abort "ERROR: While elaborating netlist graph: predecessor #{predecessor.component} of component #{vertice.component} has more than one reference to component #{vertice.component} as successor."
			end
		end
	end
end

#clone ⇒ Object 



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/blifutils/layering.rb', line 54

def clone
	vertices = @vertices.collect{|vertice| vertice.clone}
	# Update successors and predecessors references to cloned vertices
	vertices.each do |vertice|
		(0 ... vertice.successors.length).each do |i|
			next if vertice.successors[i] == :output
			successorVertice = vertices.select{|vever| vever.component == vertice.successors[i].component}
			if successorVertice.empty? then
				abort "ERROR: While cloning netlist graph: successor #{vertice.successors[i].component} of component #{vertice.component} has no reference in the graph."
			end
			if successorVertice.length > 1 then
				abort "ERROR: While cloning netlist graph: successor #{vertice.successors[i].component} of component #{vertice.component} has more than one reference in the graph."
			end
			vertice.successors[i] = successorVertice[0]
		end
		(0 ... vertice.predecessors.length).each do |i|
			next if vertice.predecessors[i] == :input
			predecessorVertice = vertices.select{|vever| vever.component == vertice.predecessors[i].component}
			if predecessorVertice.empty? then
				abort "ERROR: While cloning netlist graph: predecessor #{vertice.predecessors[i].component} of component #{vertice.component} has no reference in the graph."
			end
			if predecessorVertice.length > 1 then
				abort "ERROR: While cloning netlist graph: predecessor #{vertice.predecessors[i].component} of component #{vertice.component} has more than one reference in the graph."
			end
			vertice.predecessors[i] = predecessorVertice[0]
		end
	end
	newGraph = BlifUtils::NetlistGraph::Graph.new(vertices, @fromModel)
	return newGraph
end

#get_connected_subgraphs ⇒ Object 



184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/blifutils/layering.rb', line 184

def get_connected_subgraphs
	dags = []

	verticePool = @vertices.collect{|vert| vert}

	until verticePool.empty? do
		newDAGvertices = []
		# Pick up a vertice
		BlifUtils::NetlistGraph::Graph.get_connected_vertices_recursive(verticePool[0], newDAGvertices, verticePool)
		dags << BlifUtils::NetlistGraph::Graph.new(newDAGvertices, @fromModel)
	end

	return dags
end

#get_graph_without_input_output_reg_cst_modinst ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/blifutils/layering.rb', line 38

def get_graph_without_input_output_reg_cst_modinst
	newGraph = clone
	newGraph.vertices.delete_if do |vertice|
		vertice.component == :input or
			vertice.component == :output or
			vertice.component.class == BlifUtils::Netlist::SubCircuit or
			vertice.component.class == BlifUtils::Netlist::Latch or
			(vertice.component.class == BlifUtils::Netlist::LogicGate and vertice.component.is_constant?)
	end
	newGraph.vertices.each do |vertice|
		vertice.remove_input_output_reg_cst_modinst_references
	end
	return newGraph
end

#is_acyclic? ⇒ Boolean

Returns:

  • (Boolean) 


200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/blifutils/layering.rb', line 200

def is_acyclic?
	# If a directed graph is acyclic, it has at least a node with no successors,
	# if there is no such node, the graph cannot be acyclic.
	# If we remove a node with no successors, the graph is still acyclic as it leaves new nodes without successors

	# We make a copy of the graph as we will modigy it and its nodes
	graph = self.clone

	until graph.vertices.empty? do
		# Find a leaf, e.g. a node with no successors
		leafs = graph.vertices.select{|vertice| vertice.successors.empty?}
		return false if leafs.empty?
		# Remove the leaf from the graph
		leaf = leafs[0]
		graph.vertices.delete(leaf)
		leaf.predecessors.each do |predecessor|
			predecessor.successors.delete(leaf)
		end
	end

	return true
end

#to_graphviz ⇒ Object 



119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/blifutils/layering.rb', line 119

def to_graphviz
	@vertices.each_with_index{|vert, i| vert.id = i}
	str = "digraph #{@fromModel.nil? ? '' : @fromModel.name} {\n"
	@vertices.each do |vertice|
		str += "\t#{vertice.id} [label=\"#{vertice.to_s}\""
		if vertice.component == :input or
				vertice.component == :output or
				vertice.component.class == BlifUtils::Netlist::Latch or
				(vertice.component.class == BlifUtils::Netlist::LogicGate and vertice.component.is_constant?) then
			str += ",shape=box"
		end
		str += "];\n"
	end
	@vertices.each do |vertice|
		vertice.successors.each do |successor|
			next if successor.class == Symbol
			str += "\t#{vertice.id} -> "
			str += "#{successor.id};\n"
		end
		if vertice.successors.empty? and vertice.predecessors.empty? then
			str += "\t#{vertice.id};\n"
		end
	end
	str += "}\n"
	return str
end