<commit_before>(declare (usual-integrations))

;;; A feedback vertex set of a directed graph G is a subset of the
;;; vertices of G whose removal causes G to become acyclic.  It is
;;; usually desirable for such feedback sets to be smaller rather than
;;; larger; however, the problem of finding a minimum feedback vertex
;;; set for a directed graph is known to be NP-complete.  In the
;;; present application, minimality is not strictly necessary, whereas
;;; finding a plausible acceptable solution quickly is also important.
;;; To that end, this code heuristically spits out some feedback
;;; vertex set of the given graph.

;;; The incoming graph is accepted as an alist of vertex with
;;; out-neighbors.  It is assumed normalized so that sameness of
;;; vertices can be tested with eq?.

(define (feedback-vertex-set graph)
  ;; The internal graph representation is a linked record pile, with
  ;; one record per vertex maintaining bidirectional adjacency and
  ;; degrees.
  (define-structure (node safe-accessors (conc-name #f))
    name
    out-neighbors
    out-degree
    in-neighbors
    in-degree)
  (define (add-out-neighbor! node1 node2)
    (set-out-neighbors! node1 (cons node2 (out-neighbors node1)))<commit_msg>Comment about approximation algorithms.<commit_after>(declare (usual-integrations))

;;; A feedback vertex set of a directed graph G is a subset of the
;;; vertices of G whose removal causes G to become acyclic.  It is
;;; usually desirable for such feedback sets to be smaller rather than
;;; larger; however, the problem of finding a minimum feedback vertex
;;; set for a directed graph is known to be NP-complete.  Furthermore,
;;; no good approximation algorithms are known.  In the present
;;; application, minimality is not strictly necessary, whereas finding
;;; a plausible acceptable solution quickly is important.  To that
;;; end, this code heuristically spits out some feedback vertex set of
;;; the given graph.

;;; The incoming graph is accepted as an alist of vertex with
;;; out-neighbors.  It is assumed normalized so that sameness of
;;; vertices can be tested with eq?.

(define (feedback-vertex-set graph)
  ;; The internal graph representation is a linked record pile, with
  ;; one record per vertex maintaining bidirectional adjacency and
  ;; degrees.
  (define-structure (node safe-accessors (conc-name #f))
    name
    out-neighbors
    out-degree
    in-neighbors
    in-degree)
  (define (add-out-neighbor! node1 node2)
    (set-out-neighbors! node1 (cons node2 (out-neighbors node1)))
{'fraction_non_alphanumeric': 0.0816967792615868, 'fraction_numerical': 0.003927729772191673, 'mean_word_length': 4.1454545454545455, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, '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': '3806060', 'n_tokens_mistral': 717, 'n_tokens_neox': 682, 'n_words': 332}