Class TopologicalSort¶

Inheritance Relationships¶

Class Documentation¶

class TopologicalSort : public NetworKit::Algorithm¶

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, const std::unordered_map<node, node> &nodeIdMapping = {}, bool checkMapping = false)¶

Initialize the topological sort algorithm by passing an input graph. Note that topological sort is defined for directed graphs only. The node id mapping must be a continuous.

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.