Template Class GenericTopologicalSort¶

Inheritance Relationships¶

Class Documentation¶

template<typename GraphT>
class GenericTopologicalSort : 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 Types

using NodeT = typename GraphT::NodeT¶

using NodeIdMapping = std::unordered_map<NodeT, index>¶

Public Functions

GenericTopologicalSort(const GraphT &G)¶

Initialize the topological sort algorithm by passing an input graph.

Parameters:

G – The input graph.

GenericTopologicalSort(const GraphT &G, const NodeIdMapping &nodeIdMapping, bool checkMapping = false)¶

Initialize the topological sort algorithm by passing an input graph and an node id map. The node id mapping must be a continuous. This can be checked by setting checkMapping to true.

Parameters:

• G – The input graph.

• nodeIdMapping – Node id mapping from non-continuous to continuous ids.

• checkMapping – Check whether the given node id map is continuous.

virtual void run() override¶

Execute the algorithm. The algorithm is not parallel.

inline const std::vector<NodeT> &getResult() const¶

Return the topology

Returns:

One valid topology. Order in topology is from 0 to number of nodes.