lib/get-transitive-data.js
function getCommonPaths ({
  getRouteIndexFromPatternId,
  log,
  origin,
  paths
}: {
  getRouteIndexFromPatternId: (string | number) => number,
  log: Function,
  origin: Origin,
  paths: Array<PathDescriptor>
}): Array<StopPatternStops> {
  paths.sort(byStopIdAndPathIndex)
  const pathCounts = paths.reduce(countCommonPaths, [])
  pathCounts.sort(byCount)

  log(`${pathCounts.length} unique paths`)
  if (pathCounts.length > MAX_TRANSITIVE_PATHS) {
    log(`eliminated ${pathCounts.length - MAX_TRANSITIVE_PATHS} paths with frequency <= ${pathCounts[MAX_TRANSITIVE_PATHS].count} / ${paths.length} `)
  }

  let allStopPatternStopSets = pathCounts
    .slice(0, MAX_TRANSITIVE_PATHS)
    .map((p) => p.path)
    .filter(uniquePathIds) // uniquify the paths
    .map((p) => getStopPatternStopSets({log, pathDescriptor: p, origin}))

  const inPathCount = allStopPatternStopSets.length

  // Sort paths by the sequence of routes they use, and choose an example,
  // eliminating the multiple-board/transfer-stops problem
  allStopPatternStopSets.sort((p1, p2) => {
    if (p1.length < p2.length) return -1
    else if (p1.length > p2.length) return 1
    else {
      for (let i = 0; i < p1.length; i++) {
        const r1 = getRouteIndexFromPatternId(p1[i][1])
        const r2 = getRouteIndexFromPatternId(p2[i][1])
        if (r1 < r2) return -1
        if (r1 > r2) return 1
      }

      // identical patterns
      return 0
    }
  })

  allStopPatternStopSets = allStopPatternStopSets.filter((p, i, a) => {
    if (i === 0) return true
    const prev = a[i - 1]
    if (p.length !== prev.length) return true

    for (let s = 0; s < p.length; s++) {
      const r1 = getRouteIndexFromPatternId(p[s][1])
      const r2 = getRouteIndexFromPatternId(prev[s][1])
      if (r1 !== r2) {
        return true
      }
    }

    return false
  })

  const pathCountAfterMultiTransfer = allStopPatternStopSets.length

  // eliminate longer paths if there is a shorter path that is a subset
  // (eliminate the short access/egress/transfer leg problem)
  allStopPatternStopSets = allStopPatternStopSets.filter((path, i, rest) => {
    for (const otherPath of rest) {
      // longer paths cannot be subsets. Also don't evaluate the same path.
      if (otherPath.length >= path.length) continue

      let otherPathIsSubset = true
      const routes = path.map(seg => getRouteIndexFromPatternId(seg[1]))

      for (const seg of otherPath) {
        if (routes.indexOf(getRouteIndexFromPatternId(seg[1])) === -1) {
          otherPathIsSubset = false
          break
        }
      }

      if (otherPathIsSubset) {
        return false
      }
    }

    return true
  })

  log(`filtering reduced ${inPathCount} paths to ${pathCountAfterMultiTransfer} after multiple-stop elimination, to ${allStopPatternStopSets.length} after stemming`)

  return allStopPatternStopSets
}
function getCommonPaths ({
  getRouteIndexFromPatternId,
  log,
  origin,
  paths
}: {
  getRouteIndexFromPatternId: (string | number) => number,
  log: Function,
  origin: Origin,
  paths: Array<PathDescriptor>
}): Array<StopPatternStops> {
  paths.sort(byStopIdAndPathIndex)
  const pathCounts = paths.reduce(countCommonPaths, [])
  pathCounts.sort(byCount)

  log(`${pathCounts.length} unique paths`)
  if (pathCounts.length > MAX_TRANSITIVE_PATHS) {
    log(`eliminated ${pathCounts.length - MAX_TRANSITIVE_PATHS} paths with frequency <= ${pathCounts[MAX_TRANSITIVE_PATHS].count} / ${paths.length} `)
  }

  let allStopPatternStopSets = pathCounts
    .slice(0, MAX_TRANSITIVE_PATHS)
    .map((p) => p.path)
    .filter(uniquePathIds) // uniquify the paths
    .map((p) => getStopPatternStopSets({log, pathDescriptor: p, origin}))

  const inPathCount = allStopPatternStopSets.length

  // Sort paths by the sequence of routes they use, and choose an example,
  // eliminating the multiple-board/transfer-stops problem
  allStopPatternStopSets.sort((p1, p2) => {
    if (p1.length < p2.length) return -1
    else if (p1.length > p2.length) return 1
    else {
      for (let i = 0; i < p1.length; i++) {
        const r1 = getRouteIndexFromPatternId(p1[i][1])
        const r2 = getRouteIndexFromPatternId(p2[i][1])
        if (r1 < r2) return -1
        if (r1 > r2) return 1
      }

      // identical patterns
      return 0
    }
  })

  allStopPatternStopSets = allStopPatternStopSets.filter((p, i, a) => {
    if (i === 0) return true
    const prev = a[i - 1]
    if (p.length !== prev.length) return true

    for (let s = 0; s < p.length; s++) {
      const r1 = getRouteIndexFromPatternId(p[s][1])
      const r2 = getRouteIndexFromPatternId(prev[s][1])
      if (r1 !== r2) {
        return true
      }
    }

    return false
  })

  const pathCountAfterMultiTransfer = allStopPatternStopSets.length

  // eliminate longer paths if there is a shorter path that is a subset
  // (eliminate the short access/egress/transfer leg problem)
  allStopPatternStopSets = allStopPatternStopSets.filter((path, i, rest) => {
    for (const otherPath of rest) {
      // longer paths cannot be subsets. Also don't evaluate the same path.
      if (otherPath.length >= path.length) continue

      let otherPathIsSubset = true
      const routes = path.map(seg => getRouteIndexFromPatternId(seg[1]))

      for (const seg of otherPath) {
        if (routes.indexOf(getRouteIndexFromPatternId(seg[1])) === -1) {
          otherPathIsSubset = false
          break
        }
      }

      if (otherPathIsSubset) {
        return false
      }
    }

    return true
  })

  log(`filtering reduced ${inPathCount} paths to ${pathCountAfterMultiTransfer} after multiple-stop elimination, to ${allStopPatternStopSets.length} after stemming`)

  return allStopPatternStopSets
}
Get the most common paths