mapss.dif.graph
Class PartialTopSortStrategy

java.lang.Object
  mocgraph.analysis.strategy.CachedStrategy
      mapss.dif.graph.BaseTopSortStrategy
          mapss.dif.graph.PartialTopSortStrategy

All Implemented Interfaces:

TopSortAnalyzer, mocgraph.analysis.analyzer.Analyzer, mocgraph.analysis.analyzer.GraphAnalyzer

public class PartialTopSortStrategy
extends BaseTopSortStrategy

A topological sorting approach by building partial orders. One advantage of partial ordering is that optimization at later stage can make better decision based on the partial order.

Version:

$Id: PartialTopSortStrategy.java 409 2007-05-13 19:47:16Z plishker $

Author:

Ming-Yung Ko

See Also:

TopSortAnalysis

Constructor Summary

PartialTopSortStrategy(mocgraph.Graph graph)
Construct a top sorting strategy for a given graph.

Method Summary

protected java.lang.Object	_compute() Compute a topological sorting order.
protected mocgraph.Node	_nextSource(java.util.List partialOrder, java.util.Collection sources) Return the next source node in determining the top sort.

Methods inherited from class mapss.dif.graph.BaseTopSortStrategy

_validate, directedGraph, topSort, toString, valid

Methods inherited from class mocgraph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface mocgraph.analysis.analyzer.GraphAnalyzer

graph

Constructor Detail

PartialTopSortStrategy

public PartialTopSortStrategy(mocgraph.Graph graph)

Construct a top sorting strategy for a given graph.

Parameters:

graph - The given graph.

Method Detail

_compute

protected java.lang.Object _compute()

Compute a topological sorting order. The result is returned as a List, where the order begins at index 0.

Overrides:

_compute in class mocgraph.analysis.strategy.CachedStrategy

Returns:

A topological sorting order.

_nextSource

protected mocgraph.Node _nextSource(java.util.List partialOrder,
                                    java.util.Collection sources)

Return the next source node in determining the top sort. The next source node candidate is determined by the top sort computed so far as well the candidate sources to append to the parial order. This method is supposed to be overriden by specific source selection approach.

Parameters:

partialOrder - The partial top sort computed so far.

sources - The candidate sources to append to the partial order.

Returns:

The next source node.