code: def maximal_independent_set(
      i, j, keep=True, tie_breaker=None, keyed=True
  ) -> Table:
      """Return a table containing the vertices in a near
      `maximal independent set <https://en.wikipedia.org/wiki/Maximal_independent_set>`_
      of an undirected graph whose edges are given by a two-column table.
  
      Examples
      --------
      Run PC-relate and compute pairs of closely related individuals:
  
      >>> pc_rel = hl.pc_relate(dataset.GT, 0.001, k=2, statistics='kin')
      >>> pairs = pc_rel.filter(pc_rel['kin'] > 0.125)
  
      Starting from the above pairs, prune individuals from a dataset until no
      close relationships remain:
  
      >>> related_samples_to_remove = hl.maximal_independent_set(pairs.i, pairs.j, False)
      >>> result = dataset.filter_cols(
      ...     hl.is_defined(related_samples_to_remove[dataset.col_key]), keep=False)
  
      Starting from the above pairs, prune individuals from a dataset until no
      close relationships remain, preferring to keep cases over controls:
  
      >>> samples = dataset.cols()
      >>> pairs_with_case = pairs.key_by(
      ...     i=hl.struct(id=pairs.i, is_case=samples[pairs.i].is_case),
      ...     j=hl.struct(id=pairs.j, is_case=samples[pairs.j].is_case))
      >>> def tie_breaker(l, r):
      ...     return hl.if_else(l.is_case & ~r.is_case, -1,
      ...                       hl.if_else(~l.is_case & r.is_case, 1, 0))
      >>> related_samples_to_remove = hl.maximal_independent_set(
      ...    pairs_with_case.i, pairs_with_case.j, False, tie_breaker)
      >>> result = dataset.filter_cols(hl.is_defined(
      ...     related_samples_to_remove.key_by(
      ...        s = related_samples_to_remove.node.id.s)[dataset.col_key]), keep=False)
  
      Notes
      -----
  
      The vertex set of the graph is implicitly all the values realized by `i`
      and `j` on the rows of this table. Each row of the table corresponds to an
      undirected edge between the vertices given by evaluating `i` and `j` on
      that row. An undirected edge may appear multiple times in the table and
      will not affect the output. Vertices with self-edges are removed as they
      are not independent of themselves.
  
      The expressions for `i` and `j` must have the same type.
  
      The value of `keep` determines whether the vertices returned are those
      in the maximal independent set, or those in the complement of this set.
      This is useful if you need to filter a table without removing vertices that
      don't appear in the graph at all.
  
      This method implements a greedy algorithm which iteratively removes a
      vertex of highest degree until the graph contains no edges. The greedy
      algorithm always returns an independent set, but the set may not always
      be perfectly maximal.
  
      `tie_breaker` is a Python function taking two arguments---say `l` and
      `r`---each of which is an :class:`~.Expression` of the same type as `i` and
      `j`. `tie_breaker` returns a :class:`~.NumericExpression`, which defines an
      ordering on nodes. A pair of nodes can be ordered in one of three ways, and
      `tie_breaker` must encode the relationship as follows:
  
       - if ``l < r`` then ``tie_breaker`` evaluates to some negative integer
       - if ``l == r`` then ``tie_breaker`` evaluates to 0
       - if ``l > r`` then ``tie_breaker`` evaluates to some positive integer
  
      For example, the usual ordering on the integers is defined by: ``l - r``.
  
      The `tie_breaker` function must satisfy the following property:
      ``tie_breaker(l, r) == -tie_breaker(r, l)``.
  
      When multiple nodes have the same degree, this algorithm will order the
      nodes according to ``tie_breaker`` and remove the *largest* node.
  
      If `keyed` is ``False``, then a node may appear twice in the resulting
      table.
  
      Parameters
      ----------
      i : :class:`.Expression`
          Expression to compute one endpoint of an edge.
      j : :class:`.Expression`
          Expression to compute another endpoint of an edge.
      keep : :obj:`bool`
          If ``True``, return vertices in set. If ``False``, return vertices removed.
      tie_breaker : function
          Function used to order nodes with equal degree.
      keyed : :obj:`bool`
          If ``True``, key the resulting table by the `node` field, this requires
          a sort.
  
      Returns
      -------
      :class:`.Table`
          Table with the set of independent vertices. The table schema is one row
          field `node` which has the same type as input expressions `i` and `j`.
      """
  
      if i.dtype != j.dtype:
          raise ValueError(
              "'maximal_independent_set' expects arguments `i` and `j` to have same type. "
              "Found {} and {}.".format(i.dtype, j.dtype)
          )
  
      source = i._indices.source
      if not isinstance(source, Table):
          raise ValueError(
              "'maximal_independent_set' expects an expression of 'Table'. Found {}".format(
                  "expression of '{}'".format(source.__class__)
                  if source is not None
                  else "scalar expression"
              )
          )
  
      if i._indices.source != j._indices.source:
          raise ValueError(
              "'maximal_independent_set' expects arguments `i` and `j` to be expressions of the same Table. "
              "Found\n{}\n{}".format(i, j)
          )
  
      node_t = i.dtype
  
      if tie_breaker:
          wrapped_node_t = ttuple(node_t)
          left_id = Env.get_uid()
          right_id = Env.get_uid()
          left = construct_variable(left_id, wrapped_node_t)
          right = construct_variable(right_id, wrapped_node_t)
          tie_breaker_expr = hl.float64(tie_breaker(left[0], right[0]))
          tie_breaker_ir = tie_breaker_expr._ir
          t, _ = source._process_joins(i, j, tie_breaker_expr)
      else:
          left_id, right_id, tie_breaker_ir = None, None, None
          t, _ = source._process_joins(i, j)
  
      edges = t.select(__i=i, __j=j).key_by().select("__i", "__j")
      edges = edges.checkpoint(new_temp_file())
  
      mis_nodes = hl.set(
          construct_expr(
              ir.ArrayMaximalIndependentSet(
                  edges.collect(_localize=False)._ir,
                  left_id,
                  right_id,
                  tie_breaker_ir,
              ),
              hl.tarray(node_t),
          )
      )
  
      nodes = edges.select(node=[edges.__i, edges.__j])
      nodes = nodes.explode(nodes.node)
      nodes = nodes.annotate_globals(mis_nodes=mis_nodes)
      nodes = nodes.filter(nodes.mis_nodes.contains(nodes.node), keep)
      nodes = nodes.select_globals()
      if keyed:
          return nodes.key_by("node").distinct()
      return nodes
  
imports: from typing import Union
  import hail
  from hail.expr import Expression, expr_numeric, expr_array, expr_interval, expr_any, construct_expr, construct_variable
  from hail.expr.types import tlocus, tarray, tstr, tstruct, ttuple
  from hail.matrixtable import MatrixTable
  from hail.table import Table
  from hail.typecheck import typecheck, nullable, func_spec, oneof
  from hail.utils import Interval, Struct, new_temp_file, deduplicate
  from hail.utils.misc import plural
  from hail.utils.java import Env, info
  from hail import ir
label_desc: Use image node_id 1 for calling a global function with example usage: maximal_independent_set(i, j, keep, tie_breaker, keyed) and returns: nodes, nodes