Stoer_Wagner.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef STOER_WAGNER_H
# define STOER_WAGNER_H
 
# include <ah-graph-concepts.H>
 
# include <limits>
# include <vector>
# include <queue>
# include <functional>
# include <htlist.H>
# include <tpl_sgraph.H>
# include <tpl_dynArray.H>
# include <tpl_graph_utils.H>
# include <ah-errors.H>
 
namespace Aleph
{
  template <AlephGraph GT,
            ArcDistance<GT> Distance = Dft_Dist<GT>,
            ArcFilter<GT> SA = Dft_Show_Arc<GT>>
  class Stoer_Wagner_Min_Cut
  {
  public:
    using Node = typename GT::Node;
    using Arc = typename GT::Arc;
    using Weight = typename Distance::Distance_Type;
 
  private:
    Distance distance;
    SA sa;
 
    // Internal representation for contraction
    struct SWNode
    {
      DynList<Node*> members;     // Original nodes in this super-node
      size_t id;                  // Index for adjacency matrix
      bool merged;                // True if merged into another node
    };
 
    // Priority queue entry
    struct PQEntry
    {
      size_t node_id;
      Weight priority;
 
      bool operator<(const PQEntry& other) const
      {
        return priority < other.priority;  // Max-heap: higher priority first
      }
    };
 
    // Adjacency matrix for weights (dense representation for efficiency)
    std::vector<std::vector<Weight>> adj;
    std::vector<SWNode> nodes;
    size_t active_count;
 
    // Initialize internal structures from graph
    void init_from_graph(GT& g)
    {
      const size_t n = g.get_num_nodes();
      adj.assign(n, std::vector<Weight>(n, Weight(0)));
      nodes.resize(n);
      active_count = n;
 
      // Assign IDs to nodes
      size_t id = 0;
      for (typename GT::Node_Iterator it(g); it.has_curr(); it.next_ne())
      {
        auto p = it.get_curr();
        NODE_COUNTER(p) = id;
        nodes[id].members.append(p);
        nodes[id].id = id;
        nodes[id].merged = false;
        ++id;
      }
 
      // Build adjacency matrix
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      {
        auto a = it.get_curr();
        size_t src_id = NODE_COUNTER(g.get_src_node(a));
        size_t tgt_id = NODE_COUNTER(g.get_tgt_node(a));
        Weight w = distance(a);
 
        adj[src_id][tgt_id] += w;
        adj[tgt_id][src_id] += w;  // Undirected
      }
    }
 
    // Maximum Adjacency Search: returns (s, t, cut-of-phase weight)
    std::tuple<size_t, size_t, Weight> minimum_cut_phase()
    {
      const size_t n = nodes.size();
 
      // Find first active node to start
      size_t start = 0;
      while (start < n && nodes[start].merged)
        ++start;
 
      if (start >= n)
        return {0, 0, Weight(0)};
 
      // Priority (sum of weights to nodes in A)
      std::vector<Weight> key(n, Weight(0));
      std::vector<bool> in_A(n, false);
 
      // Use priority queue (max-heap)
      std::priority_queue<PQEntry> pq;
 
      // Initialize: add starting node to A
      in_A[start] = true;
      size_t last = start;
      size_t second_last = start;
 
      // Update priorities for neighbors of start
      for (size_t j = 0; j < n; ++j)
      {
        if (!nodes[j].merged && !in_A[j] && adj[start][j] > Weight(0))
        {
          key[j] = adj[start][j];
          pq.push({j, key[j]});
        }
      }
 
      // Add remaining nodes one by one
      for (size_t count = 1; count < active_count; ++count)
      {
        // Find node with maximum key not in A
        size_t next = n;
        while (!pq.empty())
        {
          auto top = pq.top();
          pq.pop();
 
          if (!in_A[top.node_id] && !nodes[top.node_id].merged &&
              top.priority == key[top.node_id])
          {
            next = top.node_id;
            break;
          }
        }
 
        if (next >= n)
        {
          // Graph is disconnected - find any unvisited node
          for (size_t j = 0; j < n; ++j)
          {
            if (!nodes[j].merged && !in_A[j])
            {
              next = j;
              break;
            }
          }
        }
 
        if (next >= n)
          break;
 
        // Add next to A
        second_last = last;
        last = next;
        in_A[next] = true;
 
        // Update keys for neighbors of next
        for (size_t j = 0; j < n; ++j)
        {
          if (!nodes[j].merged && !in_A[j] && adj[next][j] > Weight(0))
          {
            key[j] += adj[next][j];
            pq.push({j, key[j]});
          }
        }
      }
 
      // Cut-of-phase: weight of edges from last to A
      Weight cut_weight = key[last];
 
      return {second_last, last, cut_weight};
    }
 
