Function NetworKit::GraphTools::topologicalSort(const Graph&)¶

Function Documentation¶

std::vector<node> NetworKit::GraphTools::topologicalSort(const Graph &G)¶

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

Returns:

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