Given a directed graph G, the topology sort algorithm creates one valid topology order of nodes. Undirected graphs are not accepted as input, since a topology sort is a linear ordering of vertices such that for every edge u -> v, node u comes before v in the ordering.
Public Functions
-
TopologicalSort(const Graph &G)
Initialize the topological sort algorithm by passing an input graph. Note that topological sort is defined for directed graphs only.
- Parameters:
G – The input graph.
-
virtual void run() override
Execute the algorithm. The algorithm is not parallel.
-
inline const std::vector<node> &getResult() const
Return the topology
- Returns:
One valid topology. Order in topology is from 0 to number of nodes.