csa

Documentation

Overview

Package csa is an implementation of the Connection-Scan-Algorithm.

This logic stands alone and can be tested independently of database functionality as it uses direct / native Go-types.

This package is used by apirtroute for routing calculations.

Index

• func CheapestArrivalDestination(mapStopToArrivalDetails map[string]ArrivalDetails, ...) (string, error)
• func ConnOIDs(conns []*dbt.Connection) []int
• func ExecuteCSA(conns *[]dbt.Connection, transfers *[]dbt.Transfer, ...) ([]*dbt.Connection, error)
• func ExecuteCSAFinalization(mapStopToArrivalDetails map[string]ArrivalDetails, ...) ([]*dbt.Connection, error)
• func ExecuteCSAMainLoop(conns *[]dbt.Connection, transfers *[]dbt.Transfer, ...) map[string]ArrivalDetails
• func InitializeMapStopToArrivalDetails(initialStopToArrivalTimeMap map[string]int) map[string]ArrivalDetails
• func TransferPossibleBetweenConnections(transfersMap map[string]map[string]uint, ...) bool
• type ArrivalDetails

Functions

func CheapestArrivalDestination

func CheapestArrivalDestination(
	mapStopToArrivalDetails map[string]ArrivalDetails,
	stopWalkcosts map[string]uint,
	maxWalkSeconds uint,
) (string, error)

func ConnOIDs

func ConnOIDs(conns []*dbt.Connection) []int

func ExecuteCSA

func ExecuteCSA(
	conns *[]dbt.Connection,
	transfers *[]dbt.Transfer,
	stopWalkcostsOrigin map[string]uint,
	stopWalkcostsDest map[string]uint,
	originTimeSeconds int,
	maxTransferSeconds, maxWalkSeconds, maxNTransfers uint,
) ([]*dbt.Connection, error)

ExecuteCSA runs the connection-scan-algorithm given the input connections, transfers, origin walkcosts, dest walkcosts, origin time, and transfer cost min.

The concept of a 'walkcost' is a generalized way to abstract time in seconds it takes to get from the stop to another point (e.g. used for both input and output points). The purpose of this is that the CSA algorithm itself doesn't need to know or do any comparisons around lat/lon haversine dist etc. and rather it's just an abstract concept of given each stop how long does it take to get from that stop to some target point in seconds. We don't "know" the best stop-to-stop route to take (which CSA output return requires), but walkcosts cover this.

The route taken / returned is the cheapest route based on the timetable (connections). The entrypoint itself is unknown until the main algorithm loop completes. Each stop is initialized based on walkcosts, e.g. as originTime + walkcost. See CSA paper for details on implementation, which this fn is an implemntation of besides entry/exit point walkcost logic.

Upon completing scanning the timetable, the time reached for each destination is examined and added witht the destination walkcost. The destination stop that is the cheapest to get to is taken and the path is built by iterating back up from FromStopUID's until the root at which point that origin stop is assumed to be the best.

The resulting returned route is an array of connections (limited from the input conns) which can be followed sequentially as a number of trips and transfers.

func ExecuteCSAFinalization

func ExecuteCSAFinalization(
	mapStopToArrivalDetails map[string]ArrivalDetails,
	stopWalkcostsDest map[string]uint,
	maxWalkSeconds uint,
) ([]*dbt.Connection, error)

func ExecuteCSAMainLoop

func ExecuteCSAMainLoop(
	conns *[]dbt.Connection,
	transfers *[]dbt.Transfer,
	stopWalkcostsOrigin map[string]uint,
	originTimeSeconds int,
	maxTransferSeconds, maxNTransfers uint,
) map[string]ArrivalDetails

ExecuteCSAMainLoop is the main logic loop for the CSA algorithm returns a map containing STOPUID-to-connectionptr AND another map for STOPUID-to-arrivaltime

func InitializeMapStopToArrivalDetails

func InitializeMapStopToArrivalDetails(initialStopToArrivalTimeMap map[string]int) map[string]ArrivalDetails

func TransferPossibleBetweenConnections

func TransferPossibleBetweenConnections(
	transfersMap map[string]map[string]uint,
	fromConnection, toConnection *dbt.Connection,
	maxTransferSeconds uint,
) bool

TransferPossibleBetweenConnections determines whether a transfer is possible given two connections, the transfers map, and implicit/max transfer secs.

Types

type ArrivalDetails

type ArrivalDetails struct {
	Time       int
	Connection *dbt.Connection
	NTrips     uint
}