Extract toposort into a free function
MODIFY
include/vcpkg_Graphs.h
include/vcpkg_Graphs.h
@@ -17,10 +17,7 @@ namespace vcpkg::Graphs
FULLY_EXPLORED
};
- template <class V>
- class Graph
- {
- template <class Func>
+ template <class V, class Func>
static void topological_sort_internal(V vertex,
ExplorationStatus& status,
const Func adjacency_list_provider,
@@ -43,13 +40,32 @@ namespace vcpkg::Graphs
throw std::runtime_error("cycle in graph");
}
}
-
status = ExplorationStatus::FULLY_EXPLORED;
sorted.push_back(vertex);
}
- public:
+ 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);
+ }
+ }
+ 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,
+ topological_sort_internal(vertex, status,
[this](const V& v) { return this->vertices.at(v); },
- exploration_status,
- sorted);
+ exploration_status, sorted);
}
}
}

Extract toposort into a free function