yog_ex

defmodule Yog.Flow.MinCut do
  @moduledoc """
  Global minimum cut algorithms for undirected graphs.

  This module finds the [global minimum cut](https://en.wikipedia.org/wiki/Minimum_cut)
  in an undirected weighted graph - the partition of nodes into two non-empty sets
  that minimizes the total weight of edges crossing between the sets.

  ## Algorithm Summary

  | Algorithm | Function | Complexity | Best For |
  |-----------|----------|------------|----------|
  | [Stoer-Wagner](https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm) | `global_min_cut/2` | O(V³) | Dense undirected graphs, exact result |
  | [Karger-Stein](https://en.wikipedia.org/wiki/Karger%27s_algorithm) | `karger_stein/2` | O(V² log³ V) | Large graphs, randomized approach |
  | [Gomory-Hu Tree](https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree) | `gomory_hu_tree/1` | O(V · MaxFlow) | All-pairs min-cut analysis |

  ## Key Concepts

  - **Global Min-Cut**: The minimum cut over all possible partitions of the graph.
  - **s-t Cut**: A cut that separates specific nodes `s` and `t`.
  - **Maximum Adjacency Search**: Orders vertices by strength of connection to the current set (used by Stoer-Wagner).
  - **Edge Contraction**: Merging two nodes while preserving total edge weight to other nodes (used by Karger-Stein).

  ## Gomory-Hu Trees

  The Gomory-Hu tree is a powerful structure that encodes all-pairs min-cuts using only `V-1` max-flow
  computations. In the tree, the min-cut value between any two nodes `u` and `v` is the minimum
  weight on the unique tree path between them.

  Use `gomory_hu_tree/1` to build the tree and `min_cut_query/3` to extract values and partitions.

  <div class="graphviz">
  graph G {
    bgcolor="transparent";
    node [shape=circle, fontname="inherit"];
    edge [fontname="inherit", fontsize=10];
    rankdir=LR;

    1 -- 2 [label="7"];
    2 -- 3 [label="5"];
    2 -- 4 [label="6"];
    
    label="Example Gomory-Hu Tree";
    fontsize=12;
  }
  </div>

  ## Randomized Algorithms

  For very large graphs where exact algorithms (O(V³)) might be slow, `karger_stein/2` 
  provides a randomized approach based on edge contraction. It uses recursive branching 
  to achieve a high probability of success.

  ## Comparison with s-t Min-Cut

  For finding a cut between specific source and sink nodes, use `Yog.Flow.MaxFlow` or the convenience `s_t_min_cut/4`:
  - `s_t_min_cut(graph, s, t, :dinic)`: Efficiently finds the cut separating `s` and `t`.
  - `global_min_cut(graph)`: Finds the minimum weight cut across *any* possible partition.

  ## Examples

  ### Global Minimum Cut (Stoer-Wagner)

      iex> graph = Yog.from_edges(:undirected, [{1, 2, 5}, {2, 3, 3}, {1, 3, 2}])
      iex> result = Yog.Flow.MinCut.global_min_cut(graph)
      iex> result.cut_value
      5

  ### All-Pairs Analysis (Gomory-Hu)

      iex> graph = Yog.from_edges(:undirected, [{1, 2, 3}, {1, 3, 4}, {2, 3, 2}, {2, 4, 5}, {3, 4, 1}])
      iex> tree = Yog.Flow.MinCut.gomory_hu_tree(graph)
      iex> {cut_value, _s, _t} = Yog.Flow.MinCut.min_cut_query(tree, 1, 4)
      iex> cut_value
      6

  ## References

  - [Wikipedia: Minimum Cut](https://en.wikipedia.org/wiki/Minimum_cut)
  - [Wikipedia: Stoer-Wagner Algorithm](https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm)
  - [Wikipedia: Karger's Algorithm](https://en.wikipedia.org/wiki/Karger%27s_algorithm)
  - [Wikipedia: Gomory-Hu Tree](https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree)
  - [CP-Algorithms: Stoer-Wagner](https://cp-algorithms.com/graph/stoer_wagner.html)

  """

  alias Yog.Flow.MaxFlow
  alias Yog.Flow.MinCutResult
  alias Yog.Model
  alias Yog.PairingHeap
  alias Yog.Transform

  @doc """
  Finds the global minimum cut of an undirected weighted graph.

  This implementation uses the Stoer-Wagner algorithm. It repeatedly finds
  an s-t min-cut in a phase using Maximum Adjacency Search and then contracts
  the nodes s and t. The global minimum cut is the minimum of all phase cuts.

  **Time Complexity:** O(V³) (O(V² log V) with priority queue optimization)

  ## Examples

  Simple triangle graph:

      iex> {:ok, graph} = Yog.undirected()
      ...>   |> Yog.add_node(1, "A")
      ...>   |> Yog.add_node(2, "B")
      ...>   |> Yog.add_node(3, "C")
      ...>   |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 2}])
      iex> result = Yog.Flow.MinCut.global_min_cut(graph)
      iex> result.cut_value
      5
      iex> result.source_side_size + result.sink_side_size
      3

  ## Parameters

  - `graph` - The undirected weighted graph
  - `opts` - Options:
    - `:track_partitions` - If `true`, populates the `source_side` and `sink_side`
      fields in the result. (default: `false`)

  ## Notes

  - The graph must be undirected
  - Edge weights must be integers
  - Returns a `Yog.Flow.MinCutResult` struct
  """
  @spec global_min_cut(Yog.graph(), keyword()) :: MinCutResult.t()
  def global_min_cut(graph, opts \\ []) do
    track_partitions = Keyword.get(opts, :track_partitions, false)
    nodes = Map.keys(graph.nodes)

    case length(nodes) do
      n when n <= 1 ->
        if track_partitions do
          side = MapSet.new(nodes)
          MinCutResult.new(0, 0, 0, side, MapSet.new())
        else
          MinCutResult.new(0, 0, 0)
        end

      n ->
        sizes = Map.new(nodes, fn node -> {node, 1} end)
        all_nodes = MapSet.new(nodes)

        if track_partitions do
          partitions = Map.new(nodes, fn node -> {node, MapSet.new([node])} end)
          do_min_cut(graph, nil, n, sizes, partitions, all_nodes)
        else
          do_min_cut(graph, nil, n, sizes, nil, nil)
        end
    end
  end

  defp do_min_cut(graph, best_cut, total_nodes, sizes, partitions, all_nodes) do
    if map_size(graph.nodes) <= 1 do
      best_cut
    else
      {s, t, cut_weight} = maximum_adjacency_search(graph)

      t_size = Map.get(sizes, t, 1)
      s_size = Map.get(sizes, s, 1)

      current_cut =
        if is_nil(best_cut) or cut_weight < best_cut.cut_value do
          if is_nil(partitions) do
            MinCutResult.new(
              cut_weight,
              t_size,
              total_nodes - t_size
            )
          else
            t_partition = Map.fetch!(partitions, t)
            rest_partition = MapSet.difference(all_nodes, t_partition)

            MinCutResult.new(
              cut_weight,
              t_size,
              total_nodes - t_size,
              t_partition,
              rest_partition
            )
          end
        else
          best_cut
        end

      new_sizes =
        sizes
        |> Map.put(s, s_size + t_size)
        |> Map.delete(t)

      new_partitions =
        if is_nil(partitions) do
          nil
        else
          partitions
          |> Map.update!(s, &MapSet.union(&1, Map.fetch!(partitions, t)))
          |> Map.delete(t)
        end

      Transform.contract(graph, s, t, &+/2)
      |> do_min_cut(current_cut, total_nodes, new_sizes, new_partitions, all_nodes)
    end
  end

  @doc """
  Computes the minimum s-t cut using a max-flow algorithm.

  This is a convenience wrapper that delegates to `Yog.Flow.MaxFlow.max_flow/4`
  and extracts the corresponding min-cut from the residual graph.

  ## Parameters

  - `graph` - The flow network
  - `source` - Source node ID
  - `sink` - Sink node ID
  - `algorithm` - Algorithm to use: `:edmonds_karp` (default), `:dinic`, or `:push_relabel`

  ## Examples

      iex> {:ok, graph} = Yog.directed()
      ...>   |> Yog.add_node(1, "s")
      ...>   |> Yog.add_node(2, "a")
      ...>   |> Yog.add_node(3, "t")
      ...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
      iex> result = Yog.Flow.MinCut.s_t_min_cut(graph, 1, 3)
      iex> result.cut_value
      5
  """
  @spec s_t_min_cut(Yog.graph(), Yog.node_id(), Yog.node_id(), atom()) :: MinCutResult.t()
  def s_t_min_cut(graph, source, sink, algorithm \\ :edmonds_karp) do
    graph
    |> MaxFlow.max_flow(source, sink, algorithm)
    |> MaxFlow.extract_min_cut()
  end

  @doc """
  Builds a Gomory-Hu tree representing all-pairs min-cuts in the graph.

  The Gomory-Hu tree is a weighted tree on the same vertex set where the
  minimum edge weight on the path between any two nodes equals their min-cut
  value in the original graph. This implementation uses Gusfield's algorithm,
  requiring only `V-1` max-flow computations.

  ## Examples

      iex> graph = Yog.from_edges(:undirected, [{1, 2, 3}, {1, 3, 4}, {2, 3, 2}, {2, 4, 5}, {3, 4, 1}])
      iex> tree = Yog.Flow.MinCut.gomory_hu_tree(graph)
      iex> length(Yog.Model.all_edges(tree))
      3
  """
  @spec gomory_hu_tree(Yog.graph()) :: Yog.graph()
  def gomory_hu_tree(graph) do
    nodes = Model.all_nodes(graph) |> Enum.sort()

    case nodes do
      [] ->
        Yog.undirected()

      [root] ->
        Yog.undirected() |> Yog.add_node(root, Model.node(graph, root))

      [root | rest] ->
        parent = Map.new(nodes, fn n -> {n, root} end)

        {final_parent, cuts} =
          Enum.reduce(rest, {parent, %{}}, fn v, {par, cuts} ->
            p = par[v]
            result = s_t_min_cut(graph, v, p, :dinic)
            cut_val = result.cut_value

            new_par =
              Enum.reduce(rest, par, fn w, acc ->
                if w > v and acc[w] == p and MapSet.member?(result.source_side, w) do
                  Map.put(acc, w, v)
                else
                  acc
                end
              end)

            new_cuts = Map.put(cuts, {min(v, p), max(v, p)}, cut_val)
            {new_par, new_cuts}
          end)

        tree =
          Enum.reduce(nodes, Yog.undirected(), fn u, acc ->
            Model.add_node(acc, u, Model.node(graph, u))
          end)

        Enum.reduce(Map.to_list(final_parent), {tree, MapSet.new()}, fn {v, p},
                                                                        {tree_acc, seen} ->
          edge = {min(v, p), max(v, p)}

          if v == p or MapSet.member?(seen, edge) do
            {tree_acc, seen}
          else
            weight = cuts[edge] || 0
            {:ok, new_tree} = Model.add_edge(tree_acc, v, p, weight)
            {new_tree, MapSet.put(seen, edge)}
          end
        end)
        |> elem(0)
    end
  end

  @doc """
  Queries the min-cut value and partitions between two nodes using a Gomory-Hu tree.

  Returns `{cut_value, partition_s, partition_t}` where `cut_value` is the min-cut
  between `node_a` and `node_b` in the original graph, and the partitions are the
  two sides of that cut.

  ## Examples

      iex> graph = Yog.from_edges(:undirected, [{1, 2, 3}, {1, 3, 4}, {2, 3, 2}, {2, 4, 5}, {3, 4, 1}])
      iex> tree = Yog.Flow.MinCut.gomory_hu_tree(graph)
      iex> {cut_value, _s, _t} = Yog.Flow.MinCut.min_cut_query(tree, 1, 4)
      iex> cut_value
      6
  """
  @spec min_cut_query(Yog.graph(), Yog.node_id(), Yog.node_id()) ::
          {number(), MapSet.t(Yog.node_id()), MapSet.t(Yog.node_id())}
  def min_cut_query(tree, node_a, node_b) do
    nodes = Model.all_nodes(tree)

    if node_a == node_b do
      {0, MapSet.new([node_a]), MapSet.difference(MapSet.new(nodes), MapSet.new([node_a]))}
    else
      path = tree_path(tree, node_a, node_b)
      {{u, v}, min_weight} = min_edge_on_path(tree, path)

      comp_a = component_without_edge(tree, node_a, u, v)
      comp_b = MapSet.difference(MapSet.new(nodes), comp_a)

      {min_weight, comp_a, comp_b}
    end
  end

  # Finds the unique path between two nodes in a tree using BFS.
  defp tree_path(tree, start, target) do
    queue = :queue.in({start, [start]}, :queue.new())
    visited = MapSet.new([start])
    bfs_path(tree, queue, visited, target)
  end

  defp bfs_path(tree, queue, visited, target) do
    case :queue.out(queue) do
      {:empty, _} ->
        []

      {{:value, {node, path}}, rest} ->
        if node == target do
          Enum.reverse(path)
        else
          neighbors = Model.neighbor_ids(tree, node)

          {next_q, next_v} =
            Enum.reduce(neighbors, {rest, visited}, fn n, {q, v} ->
              if MapSet.member?(v, n) do
                {q, v}
              else
                {:queue.in({n, [n | path]}, q), MapSet.put(v, n)}
              end
            end)

          bfs_path(tree, next_q, next_v, target)
        end
    end
  end

  # Finds the minimum weight edge on a given tree path.
  defp min_edge_on_path(tree, path) do
    path
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.reduce(nil, fn [u, v], acc ->
      w = Model.edge_data(tree, u, v) || Model.edge_data(tree, v, u) || 0

      case acc do
        nil -> {{u, v}, w}
        {_, w_acc} when w < w_acc -> {{u, v}, w}
        _ -> acc
      end
    end)
  end

  # Returns all nodes in the component containing `start` after removing edge {u, v}.
  defp component_without_edge(tree, start, u, v) do
    do_component(MapSet.new([start]), [start], tree, u, v)
  end

  defp do_component(visited, [], _tree, _u, _v), do: visited

  defp do_component(visited, [node | rest], tree, u, v) do
    neighbors = Model.neighbor_ids(tree, node)

    {new_visited, new_stack} =
      Enum.reduce(neighbors, {visited, rest}, fn n, {vis, stack} ->
        skip =
          MapSet.member?(vis, n) or
            (node == u and n == v) or
            (node == v and n == u)

        if skip do
          {vis, stack}
        else
          {MapSet.put(vis, n), [n | stack]}
        end
      end)

    do_component(new_visited, new_stack, tree, u, v)
  end

  @doc """
  Finds the global minimum cut using the randomized Karger-Stein algorithm.

  Karger-Stein uses repeated random edge contraction with recursive branching
  to achieve high success probability. It is particularly effective on large
  graphs where the exact Stoer-Wagner algorithm may be slower, as the randomized
  approach can often find the global minimum cut with very few iterations.

  ## Parameters

  - `graph` - The undirected weighted graph
  - `opts` - Options:
    - `:iterations` - Number of independent runs of the recursive fast-cut
      procedure (default: `max(1, trunc(n * log2(n + 1)))`). Increasing the
      number of iterations improves the success probability.

  ## Examples

      iex> graph = Yog.from_edges(:undirected, [{1, 2, 5}, {2, 3, 3}, {1, 3, 2}])
      iex> result = Yog.Flow.MinCut.karger_stein(graph)
      iex> result.cut_value
      5
  """
  @spec karger_stein(Yog.graph(), keyword()) :: MinCutResult.t()
  def karger_stein(graph, opts \\ []) do
    nodes = Map.keys(graph.nodes)
    n = length(nodes)

    if n <= 1 do
      side = MapSet.new(nodes)
      MinCutResult.new(0, 0, 0, side, MapSet.new())
    else
      {adj, vertices} = build_karger_adj(graph)

      default_iterations = max(1, trunc(n * :math.log2(n + 1)))
      iterations = Keyword.get(opts, :iterations, default_iterations)

      {best_cut, {best_a, best_b}} =
        Enum.reduce(1..iterations, {nil, nil}, fn _, {best_val, best_part} ->
          {cut_val, {part_a, part_b}} = fast_cut(adj, vertices)

          if is_nil(best_val) or cut_val < best_val do
            {cut_val, {part_a, part_b}}
          else
            {best_val, best_part}
          end
        end)

      MinCutResult.new(
        best_cut,
        MapSet.size(best_a),
        MapSet.size(best_b),
        best_a,
        best_b
      )
    end
  end

  # ==========================================================================
  # Karger-Stein Internals
  # ==========================================================================

  defp build_karger_adj(graph) do
    edges = Yog.Model.all_edges(graph)

    adj =
      Enum.reduce(edges, %{}, fn {u, v, w}, acc ->
        acc
        |> Map.update(u, %{v => w}, &Map.put(&1, v, w))
        |> Map.update(v, %{u => w}, &Map.put(&1, u, w))
      end)

    vertices = Map.new(Map.keys(graph.nodes), fn u -> {u, MapSet.new([u])} end)
    {adj, vertices}
  end

  defp fast_cut(adj, vertices) when map_size(vertices) <= 6 do
    brute_force_min_cut(adj, vertices)
  end

  defp fast_cut(adj, vertices) do
    n = map_size(vertices)
    t = trunc(Float.ceil(1 + n / :math.sqrt(2)))

    {adj1, vertices1} = contract_until(adj, vertices, t)
    {adj2, vertices2} = contract_until(adj, vertices, t)

    {cut1, part1} = fast_cut(adj1, vertices1)
    {cut2, part2} = fast_cut(adj2, vertices2)

    if cut1 <= cut2 do
      {cut1, part1}
    else
      {cut2, part2}
    end
  end

  defp contract_until(adj, vertices, target_count) do
    if map_size(vertices) <= target_count do
      {adj, vertices}
    else
      case random_edge(adj, vertices) do
        nil ->
          {adj, vertices}

        {u, v} ->
          {new_adj, new_vertices} = contract_edge(adj, vertices, u, v)
          contract_until(new_adj, new_vertices, target_count)
      end
    end
  end

  defp contract_edge(adj, vertices, u, v) do
    u_set = Map.fetch!(vertices, u)
    v_set = Map.fetch!(vertices, v)
    merged_set = MapSet.union(u_set, v_set)

    u_adj = Map.get(adj, u, %{})
    v_adj = Map.get(adj, v, %{})

    merged_adj =
      v_adj
      |> Enum.reduce(u_adj, fn {n, w}, acc ->
        if n == u or n == v do
          acc
        else
          Map.update(acc, n, w, &(&1 + w))
        end
      end)
      |> Map.delete(u)
      |> Map.delete(v)

    adj =
      v_adj
      |> Enum.reduce(adj, fn {n, w}, acc ->
        if n == u or n == v do
          acc
        else
          n_adj =
            acc
            |> Map.fetch!(n)
            |> Map.delete(v)
            |> Map.update(u, w, &(&1 + w))

          Map.put(acc, n, n_adj)
        end
      end)
      |> Map.put(u, merged_adj)
      |> Map.delete(v)

    vertices = vertices |> Map.put(u, merged_set) |> Map.delete(v)

    {adj, vertices}
  end

  defp random_edge(adj, vertices) do
    {edges, _} =
      vertices
      |> Map.keys()
      |> Enum.reduce({[], MapSet.new()}, fn u, {e_acc, seen} ->
        adj
        |> Map.get(u, %{})
        |> Enum.reduce({e_acc, seen}, fn {v, w}, {edges, s} ->
          key = {u, v}

          if MapSet.member?(s, key) do
            {edges, s}
          else
            {[{u, v, w} | edges], MapSet.put(s, {v, u})}
          end
        end)
      end)

    total = Enum.reduce(edges, 0, fn {_, _, w}, acc -> acc + w end)

    if total == 0 do
      nil
    else
      target = :rand.uniform() * total
      pick_weighted_edge(edges, target, 0)
    end
  end

  defp pick_weighted_edge([{u, v, w} | rest], target, acc) do
    acc = acc + w

    if acc >= target do
      {u, v}
    else
      pick_weighted_edge(rest, target, acc)
    end
  end

  defp brute_force_min_cut(adj, vertices) do
    vertex_list = Map.keys(vertices)
    n = length(vertex_list)

    {best_cut, {side_a_supers, side_b_supers}} =
      1..(trunc(:math.pow(2, n - 1)) - 1)
      |> Enum.reduce({nil, nil}, fn mask, {best_val, best_part} ->
        {side_a, side_b} = partition_from_mask(vertex_list, mask)
        cut_val = cut_weight_between(adj, side_a, side_b)

        if is_nil(best_val) or cut_val < best_val do
          {cut_val, {side_a, side_b}}
        else
          {best_val, best_part}
        end
      end)

    side_a_nodes = flatten_partition(vertices, side_a_supers)
    side_b_nodes = flatten_partition(vertices, side_b_supers)

    {best_cut, {side_a_nodes, side_b_nodes}}
  end

  defp partition_from_mask(vertex_list, mask) do
    vertex_list
    |> Enum.with_index()
    |> Enum.reduce({MapSet.new(), MapSet.new()}, fn {v, i}, {a, b} ->
      if Bitwise.band(Bitwise.bsr(mask, i), 1) == 1 do
        {MapSet.put(a, v), b}
      else
        {a, MapSet.put(b, v)}
      end
    end)
  end

  defp cut_weight_between(adj, side_a, side_b) do
    side_a
    |> MapSet.to_list()
    |> Enum.reduce(0, fn u, acc ->
      u_adj = Map.get(adj, u, %{})

      side_b
      |> MapSet.to_list()
      |> Enum.reduce(acc, fn v, inner_acc ->
        inner_acc + Map.get(u_adj, v, 0)
      end)
    end)
  end

  defp flatten_partition(vertices, supernode_set) do
    supernode_set
    |> MapSet.to_list()
    |> Enum.reduce(MapSet.new(), fn u, acc ->
      MapSet.union(acc, Map.fetch!(vertices, u))
    end)
  end

  # Maximum Adjacency Search: finds the two most tightly connected nodes.
  # Returns {s, t, cut_weight} where:
  # - s: second-to-last node added
  # - t: last node added
  # - cut_weight: accumulated weight in the MAS weights dict for t
  defp maximum_adjacency_search(graph) do
    nodes = Map.keys(graph.nodes)
    [start | rest] = nodes

    # Direct edge access for performance
    out_edges = graph.out_edges

    initial_dists =
      case Map.fetch(out_edges, start) do
        {:ok, neighbors} ->
          List.foldl(Map.to_list(neighbors), %{}, fn {neighbor, weight}, acc ->
            Map.put(acc, neighbor, weight)
          end)

        :error ->
          %{}
      end

    pq =
      List.foldl(rest, PairingHeap.new(fn a, b -> a >= b end), fn node, acc ->
        dist = Map.get(initial_dists, node, 0)
        PairingHeap.push(acc, {dist, node})
      end)

    remaining = MapSet.new(rest)

    {final_order, final_weights} =
      build_mas_order(
        out_edges,
        [start],
        remaining,
        initial_dists,
        pq
      )

    [t, s | _] = final_order

    cut_weight = Map.get(final_weights, t, 0)

    {s, t, cut_weight}
  end

  # Builds the MAS ordering by greedily adding the most tightly connected node.
  # Uses direct out_edges access for performance.
  defp build_mas_order(out_edges, current_order, remaining, weights, queue) do
    if MapSet.size(remaining) == 0 do
      {current_order, weights}
    else
      {node, new_queue} = get_next_mas_node(queue, remaining, weights)
      new_remaining = MapSet.delete(remaining, node)

      {new_weights, updated_queue} =
        case Map.fetch(out_edges, node) do
          {:ok, neighbors} ->
            List.foldl(Map.to_list(neighbors), {weights, new_queue}, fn {neighbor, weight},
                                                                        {weights_acc, queue_acc} ->
              if MapSet.member?(new_remaining, neighbor) do
                existing_w = Map.get(weights_acc, neighbor, 0)
                new_w = existing_w + weight

                new_weights_acc = Map.put(weights_acc, neighbor, new_w)
                new_queue_acc = PairingHeap.push(queue_acc, {new_w, neighbor})

                {new_weights_acc, new_queue_acc}
              else
                {weights_acc, queue_acc}
              end
            end)

          :error ->
            {weights, new_queue}
        end

      build_mas_order(
        out_edges,
        [node | current_order],
        new_remaining,
        new_weights,
        updated_queue
      )
    end
  end

  defp get_next_mas_node(queue, remaining, weights) do
    case PairingHeap.pop(queue) do
      {:ok, {w, node}, q_rest} ->
        if MapSet.member?(remaining, node) do
          current_weight = Map.get(weights, node, 0)

          if w == current_weight do
            {node, q_rest}
          else
            get_next_mas_node(q_rest, remaining, weights)
          end
        else
          get_next_mas_node(q_rest, remaining, weights)
        end

      :error ->
        [node | _] = MapSet.to_list(remaining)
        {node, queue}
    end
  end
end