mapss.dif.graph
Class DFSTopSortStrategy

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

All Implemented Interfaces:

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

Direct Known Subclasses:

MBOTopSortStrategy

public class DFSTopSortStrategy
extends BaseTopSortStrategy

A depth-first-search approach for finding a topological sorting order. This class adopts a simple approach to pick the first available source node.

Version:

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

Author:

Ming-Yung Ko

See Also:

TopSortAnalysis

Constructor Summary

DFSTopSortStrategy(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(mocgraph.DirectedGraph graph) Return the next source node in determining the top sort.
protected void	_setup() A preliminary step in computing topological sorting.

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

DFSTopSortStrategy

public DFSTopSortStrategy(mocgraph.Graph graph)

Construct a top sorting strategy for a given graph.

Parameters:

graph - The given graph.

Method Detail

_compute

protected final 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(mocgraph.DirectedGraph graph)

Return the next source node in determining the top sort. This method is supposed to be overriden by specific source selection approach.

Parameters:

graph - The graph to get the next source node.

Returns:

The next source node.

_setup

protected void _setup()

A preliminary step in computing topological sorting. This is a step executed in _compute(). The default action here basically does nothing and users can define desired actions.