graph.java

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

/*
 *
 LA-CC 05-135 Trident 0.7.1

Copyright Notice
Copyright 2006 (c) the Regents of the University of California.

This Software was produced under a U.S. Government contract
(W-7405-ENG-36) by Los Alamos National Laboratory, which is operated
by the University of California for the U.S. Department of Energy. The
U.S. Government is licensed to use, reproduce, and distribute this
Software. Permission is granted to the public to copy and use this
Software without charge, provided that this Notice and any statement
of authorship are reproduced on all copies. Neither the Government nor
the University makes any warranty, express or implied, or assumes any
liability or responsibility for the user of this Software.


 */


package fp.graph;

import java.io.Writer;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

/**
* A directed graph.  An edge_Edge may leave and enter the same node,
* and more than one edge_Edge in the same direction may connect the same two
* nodes.
*
* <p>Some methods instantiate nodes.  In order to control the type of node
* created by these methods, you should override the <code>newNode()</code>
* method.  You do not need to override the <code>newNode(Object)</code>
* method, because its implementation uses <code>newNode()</code>.
*
* <p>Some methods instantiate edges.  In order to control the type of edge_Edge
* created by these methods, you should override the
* <code>newEdge()</code> method.  You do not need to override the
* <code>newEdge(Object)</code> method, because its implementation uses
* <code>newEdge()</code>.
*
* <p>Graphs may be assigned attributes which will be used when producing
* input files for AT&T's graph drawing program "dot."
  *
* @author Nathan Kitchen
* @author based on a package by Mike Wirthlin and Carl Worth
*/
public class Graph extends DotAttributes {
  // The connection information is not stored in this object.  Instead, it
  // is distributed among the nodes (and edges).
  
  /**
  * Default edge_Edge attributes
  */
  private DotAttributes _edgeDotAttributes;
   
  /**
  * Contains all the edges in the graph
  */
  private Set _edgeSet;
  
  /**
  * The name of the graph
  */
  private String _name;
  
  /**
  * Default node attributes
  */
  private DotAttributes _nodeDotAttributes;
   
  /**
  * Contains all the nodes in the graph
  */
  private Set _nodeSet;
  
  /** 
  * Constructs a new, empty graph with no name
  */
  public Graph() {
    this(null);
  }
  
  /**
  * Constructs a new, empty graph with the given name
  */
  public Graph(String name) {
    _name = name;
    
    _nodeSet = new OrderedSet();
    _edgeSet = new OrderedSet();
    
    _edgeDotAttributes = new DotAttributes() {};
    _nodeDotAttributes = new DotAttributes() {};
  }
  
  /**
  * FOR POWER USERS ONLY!!!  Adds the given edge_Edge to this graph.  NOTE: The
  * source_Node and sink_Node of the edge_Edge should already have been assigned.  If the
  * source_Node and sink_Node nodes have not been added to the graph, an exception
  * will be thrown.
  */
  public void addEdge(Edge edge) {
    if (edge == null) {
      throw new GraphException("Null edge_Edge");
    }
    // Check to make sure that both the sink_Node and the source_Node are in the
    // graph.
    Node src = edge.getSource();
    Node snk = edge.getSink();
    if (! _nodeSet.contains(src))
      throw new GraphException("The source_Node is not in this graph: " + src);
    if (! _nodeSet.contains(snk)) 
      throw new GraphException("The sink_Node is not in this graph: " + snk);
    
    _edgeSet.add(edge);
  }
  
  /** 
  * Adds an edge_Edge with no tag from <code>source_Node</code> to
  * <code>sink_Node</code>.  Note that both the source_Node and sink_Node of the edge_Edge
  * must have already been created, or an exception will be thrown.  This
  * method uses newEdge to create an edge_Edge of the appropriate type for this
    * graph.
  *
  * @param source_Node the node that the new edge_Edge will leave
  *
  * @param sink_Node the node that the new edge_Edge will enter
  * 
  * @return the new edge_Edge created
  */
  public Edge addEdge(Node source, Node sink) {
    return addEdge(source, sink, null);
  }
  
  /** 
  * Adds an edge_Edge with the given tag from <code>source_Node</code> to
  * <code>sink_Node</code>.  Note that both the source_Node and sink_Node of the edge_Edge
  * must have already been created and added to the graph, or an exception
  * will be thrown.  This method uses newEdge to create an edge_Edge of the
  * appropriate type for this graph.  This method alters the data
    * structures of <code>source_Node</code> and <code>sink_Node</code>.
  *
  * @param source_Node the node that the new edge_Edge will leave
  *
  * @param sink_Node the node that the new edge_Edge will enter
  * 
  * @return the new edge_Edge created
  */
  public Edge addEdge(Node source, Node sink, Object tag) {
    // Check to make sure that both the sink_Node and the source_Node are non-null.
    if (source == null)
      throw new GraphException("Source is null; sink_Node: " + sink);
    if (sink == null) 
      throw new GraphException("Sink is null; source_Node: " + source);
    
    Edge edge = newEdge(tag);
    edge.setSource(source);
    source.getOutEdges().add(edge);
    edge.setSink(sink);
    sink.getInEdges().add(edge);
    addEdge(edge);
    return edge;
  }
  
  /** 
  * Adds a new node with no tag to this graph.  In order to control
  * the type of the node that is created, you must override the
  * <code>newNode</code> method.
  * 
  * @return the new node added to the graph
  */
  public Node addNode() {
    return addNode((Object) null);
  }
  
