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
}
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 } ` ) if ( pathCounts . length > MAX_TRANSITIVE_PATHS ) { log ( ` ${ pathCounts . length - MAX_TRANSITIVE_PATHS } ${ 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 ( ` ${ inPathCount } ${ pathCountAfterMultiTransfer } ${ allStopPatternStopSets . length } ` ) return allStopPatternStopSets }
Get the most common paths
Get the most common paths