diff options
| author | Alexander Karatarakis <alkarata@microsoft.com> | 2017-04-10 18:45:44 -0700 |
|---|---|---|
| committer | Alexander Karatarakis <alkarata@microsoft.com> | 2017-04-12 22:05:02 -0700 |
| commit | 612d941afc1339154354145f6fa5264d3c573cc0 (patch) | |
| tree | 5a7030a5f2f983fce25aed1381912c3a3ac0dda0 /toolsrc/include | |
| parent | a6f895ac8cf1f90c97d1dc98a942c33fa9bdbe01 (diff) | |
| download | vcpkg-612d941afc1339154354145f6fa5264d3c573cc0.tar.gz vcpkg-612d941afc1339154354145f6fa5264d3c573cc0.zip | |
toposort: use lambda to obtain the neighbours of a vertex
Diffstat (limited to 'toolsrc/include')
| -rw-r--r-- | toolsrc/include/vcpkg_Graphs.h | 15 |
1 files changed, 11 insertions, 4 deletions
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h index 933d9ac67..fb57a38db 100644 --- a/toolsrc/include/vcpkg_Graphs.h +++ b/toolsrc/include/vcpkg_Graphs.h @@ -20,20 +20,23 @@ namespace vcpkg::Graphs template <class V> class Graph { + template <class Func> static void find_topological_sort_internal(V vertex, ExplorationStatus& status, - const std::unordered_map<V, std::unordered_set<V>>& adjacency_list, + const Func adjacency_list_provider, std::unordered_map<V, ExplorationStatus>& exploration_status, std::vector<V>& sorted) { status = ExplorationStatus::PARTIALLY_EXPLORED; - for (V neighbour : adjacency_list.at(vertex)) + auto neighbours = adjacency_list_provider(vertex); + + for (V neighbour : neighbours) { ExplorationStatus& neighbour_status = exploration_status[neighbour]; if (neighbour_status == ExplorationStatus::NOT_EXPLORED) { - find_topological_sort_internal(neighbour, neighbour_status, adjacency_list, exploration_status, sorted); + find_topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted); } else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED) { @@ -85,7 +88,11 @@ namespace vcpkg::Graphs ExplorationStatus& status = exploration_status[vertex]; if (status == ExplorationStatus::NOT_EXPLORED) { - find_topological_sort_internal(vertex, status, this->vertices, exploration_status, sorted); + find_topological_sort_internal(vertex, + status, + [this](const V& v) { return this->vertices.at(v); }, + exploration_status, + sorted); } } } |