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 * This class implements miscellaneous utilities for graphs.
020 */
021public class GraphUtilities {
022
023  /**
024   * Return an enumeration of the nodes, or a subset of the nodes, in an
025   * acyclic graph in topological order. <p>
026   *
027   * Note: if G is cyclic, results are undefined
028   *
029   * @param G the graph to enumerate
030   * @return an enumeration of the graph in topological order, as defined
031   *  above
032   */
033  public static Enumeration<GraphNode> enumerateTopSort(Graph G) {
034    return enumerateTopSort(G, G.enumerateNodes());
035  }
036
037  public static Enumeration<GraphNode> enumerateTopSort(Graph G, Enumeration<GraphNode> ie) {
038    return enumerateTopSortInternal(G, new DFSenumerateByFinish(G, ie));
039  }
040
041  public static Enumeration<GraphNode> enumerateTopSort(Graph G, Enumeration<GraphNode> ie,
042                                                          GraphEdgeFilter f) {
043    return enumerateTopSortInternal(G, new FilteredDFSenumerateByFinish(G, ie, f));
044  }
045
046  private static Enumeration<GraphNode> enumerateTopSortInternal(Graph G, Enumeration<GraphNode> e) {
047    final GraphNode[] elts = new GraphNode[G.numberOfNodes()];
048
049    int i = 0;
050    while (e.hasMoreElements()) {
051      elts[i++] = e.nextElement();
052    }
053
054    final int i1 = i;
055
056    return new GraphNodeEnumerator() {
057      private int top = i1;
058
059      @Override
060      public boolean hasMoreElements() {
061        return top > 0;
062      }
063
064      @Override
065      public GraphNode nextElement() {
066        return elts[--top];
067      }
068    };
069  }
070}