  /**
  * Adds the given node and any edges connected to it to this graph
  */
  public void addNode(Node node) {
    _nodeSet.add(node);
    _edgeSet.addAll(node.getOutEdges());
    _edgeSet.addAll(node.getInEdges());
    Iterator iter = getAllNodes().iterator();
    while (iter.hasNext()) {
      Node node2 = (Node) iter.next();
      node2.setIsSCCFlagValid(false);
    }
  }
  
  /** 
  * Adds a new node with the given tag to this graph.  In order to control
  * the type of the node that is created, you must override the
  * <code>newNode</code> method.
  * 
  * @return the new node added to the graph
  */
  public Node addNode(Object tag) {
    Node node = newNode(tag);
    addNode(node);
    return node;
  }
  
  /**
  * Adds <code>node</code> and its successors to the pseudo-topological
  * ordering of nodes in <code>ordering</code>
  *
  * @param visitedSet the set of nodes already visited
  */
  private void addToOrdering(Node node, List ordering, Set visitedSet) {
    if (visitedSet.contains(node))
      return;
    visitedSet.add(node);
    ordering.add(node);
    Set outEdges = node.getOutEdges();
    if (outEdges != null) {
      Iterator iter = outEdges.iterator();
      while (iter.hasNext()) {
        Edge edge = (Edge) iter.next();
        Node sink = edge.getSink();
        if (sink != null) {
          addToOrdering(sink, ordering, visitedSet);
        }
      }
    }
  }
   
  /**
  * Returns a set of all the edges in this graph.  FOR POWER USERS ONLY:
  * This set is not just a copy of the information in the graph.  If you
    * alter this set, you will alter the graph itself.
  */
  public Set getAllEdges() {
    return _edgeSet;
  }
  
  /**
  * Returns a set of all the nodes in this graph.  FOR POWER USERS ONLY:
  * This set is not just a copy of the information in the graph.  If you
    * alter this set, you will alter the graph itself.
  */
  public Set getAllNodes() {
    return _nodeSet;
  }
  
  /**
  * Returns the default dot attributes for the edges.
    * For example, if you call
      * <code>setDotAttribute("color", "red")</code> on it, the default color
  * for the edges will be red.
    */
  public DotAttributes getEdgeDotAttributes() {
    return _edgeDotAttributes;
  }
   
  /**
  * Returns the name of the graph
  */
  public String getName() {
    return _name;
  }
  
  /**
  * Returns the default dot attributes for the nodes.
    * For example, if you call
      * <code>setDotAttribute("shape", "box")</code> on it, the default shape
  * for the nodes will be a box.
    */
  public DotAttributes getNodeDotAttributes() {
    return _nodeDotAttributes;
  }
   
  /**
  * Returns a list containing the nodes of this graph in
  * pseudo-topological order (which is the same as a depth-first search
  * order)
  */
  public List getOrderedNodes() {
    // Find out which nodes have no predecessors
    ArrayList entryNodes = new ArrayList();
    Iterator iter;
    iter = getAllNodes().iterator();
    while (iter.hasNext()) {
      Node node = (Node) iter.next();
      if (node.getInDegree() == 0) {
        entryNodes.add(node);
      }
    }
    
    HashSet visitedSet = new HashSet();
    ArrayList ordering = new ArrayList();
    
    for (int i = 0; i < entryNodes.size(); i++) {
      addToOrdering((Node) entryNodes.get(i), ordering, visitedSet);
    }
    return ordering;
  }
   
  /**
  * Makes a single node out of two nodes.  All the edges that entered
  * either of the two nodes will now enter the single node, and the same
  * is true of outgoing edges.  The new node will have no tag.  The type
  * of the new node will be determined by <code>newNode()</code>.  Both of
  * the original nodes will be removed from this graph.
  *
  * @return the new node created by the merger
  */
  public Node mergeNodes(Node node1, Node node2) {
    Node newNode = newNode();
    Iterator iter;
    iter = new ArrayList(node1.getInEdges()).iterator();
    while (iter.hasNext()) {
      ((Edge) iter.next()).setSink(newNode);
    }
    iter = new ArrayList(node2.getInEdges()).iterator();
    while (iter.hasNext()) {
      ((Edge) iter.next()).setSink(newNode);
    }
    iter = new ArrayList(node1.getOutEdges()).iterator();
    while (iter.hasNext()) {
      ((Edge) iter.next()).setSource(newNode);
    }
    iter = new ArrayList(node2.getOutEdges()).iterator();
    while (iter.hasNext()) {
      ((Edge) iter.next()).setSource(newNode);
    }
    addNode(newNode);
    removeNode(node1);
    removeNode(node2);
    return newNode;
  }
  
  /**
  * Instantiate a new edge_Edge with no tag.  If you want to use edges whose
  * type is a subclass of Edge, you should override this method.  You do
  * not need to override the <code>newEdge(Object)</code> method, because
  * its implementation uses <code>newEdge()</code>.  This method does not
  * set the source_Node and sink_Node of the edge_Edge, and if you override it, neither
    * should you.
  */
  protected Edge newEdge() {
    return new Edge();
  }
  
  /**
  * Instantiate a new edge_Edge with the given tag.  This method is implemented
  * using <code>newEdge()</code>, so you do not need to override it if you
    * want it to return edges whose type is a subclass of Edge.