Package pascal.taie.util.graph

Class TopoSorter<N>

java.lang.Object

pascal.taie.util.graph.TopoSorter<N>

Type Parameters:

N - type of nodes

public class TopoSorter<N>
extends Object

Topologically sorts a directed graph using DFS. It is assumed that the given graph is a direct acyclic graph (DAG).

Constructor Summary

Constructors

Constructor	Description
TopoSorter(Graph<N> graph)
TopoSorter(Graph<N> graph, boolean reverse)
TopoSorter(Graph<N> graph, List<N> preservedOrder)	Computes a topological soring of a graph, while the client code wishes to preserve some ordering in the sorting result.

Method Summary

Modifier and Type	Method	Description
List<N>	get()

Methods inherited from class java.lang.Object

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

Constructor Details

TopoSorter

public TopoSorter(Graph<N> graph)

TopoSorter

public TopoSorter(Graph<N> graph,
 boolean reverse)

TopoSorter

public TopoSorter(Graph<N> graph,
 List<N> preservedOrder)

Computes a topological soring of a graph, while the client code wishes to preserve some ordering in the sorting result. If preserved order conflicts the topological order, the latter is respected.

Parameters:

graph - the graph

preservedOrder - the order of the nodes that the client code wishes to preserve

Method Details

get

public List<N> get()

Returns:

the topologically sorted list.