<commit_before>/*
This is port <NAME>'s Python code (http://jorisvr.nl/article/maximum-matching) to Scala language.

Weighted maximum matching in general graphs.

The algorithm is taken from "Efficient Algorithms for Finding Maximum
Matching in Graphs" by <NAME>, ACM Computing Surveys, 1986.
It is based on the "blossom" method for finding augmenting paths and
the "primal-dual" method for finding a matching of maximum weight, both
due to Jack Edmonds.
Some ideas came from "Implementation of algorithms for maximum matching
on non-bipartite graphs" by <NAME>, Standford Ph.D. thesis, 1973.

A C program for maximum weight matching by <NAME> was used extensively
to validate this new code.
*/

package lila.tournament
package arena

import scala.annotation.tailrec

object WMMatching {
  def maxWeightMatching (edges: Array[(Int, Int, Int)], maxcardinality: Boolean) : Array[Int] = {
    /*
    Compute a maximum-weighted matching in the general undirected
    weighted graph given by "edges".  If "maxcardinality" is true,
    only maximum-cardinality matchings are considered as solutions.

    Edges is a sequence of tuples (i, j, wt) describing an undirected
    edge between vertex i and vertex j with weight wt.  There is at most
    one edge between any two vertices; no vertex has an edge to itself.
    Vertices are identified by consecutive, non-negative integers.

    Return a list "mate", such that mate(i) == j if vertex i is
    matched to vertex j, and mate(i) == -1 if vertex i is not matched.

    This function takes time O(n ** 3).

    Vertices are numbered 0 .. (nvertex-1).
    Non-trivial blossoms are numbered nvertex .. (2*nvertex-1)

    Edges are numbered 0 .. (nedge-1).
    Edge endpoints are numbered 0 .. (2*nedge-1), such that endpoints
    (2*k) and (2*k+1) both belong to edge k.

    Many terms used in the comments (sub-blossom, T-vertex) come from
    the paper by Galil; read the paper before reading this code.

    */
    val nedge = edges.length
    val nvertex = 1 + edges.view.map ( x => x._1.max (x._2) ).max
    // Find the maximum edge weight.
    val maxweight = edges.view.map(_._3).max.max(0)
    // If p is an edge endpoint,
    // endpoint(p) is the vertex to which endpoint p is attached.
    val endpoint:Array[Int] = edges.flatMap ( x => List(x._1, x._2))
    //If v is a vertex,
    //neighbend(v) is the list of remote endpoints of the edges attached to v.
    val neighbend:Array[List[Int]] = Array.fill(nvertex)(Nil)
    edges.zipWithIndex.reverseIterator.foreach { case ((i, j, w), k) => neighbend(i) ::= (2 * k + 1); neighbend(j) ::= (2 * k) }

    // If v is a vertex,
    // mate(v) is the remote endpoint of its matched edge, or -1 if it is single
    // (i.e. endpoint(mate(v)) is v's partner vertex).
    // Initially all vertices are single; updated during augmentation.
    val mate: Array[Int] = Array.fill(nvertex)(-1)

    /*
    If b is a top-level blossom,
    label(b) is 0 if b is unlabeled (free);
                1 if b is an S-vertex/blossom;
                2 if b is a T-vertex/blossom.
    The label of a vertex is found by looking at the label of its
    top-level containing blossom.
    If v is a vertex inside a T-blossom,
    label(v) is 2 iff v is reachable from an S-vertex outside the blossom.
    Labels are assigned during a stage and reset after each augmentation.
    */
    var label: Array[Int] = Array.fill(2 * nvertex)(0)
    /*
    If b is a labeled top-level blossom,
    labelend(b) is the remote endpoint of the edge through which b obtained
    its label, or -1 if b's base vertex is single.
    If v is a vertex inside a T-blossom and label(v) == 2,
    labelend(v) is the remote endpoint of the edge through which v is
    reachable from outside the blossom.
    */
    val labelend: Array[Int] = Array.fill(2 * nvertex)(-1)

    /*
    If v is a vertex, inblossom(v) is the top-level blossom to which v belongs.
    If v is a top-level vertex, v is itself a blossom (a trivial blossom)
    and inblossom(v) == v.
    Initially all vertices are top-level trivial blossoms.
    */
    val inblossom: Array[Int] = Array.range(0, nvertex)

    /*
    If b is a sub-blossom,
    blossomparent(b) is its immediate parent (sub-)blossom.
    If b is a top-level blossom, blossomparent(b) is -1.
    */
    val blossomparent: Array[Int] = Array.fill(2 * nvertex)(-1)
    /*
    If b is a non-trivial (sub-)blossom,
    blossomchilds(b) is an ordered list of its sub-blossoms, starting with
    the base and going round the blossom.
    */
    val blossomchilds: Array[Array[Int]] = new Array(2 * nvertex)

    // If b is a (sub-)blossom,
    // blossombase(b) is its base VERTEX (i.e. recursive sub-blossom).
    val blossombase: Array[Int] = Array.tabulate(2*nvertex) { i:Int => if (i < nvertex) i else -1 }

    /*
    If b is a non-trivial (sub-)blossom,
    blossomendps(b) is a list of endpoints on its connecting edges,
    such that blossomendps(b)(i) is the local endpoint of blossomchilds(b)(i)
    on the edge that connects it to blossomchilds(b)(wrap(i+1)).
    */
    val blossomendps: Array[Array[Int]] = new Array(2 * nvertex)

    /*
    If v is a free vertex (or an unreached vertex inside a T-blossom),
    bestedge(v) is the edge to an S-vertex with least slack,
    or -1 if there is no such edge.
    If b is a (possibly trivial) top-level S-blossom,
    bestedge(b) is the least-slack edge to a different S-blossom,
    or -1 if there is no such edge.
    This is used for efficient computation of delta2 and delta3.
    */
    var bestedge: Array[Int] = Array.fill(2 * nvertex)(-1)

    // If b is a non-trivial top-level S-blossom,
    // blossombestedges(b) is a list of least-slack edges to neighbouring
    // S-blossoms, or None if no such list has been computed yet.
    // This is used for efficient computation of delta3.
    val blossombestedges: Array[List[Int]] = new Array(2 * nvertex)

    // List of currently unused blossom numbers.
    var unusedblossoms = List.range(nvertex, 2 * nvertex)
    var allocatedvertex = nvertex

    // If v is a vertex,
    // dualvar(v) = 2 * u(v) where u(v) is the v's variable in the dual
    // optimization problem (multiplication by two ensures integer values
    // throughout the algorithm if all edge weights are integers).
    // If b is a non-trivial blossom,
    // dualvar(b) = z(b) where z(b) is b's variable in the dual optimization
    // problem.
    val dualvar: Array[Int] = Array.tabulate(2*nvertex) { i:Int => if (i < nvertex) maxweight else 0 }

    // If allowedge(k) is true, edge k has zero slack in the optimization<commit_msg>WMMatching: var->val wherever the compiler accepts it<commit_after>/*
This is port <NAME>'s Python code (http://jorisvr.nl/article/maximum-matching) to Scala language.

Weighted maximum matching in general graphs.

The algorithm is taken from "Efficient Algorithms for Finding Maximum
Matching in Graphs" by <NAME>, ACM Computing Surveys, 1986.
It is based on the "blossom" method for finding augmenting paths and
the "primal-dual" method for finding a matching of maximum weight, both
due to Jack Edmonds.
Some ideas came from "Implementation of algorithms for maximum matching
on non-bipartite graphs" by <NAME>, Standford Ph.D. thesis, 1973.

A C program for maximum weight matching by <NAME> was used extensively
to validate this new code.
*/

package lila.tournament
package arena

import scala.annotation.tailrec

object WMMatching {
  def maxWeightMatching (edges: Array[(Int, Int, Int)], maxcardinality: Boolean) : Array[Int] = {
    /*
    Compute a maximum-weighted matching in the general undirected
    weighted graph given by "edges".  If "maxcardinality" is true,
    only maximum-cardinality matchings are considered as solutions.

    Edges is a sequence of tuples (i, j, wt) describing an undirected
    edge between vertex i and vertex j with weight wt.  There is at most
    one edge between any two vertices; no vertex has an edge to itself.
    Vertices are identified by consecutive, non-negative integers.

    Return a list "mate", such that mate(i) == j if vertex i is
    matched to vertex j, and mate(i) == -1 if vertex i is not matched.

    This function takes time O(n ** 3).

    Vertices are numbered 0 .. (nvertex-1).
    Non-trivial blossoms are numbered nvertex .. (2*nvertex-1)

    Edges are numbered 0 .. (nedge-1).
    Edge endpoints are numbered 0 .. (2*nedge-1), such that endpoints
    (2*k) and (2*k+1) both belong to edge k.

    Many terms used in the comments (sub-blossom, T-vertex) come from
    the paper by Galil; read the paper before reading this code.

    */
    val nedge = edges.length
    val nvertex = 1 + edges.view.map ( x => x._1.max (x._2) ).max
    // Find the maximum edge weight.
    val maxweight = edges.view.map(_._3).max.max(0)
    // If p is an edge endpoint,
    // endpoint(p) is the vertex to which endpoint p is attached.
    val endpoint:Array[Int] = edges.flatMap ( x => List(x._1, x._2))
    //If v is a vertex,
    //neighbend(v) is the list of remote endpoints of the edges attached to v.
    val neighbend:Array[List[Int]] = Array.fill(nvertex)(Nil)
    edges.zipWithIndex.reverseIterator.foreach { case ((i, j, w), k) => neighbend(i) ::= (2 * k + 1); neighbend(j) ::= (2 * k) }

    // If v is a vertex,
    // mate(v) is the remote endpoint of its matched edge, or -1 if it is single
    // (i.e. endpoint(mate(v)) is v's partner vertex).
    // Initially all vertices are single; updated during augmentation.
    val mate: Array[Int] = Array.fill(nvertex)(-1)

    /*
    If b is a top-level blossom,
    label(b) is 0 if b is unlabeled (free);
                1 if b is an S-vertex/blossom;
                2 if b is a T-vertex/blossom.
    The label of a vertex is found by looking at the label of its
    top-level containing blossom.
    If v is a vertex inside a T-blossom,
    label(v) is 2 iff v is reachable from an S-vertex outside the blossom.
    Labels are assigned during a stage and reset after each augmentation.
    */
    val label: Array[Int] = Array.fill(2 * nvertex)(0)
    /*
    If b is a labeled top-level blossom,
    labelend(b) is the remote endpoint of the edge through which b obtained
    its label, or -1 if b's base vertex is single.
    If v is a vertex inside a T-blossom and label(v) == 2,
    labelend(v) is the remote endpoint of the edge through which v is
    reachable from outside the blossom.
    */
    val labelend: Array[Int] = Array.fill(2 * nvertex)(-1)

    /*
    If v is a vertex, inblossom(v) is the top-level blossom to which v belongs.
    If v is a top-level vertex, v is itself a blossom (a trivial blossom)
    and inblossom(v) == v.
    Initially all vertices are top-level trivial blossoms.
    */
    val inblossom: Array[Int] = Array.range(0, nvertex)

    /*
    If b is a sub-blossom,
    blossomparent(b) is its immediate parent (sub-)blossom.
    If b is a top-level blossom, blossomparent(b) is -1.
    */
    val blossomparent: Array[Int] = Array.fill(2 * nvertex)(-1)
    /*
    If b is a non-trivial (sub-)blossom,
    blossomchilds(b) is an ordered list of its sub-blossoms, starting with
    the base and going round the blossom.
    */
    val blossomchilds: Array[Array[Int]] = new Array(2 * nvertex)

    // If b is a (sub-)blossom,
    // blossombase(b) is its base VERTEX (i.e. recursive sub-blossom).
    val blossombase: Array[Int] = Array.tabulate(2*nvertex) { i:Int => if (i < nvertex) i else -1 }

    /*
    If b is a non-trivial (sub-)blossom,
    blossomendps(b) is a list of endpoints on its connecting edges,
    such that blossomendps(b)(i) is the local endpoint of blossomchilds(b)(i)
    on the edge that connects it to blossomchilds(b)(wrap(i+1)).
    */
    val blossomendps: Array[Array[Int]] = new Array(2 * nvertex)

    /*
    If v is a free vertex (or an unreached vertex inside a T-blossom),
    bestedge(v) is the edge to an S-vertex with least slack,
    or -1 if there is no such edge.
    If b is a (possibly trivial) top-level S-blossom,
    bestedge(b) is the least-slack edge to a different S-blossom,
    or -1 if there is no such edge.
    This is used for efficient computation of delta2 and delta3.
    */
    val bestedge: Array[Int] = Array.fill(2 * nvertex)(-1)

    // If b is a non-trivial top-level S-blossom,
    // blossombestedges(b) is a list of least-slack edges to neighbouring
    // S-blossoms, or None if no such list has been computed yet.
    // This is used for efficient computation of delta3.
    val blossombestedges: Array[List[Int]] = new Array(2 * nvertex)

    // List of currently unused blossom numbers.
    var unusedblossoms = List.range(nvertex, 2 * nvertex)
    var allocatedvertex = nvertex

    // If v is a vertex,
    // dualvar(v) = 2 * u(v) where u(v) is the v's variable in the dual
    // optimization problem (multiplication by two ensures integer values
    // throughout the algorithm if all edge weights are integers).
    // If b is a non-trivial blossom,
    // dualvar(b) = z(b) where z(b) is b's variable in the dual optimization
    // problem.
    val dualvar: Array[Int] = Array.tabulate(2*nvertex) { i:Int => if (i < nvertex) maxweight else 0 }

    // If allowedge(k) is true, edge k has zero slack in the optimization
{'fraction_non_alphanumeric': 0.09677662298538936, 'fraction_numerical': 0.009790631119144449, 'mean_word_length': 2.880479251899474, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1685824', 'n_tokens_mistral': 4367, 'n_tokens_neox': 4145, 'n_words': 1779}