    // Merge node t into node s
    void merge_nodes(size_t s, size_t t)
    {
      const size_t n = nodes.size();
 
      // Move members from t to s
      nodes[s].members.concat(nodes[t].members);
      nodes[t].merged = true;
 
      // Update adjacency: combine edges
      for (size_t j = 0; j < n; ++j)
      {
        if (j != s && j != t && !nodes[j].merged)
        {
          adj[s][j] += adj[t][j];
          adj[j][s] = adj[s][j];
        }
      }
 
      // Clear t's edges
      for (size_t j = 0; j < n; ++j)
      {
        adj[t][j] = Weight(0);
        adj[j][t] = Weight(0);
      }
 
      --active_count;
    }
 
  public:
    Stoer_Wagner_Min_Cut() = default;
 
    explicit Stoer_Wagner_Min_Cut(Distance _distance)
      : distance(_distance)
    {}
 
    Weight operator()(GT& g,
                      DynList<Node*>& vs,
                      DynList<Node*>& vt,
                      DynList<Arc*>& cut)
    {
      const size_t n = g.get_num_nodes();
      ah_domain_error_if(n < 2) << "Graph must have at least 2 nodes";
 
      vs.empty();
      vt.empty();
      cut.empty();
 
      init_from_graph(g);
 
      Weight best_cut = std::numeric_limits<Weight>::max();
 
      // Main loop: n-1 phases
      while (active_count > 1)
      {
        auto [s, t, cut_weight] = minimum_cut_phase();
        (void)s;  // Suppress unused warning
 
        if (cut_weight < best_cut)
          best_cut = cut_weight;
 
        // Merge s and t
        merge_nodes(s, t);
      }
 
      // Reconstruct partitions
      // The best cut separates nodes[best_t].members from the rest
      // But nodes have been merged, so we need to track this differently
 
      // Rebuild: run algorithm again but stop at best cut
      init_from_graph(g);
 
      Weight target_cut = best_cut;
      DynList<Node*> cut_side;
 
      while (active_count > 1)
      {
        auto [s, t, cut_weight] = minimum_cut_phase();
 
        if (cut_weight == target_cut && cut_side.is_empty())
        {
          // This is our target cut - save t's side
          for (auto p : nodes[t].members)
            cut_side.append(p);
        }
 
        merge_nodes(s, t);
      }
 
      // Build partitions
      for (auto p : cut_side)
        vt.append(p);
 
      for (typename GT::Node_Iterator it(g); it.has_curr(); it.next_ne())
      {
        auto p = it.get_curr();
        if (!cut_side.exists([p](Node* q) { return p == q; }))
          vs.append(p);
      }
 
      // Find cut arcs
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      {
        auto a = it.get_curr();
        auto src = g.get_src_node(a);
        auto tgt = g.get_tgt_node(a);
 
        bool src_in_vs = vs.exists([src](Node* p) { return p == src; });
        bool tgt_in_vs = vs.exists([tgt](Node* p) { return p == tgt; });
 
        if (src_in_vs != tgt_in_vs)
          cut.append(a);
      }
 
      return best_cut;
    }
 
    Weight min_cut_weight(GT& g)
    {
      const size_t n = g.get_num_nodes();
      if (n < 2)
        return Weight(0);
 
      init_from_graph(g);
 
      Weight best_cut = std::numeric_limits<Weight>::max();
 
      while (active_count > 1)
      {
        auto [s, t, cut_weight] = minimum_cut_phase();
        best_cut = std::min(best_cut, cut_weight);
        merge_nodes(s, t);
      }
 
      return best_cut;
    }
  };
 
  template <AlephGraph GT>
  struct Unit_Weight
  {
    using Distance_Type = size_t;
    size_t operator()(typename GT::Arc*) const { return 1; }
  };
 
} // namespace Aleph
 
# endif // STOER_WAGNER_H