001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.util;
014
015import java.util.Enumeration;
016
017
018/**
019 * An abstract interface for generic graphs; general graph utilities
020 * should be defined in terms of this interface and all graph
021 * implementations in the system should implement it.
022 *
023 *
024 * @see GraphNode
025 * @see GraphEdge
026 * @see GraphUtilities
027 */
028public interface Graph {
029
030  /**
031   * This method lists all of the nodes in a given graph.  This is
032   * defined in terms of generic GraphNodes.
033   *
034   * @see GraphNode
035   *
036   * @return an enumeration of all nodes in the graph
037   */
038  Enumeration<GraphNode> enumerateNodes();
039
040  /**
041   *  Find out how many nodes are in the graph
042   *
043   *  @return the number of nodes in the graph
044   */
045  int numberOfNodes();
046
047  /**
048   *  After this method is called, all nodes in the graph should
049   * have a compact numbering from 0 to (number of nodes in
050   * graph - 1).  This number is what should be returned by
051   * {@link GraphNode#getIndex GraphNode.getIndex}.  This
052   * method is used by clients that want to e.g. allocate look-aside
053   * storage for graph nodes in an
054   * array.
055   */
056  void compactNodeNumbering();
057
058  /**
059   *  Add a new graph node to the graph.
060   *
061   * @param node the node to add to the graph
062   */
063  void addGraphNode(GraphNode node);
064
065  /**
066   *  Add a new edge to a graph.  This method is deliberately
067   * defined in terms of nodes to avoid requiring graphs that
068   * implement Graph have explicit edge objects.
069   *
070   * @param source the source node of the edge to add
071   * @param target the target node of the edge to add
072   */
073  void addGraphEdge(GraphNode source, GraphNode target);
074}