Program Listing for File TopologicalSort.hpp¶

/*
 * TopologicalSort.hpp
 *
 *  Created on: 22.11.2021
 *      Author: Fabian Brandt-Tumescheit
 */
#ifndef NETWORKIT_GRAPH_TOPOLOGICAL_SORT_HPP_
#define NETWORKIT_GRAPH_TOPOLOGICAL_SORT_HPP_

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class TopologicalSort final : public Algorithm {
public:
    TopologicalSort(const Graph &G);

    void run() override;

    const std::vector<node> &getResult() const {
        assureFinished();
        return topology;
    }

private:
    enum class NodeMark : unsigned char { NONE, TEMP, PERM };

    const Graph *G;

    // Used to mark the status of each node, one vector per thread
    std::vector<NodeMark> topSortMark;

    // Contains information about the computed topology
    std::vector<node> topology;

    // Helper structures
    count current;

    // Reset algorithm data structure
    void reset();
};
} // namespace NetworKit

#endif // NETWORKIT_GRAPH_TOPOLOGICAL_SORT_HPP_