<commit_before>/**
 * This module defines operations on graphs.
 *
 * @module
 */

import {copy, curry} from 'fkit'
import Immutable from 'immutable'

function keySet (graph) {
  return graph.vertexMap.keySeq().toSet()
}

function addEdge (adjacencyMap, [k, j]) {
  const kSet = adjacencyMap.get(k) || Immutable.Set()
  const jSet = adjacencyMap.get(j) || Immutable.Set()
  return adjacencyMap.set(k, kSet.add(j)).set(j, jSet.add(k))
}

function removeEdge (adjacencyMap, [k, j]) {
  const kSet = adjacencyMap.get(k) || Immutable.Set()
  const jSet = adjacencyMap.get(j) || Immutable.Set()
  return adjacencyMap.set(k, kSet.delete(j)).set(j, jSet.delete(k))
}

function removeVertex ([vertexMap, adjacencyMap], k) {
  const verticesMap_ = vertexMap.remove(k)

  const kSet = adjacencyMap.get(k)

  if (kSet) {
    const adjacencyMap_ = kSet.reduce((map, j) => {
      const jSet = adjacencyMap.get(j)
      return map.set(j, jSet.remove(k))
    }, adjacencyMap).remove(k)

    return [verticesMap_, adjacencyMap_]
  } else {
    return [verticesMap_, adjacencyMap]
  }
}

function traverse (graph, k) {
  const traverse_ = curry(([visited, vertices], k) => {
    const adjacentVertices = graph.adjacentVertices(k)

    // Add the vertex to the set of visited vertices.
    visited = visited.add(k)

    // Add the adjacent vertices to the result.
    vertices = adjacentVertices.reduce((a, b) => a.add(b), vertices)

    // Recurse with the adjacent vertices that have not been visited.
    return adjacentVertices
      .filter(j => !visited.contains(j))
      .reduce(traverse_, [visited, vertices])
  })

  const [_, keys] = traverse_(
    [Immutable.Set(), Immutable.OrderedSet.of(k)],
    k
  )

  return keys
}

function shortestPathBy (graph, p, key) {
  const [path, _, k] = shortestPathBy_([
    Immutable.OrderedMap([[key, null]]),
    Immutable.List.of(key),
    null
  ])

  return reconstructPath(k, path)

  function shortestPathBy_ ([path, frontier, k]) {
    if (frontier.size === 0) {
      return [path, frontier, k]
    }

    const next = frontier.first()

    if (p(graph.get(next), next)) {
      return [path, frontier, next]
    }

    const adjacentVertices = graph.adjacentVertices(next)

    adjacentVertices.forEach(vertex => {
      if (!path.has(vertex)) {
        frontier = frontier.push(vertex)<commit_msg>Fix linting<commit_after>/**
 * This module defines operations on graphs.
 *
 * @module
 */

import {copy, curry} from 'fkit'
import Immutable from 'immutable'

function keySet (graph) {
  return graph.vertexMap.keySeq().toSet()
}

function addEdge (adjacencyMap, [k, j]) {
  const kSet = adjacencyMap.get(k) || Immutable.Set()
  const jSet = adjacencyMap.get(j) || Immutable.Set()
  return adjacencyMap.set(k, kSet.add(j)).set(j, jSet.add(k))
}

function removeEdge (adjacencyMap, [k, j]) {
  const kSet = adjacencyMap.get(k) || Immutable.Set()
  const jSet = adjacencyMap.get(j) || Immutable.Set()
  return adjacencyMap.set(k, kSet.delete(j)).set(j, jSet.delete(k))
}

function removeVertex ([vertexMap, adjacencyMap], k) {
  const verticesMap_ = vertexMap.remove(k)

  const kSet = adjacencyMap.get(k)

  if (kSet) {
    const adjacencyMap_ = kSet.reduce((map, j) => {
      const jSet = adjacencyMap.get(j)
      return map.set(j, jSet.remove(k))
    }, adjacencyMap).remove(k)

    return [verticesMap_, adjacencyMap_]
  } else {
    return [verticesMap_, adjacencyMap]
  }
}

function traverse (graph, k) {
  const traverse_ = curry(([visited, vertices], k) => {
    const adjacentVertices = graph.adjacentVertices(k)

    // Add the vertex to the set of visited vertices.
    visited = visited.add(k)

    // Add the adjacent vertices to the result.
    vertices = adjacentVertices.reduce((a, b) => a.add(b), vertices)

    // Recurse with the adjacent vertices that have not been visited.
    return adjacentVertices
      .filter(j => !visited.contains(j))
      .reduce(traverse_, [visited, vertices])
  })

  const [, keys] = traverse_(
    [Immutable.Set(), Immutable.OrderedSet.of(k)],
    k
  )

  return keys
}

function shortestPathBy (graph, p, key) {
  const [path,, k] = shortestPathBy_([
    Immutable.OrderedMap([[key, null]]),
    Immutable.List.of(key),
    null
  ])

  return reconstructPath(k, path)

  function shortestPathBy_ ([path, frontier, k]) {
    if (frontier.size === 0) {
      return [path, frontier, k]
    }

    const next = frontier.first()

    if (p(graph.get(next), next)) {
      return [path, frontier, next]
    }

    const adjacentVertices = graph.adjacentVertices(next)

    adjacentVertices.forEach(vertex => {
      if (!path.has(vertex)) {
        frontier = frontier.push(vertex)
{'fraction_non_alphanumeric': 0.14294885512518724, 'fraction_numerical': 0.00042799058420714745, 'mean_word_length': 3.464183381088825, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 13, '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': '5779180', 'n_tokens_mistral': 1671, 'n_tokens_neox': 1581, 'n_words': 386}