Function NetworKit::GraphTools::topologicalSort¶

Function Documentation¶

std::vector<node> NetworKit::GraphTools::topologicalSort(const Graph &G, const std::unordered_map<node, node> &nodeIdMapping = {}, bool checkMapping = false)¶

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. Node ids must either be continuous or you must provide a continuous node id mapping.

This is a helper function. Instead of calling it via GraphTools, it is also possible to create a TopologicalSort-object from the base-class.

Parameters:

• G – Directed input graph

• nodeIdMapping – Optional continuous node id mapping

Returns:

A vector of node-ids sorted according to their topology.