| 744 | // --------------------------------------------------------------------------- |
| 745 | |
| 746 | std::vector<PJ::NodeId> DerivedEngine::topologicalOrder() const { |
| 747 | tsl::robin_map<PJ::NodeId, int> in_degree; |
| 748 | for (const auto& [id, _] : impl_->nodes) { |
| 749 | in_degree[id] = 0; |
| 750 | } |
| 751 | |
| 752 | for (const auto& [upstream, downstream_list] : impl_->downstream_of) { |
| 753 | for (PJ::NodeId downstream : downstream_list) { |
| 754 | if (impl_->nodes.contains(downstream)) { |
| 755 | in_degree[downstream]++; |
| 756 | } |
| 757 | } |
| 758 | } |
| 759 | |
| 760 | // Seed queue with in-degree 0 nodes (sorted for determinism) |
| 761 | std::vector<PJ::NodeId> ready; |
| 762 | ready.reserve(in_degree.size()); |
| 763 | for (const auto& [id, deg] : in_degree) { |
| 764 | if (deg == 0) { |
| 765 | ready.push_back(id); |
| 766 | } |
| 767 | } |
| 768 | std::sort(ready.begin(), ready.end()); |
| 769 | |
| 770 | std::vector<PJ::NodeId> order; |
| 771 | order.reserve(impl_->nodes.size()); |
| 772 | std::size_t head = 0; |
| 773 | |
| 774 | while (head < ready.size()) { |
| 775 | PJ::NodeId n = ready[head++]; |
| 776 | order.push_back(n); |
| 777 | |
| 778 | auto it = impl_->downstream_of.find(n); |
| 779 | if (it == impl_->downstream_of.end()) { |
| 780 | continue; |
| 781 | } |
| 782 | |
| 783 | std::vector<PJ::NodeId> newly_ready; |
| 784 | for (PJ::NodeId m : it->second) { |
| 785 | if (!impl_->nodes.contains(m)) { |
| 786 | continue; |
| 787 | } |
| 788 | if (--in_degree[m] == 0) { |
| 789 | newly_ready.push_back(m); |
| 790 | } |
| 791 | } |
| 792 | // Keep deterministic order within the newly ready set |
| 793 | std::sort(newly_ready.begin(), newly_ready.end()); |
| 794 | for (PJ::NodeId m : newly_ready) { |
| 795 | ready.push_back(m); |
| 796 | } |
| 797 | } |
| 798 | |
| 799 | return order; |
| 800 | } |
| 801 | |
| 802 | // --------------------------------------------------------------------------- |
| 803 | // on_source_committed |