class BlifUtils::NetlistGraph::Graph
Attributes
fromModel[R]
vertices[RW]
Public Class Methods
create_from_model(model)
click to toggle source
# 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
new(vertices = [], model = nil)
click to toggle source
# File lib/blifutils/layering.rb, line 31 def initialize (vertices = [], model = nil) @vertices = vertices @fromModel = model check unless @vertices.empty? end
Private Class Methods
get_connected_vertices_recursive(vertice, newDAGvertices, verticePool)
click to toggle source
# File lib/blifutils/layering.rb, line 256 def self.get_connected_vertices_recursive (vertice, newDAGvertices, verticePool) return if newDAGvertices.include?(vertice) newDAGvertices << vertice raise 'Mah! Que passa ?' unless verticePool.include?(vertice) verticePool.delete(vertice) vertice.predecessors.each do |predecessor| BlifUtils::NetlistGraph::Graph.get_connected_vertices_recursive(predecessor, newDAGvertices, verticePool) end vertice.successors.each do |successor| BlifUtils::NetlistGraph::Graph.get_connected_vertices_recursive(successor, newDAGvertices, verticePool) end end
Public Instance Methods
assign_layers_to_vertices()
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# 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?()
click to toggle source
# 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()
click to toggle source
# 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