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