edu.byu.ece.edif.util.graph
Class EdifCellInstanceGraph

java.lang.Object
  extended by edu.byu.ece.graph.AbstractGraph
      extended by edu.byu.ece.graph.BasicGraph
          extended by edu.byu.ece.edif.util.graph.AbstractEdifGraph
              extended by edu.byu.ece.edif.util.graph.EdifCellInstanceGraph
All Implemented Interfaces:
DirectedGraph, java.io.Serializable, java.lang.Cloneable

public class EdifCellInstanceGraph
extends AbstractEdifGraph

Provides a mathematical graph view of an EdifCell. This graph view of the EdifCell includes Node objects for each top-level port (EdifSingleBitPort) and each sub-cell (EdifCellInstance). The edges between these nodes are represented as EdifCellInstanceEdge objects. These objects represent an edge as a connection between a source EdifPortRef object and a sink EdifPortRef object.

This graph structure creates a single node for each EdifCellInstance object and makes the assumption of full connectivity between each of the input ports of a EdifCellInstance and each of the output ports of the instance (i.e. there is a graph "path" from every input to every output). This may be overly conservative and suggest greater connectivity than actually exists. If the lack of connectivity between some input ports and some output ports needs to be represented, a different graph data structure needs to be used. Other suggested data structures that could be created include: - Represent nodes only as EdifPortRef objects and represent connectivity between cells between edif port ref nodes. Create hierarchy to group these nodes as instances.

The major work associated with this class is figuring out the connectivity of the EdifCell object. The EDIF data structure stores connectivity information only within the EdifNet object. Because of this, the Collection of EdifNet objects must be searched completely to determine connectivity between any given EdifCellInstance objects. This search, order N, must be performed every time a connectivity query is made. This class is used to perform this connectivity search once and cache the result within HashMap objects to facilitate more efficient connectivity queries at a later time.

The data structures within this class are created by iterating through all of the EdifNet objects. Each EdifPortRef object associated with the EdifNet object is associated with either an EdifCellInstance object (i.e. a connection to a port of an instance) or it is associated with a top-level EdifPort object (i.e. a connection to a top-level port). This connectivity is stored as a Map object between EdifCellInstances (or top level ports) and a Collection of corresponding EdifCellInstanceEdge objects.

See Also:
Serialized Form

Field Summary
protected  EdifCell _cell
          The cell corresponding to these connections.
protected  java.util.Collection<EdifCellInstanceEdge> _sourceToSourceEdges
          A Collection of the source-to-source Edges in the Graph (Edges between drivers of the same Net)
 
Fields inherited from class edu.byu.ece.graph.BasicGraph
_nodes, _nodeSinkMap, _nodeSourceMap
 
Constructor Summary
EdifCellInstanceGraph(EdifCell c)
          Construct a new connectivity object from a EdifCell.
EdifCellInstanceGraph(EdifCell c, boolean includeTopLevelPorts)
          Construct a new connectivity object from a EdifCell.
EdifCellInstanceGraph(EdifCell c, boolean includeTopLevelPorts, boolean createSourceToSourceEdges)
          Construct a new connectivity object from a EdifCell.
