StronglyConnectedComponents.h 2.2 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
  1. /*
  2. * Copyright (c) 2023, Dan Klishch <danilklishch@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/Vector.h>
  8. #include "Compiler/EnableGraphPointers.h"
  9. namespace JSSpecCompiler {
  10. namespace Detail {
  11. template<typename GraphVertex, typename GraphNode>
  12. class StronglyConnectedComponents
  13. : private EnableGraphPointers<StronglyConnectedComponents<GraphVertex, GraphNode>> {
  14. using Self = StronglyConnectedComponents<GraphVertex, GraphNode>;
  15. using Vertex = typename EnableGraphPointers<Self>::Vertex;
  16. public:
  17. StronglyConnectedComponents(Vector<GraphNode> const& graph)
  18. : m_graph(graph)
  19. {
  20. }
  21. Vector<Vector<GraphVertex>> find()
  22. {
  23. Vector<Vector<GraphVertex>> result;
  24. size_t n = m_graph.size();
  25. Self::with_graph(n, [&] {
  26. for (size_t i = 0; i < m_graph.size(); ++i)
  27. find_order(i);
  28. for (size_t i = n; i--;) {
  29. if (!m_order[i]->is_processed) {
  30. result.empend();
  31. find_component(GraphVertex(m_order[i]), result.last());
  32. }
  33. }
  34. });
  35. return result;
  36. }
  37. private:
  38. friend EnableGraphPointers<Self>;
  39. void find_order(Vertex u)
  40. {
  41. if (u->is_visited)
  42. return;
  43. u->is_visited = true;
  44. for (auto v : GraphVertex(u)->incoming_edges)
  45. find_order(Vertex(v));
  46. m_order.append(u);
  47. }
  48. void find_component(GraphVertex u, Vector<GraphVertex>& current_scc)
  49. {
  50. current_scc.empend(u);
  51. Vertex(u)->is_processed = true;
  52. for (auto v : u->outgoing_edges)
  53. if (!Vertex(v)->is_processed)
  54. find_component(v, current_scc);
  55. }
  56. struct NodeData {
  57. bool is_visited = false;
  58. bool is_processed = false;
  59. };
  60. Vector<GraphNode> const& m_graph;
  61. Vector<NodeData> m_nodes;
  62. Vector<Vertex> m_order;
  63. };
  64. }
  65. template<typename NodeData>
  66. auto find_strongly_connected_components(Vector<NodeData> const& graph)
  67. {
  68. using Vertex = RemoveCVReference<decltype(graph[0].outgoing_edges[0])>;
  69. return Detail::StronglyConnectedComponents<Vertex, NodeData>(graph).find();
  70. }
  71. }