graph.java

一种将c高级语言转化给VHDL的编译器

  */
  protected Edge newEdge(Object tag) {
    Edge edge = newEdge();
    edge.setTag(tag);
    return edge;
  }
  
  /**
  * Indicates whether there is an edge_Edge from <code>node1_Node</code> to
  * <code>node2_Node</code>
  */
  public boolean hasEdge(Node node1, Node node2) {
    Set nodes = getAllNodes();
    if (nodes.contains(node1) && nodes.contains(node2)) {
      for (Iterator it = node1.getOutEdges().iterator(); it.hasNext();){
        Edge edge = (Edge) it.next();
        if (edge.getSink() == node2) {
          return true;
        } // end of if ()
      } // end of for (Iterator  = .iterator(); .hasNext();)
    } // end of if ()
    return false;
  }
  /**
  * returns the edge_Edge going from node1_Node to node2_Node or null if none exists
    */
  public Edge findEdge(Node node1, Node node2) {
    Set nodes = getAllNodes();
    if (nodes.contains(node1) && nodes.contains(node2)) {
      for (Iterator it = node1.getOutEdges().iterator(); it.hasNext();){
        Edge edge_Edge = (Edge) it.next();
        if (edge_Edge.getSink() == node2) {
          return edge_Edge;
        } // end of if ()
      } // end of for (Iterator  = .iterator(); .hasNext();)
    } // end of if ()
    return null;
  }
  
  /**
  * Instantiate a new node with no tag.  If you want to use nodes whose
  * type is a subclass of Node, you should override this method.  You do
  * not need to override the <code>newNode(Object)</code> method, because
  * its implementation uses <code>newNode()</code>.
  */
  protected Node newNode() {
    return new Node();
  }
  
  /**
  * Instantiate a new node with the given tag.  This method is implemented using
  * <code>newNode()</code>, so you do not need to override it if you want
    * it to return nodes whose type is a subclass of Node.
  */
  protected Node newNode(Object tag) {
    Node node = newNode();
    node.setTag(tag);
    return node;
  }
  
  /**
  * Returns true if a path exists from <code>fromNode</code> to
    * <code>toNode</code> in this graph.  The path will be of length zero if
      * the two nodes are the same.
  */
  public boolean pathExists(Node fromNode, Node toNode) {
    if (_nodeSet.contains(fromNode) && _nodeSet.contains(toNode)) {
      Set visitedSet = new HashSet();
      return pathExists(fromNode, toNode, visitedSet);
    } // end of if ()
    else {
      return false;
    } // end of else
  }
  
  /**
  * Returns true if a path exists from <code>fromNode</code> to
    * <code>toNode</code> in this graph.  The path will be of length zero if
      * the two nodes are the same.
  *
  * @param visitedSet contains all the nodes visited so far; they don't need
  * to be checked
  */
  private boolean pathExists(Node fromNode, Node toNode, Set visitedSet) {
    if (fromNode == toNode) {
      return true;
    } // end of if ()
    
    if (visitedSet.contains(fromNode)) {
      return false;
    } // end of if ()
    else {
      visitedSet.add(fromNode);
      Set edgeSet = fromNode.getOutEdges();
      if (edgeSet != null) {
        for (Iterator it = edgeSet.iterator(); it.hasNext();){
          Edge edge = (Edge) it.next();
          Node node = edge.getSink();
          if (node != null) {
            return pathExists(node, toNode, visitedSet);
          } // end of if ()
        } // end of for (Iterator  = .iterator(); .hasNext();)
      } // end of if ()
      return false;
    } // end of else
  }
  
  /**
  * Removes this given edge_Edge from this graph.  This method alters the data
  * structures of the source_Node and sink_Node of the edge_Edge.
  */
  public void removeEdge(Edge edge) {
    Node node;
    node = edge.getSource();
    if (node != null)
      node.getOutEdges().remove(edge);
    node = edge.getSink();
    if (node != null)
      node.getInEdges().remove(edge);
    _edgeSet.remove(edge);
  }
  
  /**
  * Removes the given node from the graph, as well as all edges entering and
  * leaving the node
  *
  * @param node the node to remove from the graph
  */
  public void removeNode(Node node) {
    // First, eliminate all the edges
    for (Iterator it = new ArrayList(node.getOutEdges()).iterator();
    it.hasNext();){
      removeEdge((Edge) it.next());
    } // end of for (Iterator  = .iterator(); .hasNext();)
    for (Iterator it = new ArrayList(node.getInEdges()).iterator();
    it.hasNext();){
      removeEdge((Edge) it.next());
    } // end of for (Iterator  = .iterator(); .hasNext();)
    _nodeSet.remove(node);
    Iterator iter = getAllNodes().iterator();
    while (iter.hasNext()) {
      Node node2 = (Node) iter.next();
      node2.setIsSCCFlagValid(false);
    }
    
  }
  
  /**
  * Replaces <code>oldEdge</code> in this graph with <code>newEdge</code>.
  * The sink_Node, source_Node, and tag of <code>oldEdge</code> will be copied to
  * <code>newEdge</code>, whose old information will be thrown out.  The
    * data structures of the source_Node and sink_Node nodes will be altered.  NOTE:
  * <code>newEdge</code> should nOT have been added to this graph already!
  */
  public void replaceEdge(Edge oldEdge, Edge newEdge) {
    if (oldEdge == newEdge)
      return;
     
    if (! _edgeSet.contains(oldEdge))
      throw new GraphException("Old edge_Edge not in graph");
    if (newEdge == null)
      throw new GraphException("New edge_Edge is null");
    if (_edgeSet.contains(newEdge)) {
      throw new GraphException("New edge_Edge already in graph");
    }
    
    newEdge.setTag(oldEdge.getTag());
    newEdge.setSource(oldEdge.getSource());
    newEdge.setSink(oldEdge.getSink());
    addEdge(newEdge);
    removeEdge(oldEdge);
  }
  
  /**
  * Replaces <code>oldNode</code> in this graph with <code>newNode</code>.
  * All the edges that enter <code>oldNode</code> will now enter
  * <code>newNode</code>, all the edges that leave <code>oldNode</code>
  * will now leave <code>newNode</code>, and <code>oldNode</code>'s tag
  * will be copied to <code>newNode</code>.  Any edge_Edge information or tag
    * that used to be in <code>newNode</code> will be thrown out.  NOTE:
  * <code>newNode</code> should nOT have been added to this graph already!
  */
  public void replaceNode(Node oldNode, Node newNode) {
    if (oldNode == newNode)
      return;
     
    if (! _nodeSet.contains(oldNode))
      throw new GraphException("Old node not in graph");
    if (newNode == null)
      throw new GraphException("New node is null");
    if (_nodeSet.contains(newNode)) {
      throw new GraphException("New node already in graph");
    }
    
    newNode.setTag(oldNode.getTag());
    Set edges;
    Iterator edgIt;
    edges = newNode.getInEdges();
    edges.clear();
    edges.addAll(oldNode.getInEdges());
    edgIt = edges.iterator();
    while (edgIt.hasNext()) {
      ((Edge) edgIt.next()).setSink(newNode);
    }
    edges = newNode.getOutEdges();
    edges.clear();
    edges.addAll(oldNode.getOutEdges());
    edgIt = edges.iterator();
    while (edgIt.hasNext()) {
      ((Edge) edgIt.next()).setSource(newNode);
    }
    addNode(newNode);
    removeNode(oldNode);
  }
  
  /**
  * For each component, sets the value_String of the dot attribute "label" to the
  * return value_String of <code>toString</code>
  */
  public void setAllDotLabelsFromToString() {
    Iterator it;
    it = getAllNodes().iterator();
    while (it.hasNext()) {
      ((Node) it.next()).setDotLabelFromToString();
    }
    it = getAllEdges().iterator();
    while (it.hasNext()) {
      ((Edge) it.next()).setDotLabelFromToString();
    }
  }
   
  /**
  * Renames the graph
  */
  public void setName(String name) {
    _name = name;
  }
  
  /**
  * Returns a String representation of this graph, which is derived from
  * its name unless the name is null.  For a String representation of all
  * the information in the graph, see <code>toDot</code>
    */
  public String toString() {
    String name = getName();
    if (name == null) {
      return super.toString();
    }
    else {
      return name;
    }
  }
  
  /**
  * Returns a representation of this graph in the language used by AT&T's
  * graph drawing program "dot"
  */
  public String toDot() {
    StringBuffer strBuf = new StringBuffer();
    strBuf.append("digraph \"" + getName() + "\" {\n");
      Iterator iter;
       
      // Graph attributes
      iter = getDotAttributeNames();
      while (iter.hasNext()) {
        String name = (String) iter.next();
        String value = getDotAttribute(name);
        strBuf.append("\t\"").append(convertSpecialsToEscapes(name))
        .append("\"=\"").append(convertSpecialsToEscapes(value))
        .append("\";\n");
      }
      
      // Default node attributes
      DotAttributes nodeAttributes = getNodeDotAttributes();
      if (nodeAttributes.getNumDotAttributes() > 0) {
        strBuf.append("\tnode ")
        .append(nodeAttributes.getDotAttributeList())
        .append(";\n");
      }
       
      // Default edge_Edge attributes
      DotAttributes edgeAttributes = getEdgeDotAttributes();
      if (edgeAttributes.getNumDotAttributes() > 0) {
        strBuf.append("\tedge ")
        .append(edgeAttributes.getDotAttributeList())
        .append(";\n");
      }
       
      // Nodes
      iter = getAllNodes().iterator();
      while (iter.hasNext()) {
        Node node = (Node) iter.next();
        strBuf.append("\t").append(node.toDot()).append(";\n");
      }
      
      // Edges
      iter = getAllEdges().iterator();
      while (iter.hasNext()) {
        strBuf.append('\t').append(((Edge) iter.next()).toDot()).append(";\n");
      }
      
    strBuf.append("}\n");
    return strBuf.toString();
  }
  
  /**
  * Writes this graph in the dot graph language to a file in the current
  * directory.  The file name is the name of the graph, plus the extension
  * ".dot".
  */
  public void writeDotFile() {
    writeDotFile(getName() + ".dot");
  }
   
  /**
  * Writes this graph in the dot graph language to a file in the current
  * directory with the given name
  */
  public void writeDotFile(String fileName) {
    try {
      FileWriter fileWriter = new FileWriter(fileName);
      writeDotFile(fileWriter);
      fileWriter.close();
      } catch (IOException e) {
      throw new GraphException("Exception occurred while trying to write" +
        " to file: " + e.getMessage());
    } // end of try-catch
  }
  
  /**
  * Writes this graph in the dot graph language to the given Writer
  */
  public void writeDotFile(Writer writer) {
    try {
      String dotStr = toDot();
      writer.write(dotStr, 0, dotStr.length());
      } catch (IOException e) {
      throw new GraphException("Exception occurred while trying to write" +
        " to file: " + e.getMessage());
    } // end of try-catch
  }
   
   
   
   
   
   
   
}