EdifCellInstanceGraph(EdifCellInstanceGraph ecic)
          Create a new connectivity object from an existing connectivity object (i.e.
 
Method Summary
protected  java.util.Collection<EdifPortRef> _createEPRCollection(java.util.Collection links, boolean keepSource)
          Create a Collection of EdifPortRef objects from a Collection of EdifCellInstanceEdge objects.
protected  void _init(boolean includeTopLevelPorts, boolean createSourceToSourceEdges)
          Initializes the connectivity maps for the given cell.
 java.lang.Object clone()
          Clone the BasicGraph object.
 EdifCell getCell()
          Return the EdifCell object that this connectivity object was created from.
 java.util.Collection<EdifCellInstanceEdge> getEdges()
          Return a Collection of all edges in the graph.
 java.util.Collection<EdifPortRef> getEdifPortRefs(EdifPort port)
          Obtain a Collection of EdifPortRef objects that are connected to the input ports of this instance.
 java.util.Collection<EdifPortRef> getEPRsWhichReferenceInputPortsOfECI(EdifCellInstance eci)
          Obtain a Collection of EdifPortRef objects that are connected to the input ports of this instance.
 java.util.Collection<EdifPortRef> getEPRsWhichReferenceInputPortsOfSinksOfECI(EdifCellInstance eci)
          Obtain the "sink" EdifPortRef objects that are driven by the given EdifCellInstance.
 java.util.Collection<EdifPortRef> getEPRsWhichReferenceOutputPortsOfECI(EdifCellInstance eci)
          Obtain a collection of EdifPortRef objects that are connected to the true output ports of this instance.
 java.util.Collection<EdifPortRef> getEPRsWhichReferenceOutputPortsOfSourcesOfECI(EdifCellInstance eci)
          Obtain the "source" EdifPortRef objects that drive the given EdifCellInstance.
 java.util.Collection<EdifCellInstanceEdge> getInputEdges(java.lang.Object node, EdifPortRef epr)
          Returns the input Edges which drive the given EdifSingleBitPort.
 java.util.Collection<EdifCellInstanceEdge> getInputEdges(java.lang.Object node, java.lang.String singleBitPortName)
          Returns the input Edges which drive the given EdifSingleBitPort.
 java.util.Collection<EdifCellInstanceEdge> getOutputEdges(java.lang.Object node, EdifPortRef epr)
          Returns the output Edges which are driven by the given EdifSingleBitPort.
 java.util.Collection<EdifCellInstanceEdge> getOutputEdges(java.lang.Object node, java.lang.String singleBitPortName)
          Returns the output Edges which are driven by the given EdifSingleBitPort.
 java.util.Collection getPredecessors(java.lang.Object node, EdifPortRef epr)
          Returns the source nodes which drive the given EdifPortRef.
 java.util.Collection getPredecessors(java.lang.Object node, java.lang.String portName)
          Returns the source nodes which drive the given EdifPort.
 java.util.Collection<EdifCellInstanceEdge> getSourceToSourceEdges()
           
 EdifCellInstanceGraph getSubGraph(java.util.Collection nodeCollection)
          Creates a sub-graph of the given graph from a sub-set of nodes in the graph.
 java.util.Collection getSuccessors(java.lang.Object node, EdifPortRef epr)
          Returns the sink nodes driven by the given EdifPort.
 java.util.Collection getSuccessors(java.lang.Object node, java.lang.String portName)
          Returns the sink nodes driven by the given EdifPortRef.
 java.util.Collection<EdifSingleBitPort> getTopLevelPortNodes()
          Finds and retrieves all of the top-level port nodes in the graph
 void removeIOBufs()
          Removes all IBUFs, BUFGPs, and OBUFs from an EDIF design/graph.
 void removeSourceToSourceEdges()
          Removes all of the source-to-source Edges (if any) in the graph.
 void removeTopLevelPortNodes()
          Removes all of the top-level port nodes from the graph
 void toEdif(java.lang.String filename)
          This method creates an EDIF file from the graph.
 
Methods inherited from class edu.byu.ece.graph.BasicGraph
addEdge, addNode, addNodes, containsNode, getEdge, getEdges, getInputEdges, getNodes, getNodesWithNoInputEdges, getNodesWithNoOutputEdges, getOutputEdges, getSinkNodes, getSourceNodes, getSubGraph2, invert, removeEdge, removeEdges, removeNode, removeNode, topologicalSort
 
Methods inherited from class edu.byu.ece.graph.AbstractGraph
_getAncestorsOrDescendents, _getAncestorsOrDescendents, getAncestors, getAncestors, getDescendents, getDescendents, getPredecessors, getSuccessors, toDotty, toString
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

_cell

protected EdifCell _cell
The cell corresponding to these connections.


_sourceToSourceEdges

protected java.util.Collection<EdifCellInstanceEdge> _sourceToSourceEdges
A Collection of the source-to-source Edges in the Graph (Edges between drivers of the same Net)

Constructor Detail

EdifCellInstanceGraph

public EdifCellInstanceGraph(EdifCell c)
Construct a new connectivity object from a EdifCell. Default to include Top Level Ports in the graph and NOT create source-to-source Edges in the Graph.

Parameters:
c -

EdifCellInstanceGraph

public EdifCellInstanceGraph(EdifCell c,
                             boolean includeTopLevelPorts)
Construct a new connectivity object from a EdifCell. Default to NOT create source-to-source Edges in the Graph.

Parameters:
c -

EdifCellInstanceGraph

public EdifCellInstanceGraph(EdifCell c,
                             boolean includeTopLevelPorts,
                             boolean createSourceToSourceEdges)
Construct a new connectivity object from a EdifCell.

Parameters:
c -

EdifCellInstanceGraph

public EdifCellInstanceGraph(EdifCellInstanceGraph ecic)
Create a new connectivity object from an existing connectivity object (i.e. a copy constructor).

Parameters:
ecic -
Method Detail

clone

public java.lang.Object clone()
Description copied from class: BasicGraph
Clone the BasicGraph object.

Overrides:
clone in class BasicGraph

getCell

public EdifCell getCell()
Return the EdifCell object that this connectivity object was created from.

Specified by:
getCell in class AbstractEdifGraph
Returns:
EdifCell object used to create this graph.
See Also:
AbstractEdifGraph.getCell()

getEdges

public java.util.Collection<EdifCellInstanceEdge> getEdges()
Description copied from interface: DirectedGraph
Return a Collection of all edges in the graph. The objects in this collection are of type Edge.

Specified by:
getEdges in interface DirectedGraph
Overrides:
getEdges in class BasicGraph
See Also:
BasicGraph.getEdges()

getEdifPortRefs

public java.util.Collection<EdifPortRef> getEdifPortRefs(EdifPort port)
Obtain a Collection of EdifPortRef objects that are connected to the input ports of this instance. If there are no connections, return a non-null empty Collection.

Note: this method is not part of the DirectedGraph interface.


getEPRsWhichReferenceInputPortsOfECI

public java.util.Collection<EdifPortRef> getEPRsWhichReferenceInputPortsOfECI(EdifCellInstance eci)
Obtain a Collection of EdifPortRef objects that are connected to the input ports of this instance. If there are no connections, return a non-null empty Collection.

Note: this method is not part of the DirectedGraph interface.


getEPRsWhichReferenceOutputPortsOfECI

public java.util.Collection<EdifPortRef> getEPRsWhichReferenceOutputPortsOfECI(EdifCellInstance eci)
Obtain a collection of EdifPortRef objects that are connected to the true output ports of this instance. If there are no connections, return a non-null empty Collection.

Note: this method is not part of the DirectedGraph interface.


getEPRsWhichReferenceInputPortsOfSinksOfECI

public java.util.Collection<EdifPortRef> getEPRsWhichReferenceInputPortsOfSinksOfECI(EdifCellInstance eci)
Obtain the "sink" EdifPortRef objects that are driven by the given EdifCellInstance. The EdifPortRef objects returned are those EPRs that are connected to EdifCellInstance ports (not top-level ports).

Note: this method is not part of the DirectedGraph interface.


getEPRsWhichReferenceOutputPortsOfSourcesOfECI

public java.util.Collection<EdifPortRef> getEPRsWhichReferenceOutputPortsOfSourcesOfECI(EdifCellInstance eci)
Obtain the "source" EdifPortRef objects that drive the given EdifCellInstance. These source EPRs may be driven by different ECIs. This method can be used to find the ECIs that drive the given parameter ECI.

Note: this method is not part of the DirectedGraph interface.


getInputEdges

public java.util.Collection<EdifCellInstanceEdge> getInputEdges(java.lang.Object node,
                                                                EdifPortRef epr)
Returns the input Edges which drive the given EdifSingleBitPort.

Parameters:
node - The node in the graph to examine
epr - The EdifPortRef whose driver edges are desired
Returns:
A Collection of Edges in the graph which drive the given node and that are attached to the named SingleBitPort

getInputEdges

public java.util.Collection<EdifCellInstanceEdge> getInputEdges(java.lang.Object node,
                                                                java.lang.String singleBitPortName)
Returns the input Edges which drive the given EdifSingleBitPort.

Parameters:
node - The node in the graph to examine
singleBitPortName - The name of the SingleBitPort whose driver is desired
Returns:
A Collection of Edges in the graph which drive the given node and that are attached to the named SingleBitPort

getOutputEdges

public java.util.Collection<EdifCellInstanceEdge> getOutputEdges(java.lang.Object node,
                                                                 EdifPortRef epr)
Returns the output Edges which are driven by the given EdifSingleBitPort.

Parameters:
node - The node in the graph to examine
epr - The EdifPortRef whose sink edges are desired
Returns:
A Collection of Edges in the graph which are driven by the given node and that are attached to the named SingleBitPort

getOutputEdges

public java.util.Collection<EdifCellInstanceEdge> getOutputEdges(java.lang.Object node,
                                                                 java.lang.String singleBitPortName)
Returns the output Edges which are driven by the given EdifSingleBitPort.

Parameters:
node - The node in the graph to examine
singleBitPortName - The name of the SingleBitPort whose sink is desired
Returns:
A Collection of Edges in the graph which are driven by the given node and that are attached to the named SingleBitPort

getPredecessors

public java.util.Collection getPredecessors(java.lang.Object node,
                                            java.lang.String portName)
Returns the source nodes which drive the given EdifPort.

Parameters:
node - The node in the graph to examine
portName - The name of the EdifPort whose drivers are desired
Returns:
A Collection of Objects (nodes) in the graph which drive the Edges connected to the given node and that are attached to the named EdifPort

getPredecessors

public java.util.Collection getPredecessors(java.lang.Object node,
                                            EdifPortRef epr)
Returns the source nodes which drive the given EdifPortRef.

Parameters:
node - The node in the graph to examine
epr - The EdifPortRef whose drivers are desired
Returns:
A Collection of Objects (nodes) in the graph which drive the Edges connected to the given node and that are attached to the given EdifPortRef

getSourceToSourceEdges

public java.util.Collection<EdifCellInstanceEdge> getSourceToSourceEdges()

getSuccessors

public java.util.Collection getSuccessors(java.lang.Object node,
                                          EdifPortRef epr)
Returns the sink nodes driven by the given EdifPort.

Parameters:
node - The node in the graph to examine
portName - The name of the EdifPort whose sinks are desired
Returns:
A Collection of Objects (nodes) in the graph which is driven by the Edges connected to the given node and that are attached to the named EdifPort

getSuccessors

public java.util.Collection getSuccessors(java.lang.Object node,
                                          java.lang.String portName)
Returns the sink nodes driven by the given EdifPortRef.

Parameters:
node - The node in the graph to examine
epr - The EdifPortRef whose sinks are desired
Returns:
A Collection of Objects (nodes) in the graph which is driven by the Edges connected to the given node and that are attached to the named EdifPort

getTopLevelPortNodes

public java.util.Collection<EdifSingleBitPort> getTopLevelPortNodes()
Finds and retrieves all of the top-level port nodes in the graph


getSubGraph

public EdifCellInstanceGraph getSubGraph(java.util.Collection nodeCollection)
Description copied from class: BasicGraph
Creates a sub-graph of the given graph from a sub-set of nodes in the graph. The resulting graph contains a sub-set of nodes and only those edges that connect nodes in the sub-graph.

Specified by:
getSubGraph in interface DirectedGraph
Overrides:
getSubGraph in class BasicGraph
Returns:
a new DirectedGraph object that is a sub-graph of this graph. The sub-graph is based on the Collection of nodes passed in as a parameter.

removeIOBufs

public void removeIOBufs()
Removes all IBUFs, BUFGPs, and OBUFs from an EDIF design/graph. This removal is essential when importing an EDIF file as a EdifCell into a larger design. If these BUFs are not taken out, the Xilinx tools will attempt to connect the ports of the imported EDIF design to pins.


removeTopLevelPortNodes

public void removeTopLevelPortNodes()
Removes all of the top-level port nodes from the graph


removeSourceToSourceEdges

public void removeSourceToSourceEdges()
Removes all of the source-to-source Edges (if any) in the graph. Also removes all references to these Edges in this class.


toEdif

public void toEdif(java.lang.String filename)
This method creates an EDIF file from the graph.

Parameters:
filename - - the name of the EDIF file created.

_init

protected void _init(boolean includeTopLevelPorts,
                     boolean createSourceToSourceEdges)
Initializes the connectivity maps for the given cell. Note that this happens only once and that this does not track changes in the EdifCell. If the cell changes, this connectivity will be stale.


_createEPRCollection

protected java.util.Collection<EdifPortRef> _createEPRCollection(java.util.Collection links,
                                                                 boolean keepSource)
Create a Collection of EdifPortRef objects from a Collection of EdifCellInstanceEdge objects. If keepSource is true, return the EdifPortRef objects that are the "sources" of the links. If false, return the EdifPortRef objects that are the "sinks" of the links.

Parameters:
links - The Collection of EdifCellInstanceEdge objects
keepSource - If true, get the sources. If false, get the sinks
Returns:
The Collection of EdifPortRef objects