Program Listing for File graph_runtime.cc

↰ Return to documentation for file (src/graph_runtime.cc)

#include <algorithm>
#include <utility>
#include "nodes-graph/graph_runtime.h"


namespace ng {

std::vector<node_id_t> sorted_by_depth(const Graph& graph) {
    Graph::DepthProperties props = graph.get_depth_properties();
    if (props.has_cycle) {
        throw std::runtime_error("Can't sort a graph containing a cycle");
    }

    std::vector<std::pair<node_id_t, std::size_t>> by_depth(props.depth.begin(), props.depth.end());
    std::stable_sort(by_depth.begin(), by_depth.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    std::vector<node_id_t> sorted_nodes;
    sorted_nodes.reserve(by_depth.size());
    for (const auto& [node_id, _] : by_depth) {
        sorted_nodes.push_back(node_id);
    }
    return sorted_nodes;
}

} // namespace ng