diff options
| author | Alexander Karatarakis <alkarata@microsoft.com> | 2017-04-11 14:44:14 -0700 |
|---|---|---|
| committer | Alexander Karatarakis <alkarata@microsoft.com> | 2017-04-12 22:05:03 -0700 |
| commit | d7466d98bb192952a31255bee53c9d74192dedd6 (patch) | |
| tree | 4473f749addc1e1fe142850b77f2c4c76eea4165 /toolsrc/include | |
| parent | cfbfa0d81327b32478e57cda85059c6063cd4bfd (diff) | |
| download | vcpkg-d7466d98bb192952a31255bee53c9d74192dedd6.tar.gz vcpkg-d7466d98bb192952a31255bee53c9d74192dedd6.zip | |
Extract toposort into a free function
Diffstat (limited to 'toolsrc/include')
| -rw-r--r-- | toolsrc/include/vcpkg_Graphs.h | 72 |
1 files changed, 43 insertions, 29 deletions
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h index b97f7ac50..1f90710fd 100644 --- a/toolsrc/include/vcpkg_Graphs.h +++ b/toolsrc/include/vcpkg_Graphs.h @@ -17,39 +17,55 @@ namespace vcpkg::Graphs FULLY_EXPLORED }; - template <class V> - class Graph + template <class V, class Func> + static void topological_sort_internal(V vertex, + ExplorationStatus& status, + const Func adjacency_list_provider, + std::unordered_map<V, ExplorationStatus>& exploration_status, + std::vector<V>& sorted) { - template <class Func> - static void topological_sort_internal(V vertex, - ExplorationStatus& status, - const Func adjacency_list_provider, - std::unordered_map<V, ExplorationStatus>& exploration_status, - std::vector<V>& sorted) - { - status = ExplorationStatus::PARTIALLY_EXPLORED; + status = ExplorationStatus::PARTIALLY_EXPLORED; - auto neighbours = adjacency_list_provider(vertex); + auto neighbours = adjacency_list_provider(vertex); - for (V neighbour : neighbours) + for (V neighbour : neighbours) + { + ExplorationStatus& neighbour_status = exploration_status[neighbour]; + if (neighbour_status == ExplorationStatus::NOT_EXPLORED) { - ExplorationStatus& neighbour_status = exploration_status[neighbour]; - if (neighbour_status == ExplorationStatus::NOT_EXPLORED) - { - topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted); - } - else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED) - { - throw std::runtime_error("cycle in graph"); - } + topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted); } + else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED) + { + throw std::runtime_error("cycle in graph"); + } + } + status = ExplorationStatus::FULLY_EXPLORED; + sorted.push_back(vertex); + } - status = ExplorationStatus::FULLY_EXPLORED; - sorted.push_back(vertex); + template <class V, class Func> + std::vector<V> topological_sort(const std::vector<V>& starting_vertices, const Func adjacency_list_provider) + { + std::vector<V> sorted; + std::unordered_map<V, ExplorationStatus> exploration_status; + + for (auto& vertex : starting_vertices) + { + ExplorationStatus& status = exploration_status[vertex]; + if (status == ExplorationStatus::NOT_EXPLORED) + { + topological_sort_internal(vertex, status, adjacency_list_provider, exploration_status, sorted); + } } - public: + return sorted; + } + template <class V> + class Graph + { + public: void add_vertex(V v) { this->vertices[v]; @@ -88,11 +104,9 @@ namespace vcpkg::Graphs ExplorationStatus& status = exploration_status[vertex]; if (status == ExplorationStatus::NOT_EXPLORED) { - topological_sort_internal(vertex, - status, - [this](const V& v) { return this->vertices.at(v); }, - exploration_status, - sorted); + topological_sort_internal(vertex, status, + [this](const V& v) { return this->vertices.at(v); }, + exploration_status, sorted); } } } |