Crate transit_grid

TransitGrid

TransitGrid is a Rust library for simulating and analyzing transportation networks. It’s designed to be flexible and general-purpose, capable of simulating trains on tracks, planes in the air, or ships at sea, and more.

Project Status

TransitGrid is currently in the ideation phase. We’re still designing the architecture of the library and determining its exact features. Please feel free to submit suggestions or feedback by opening an issue on our GitHub repository.

Design Goals

TransitGrid is built around two core data structures: the PhysicalGraph and the TopologyGraph.

• PhysicalGraph: This is an undirected graph where each node represents a transit node (a point in the transit network where a vehicle can stop) and each edge represents a transit edge (a path between two transit nodes). The PhysicalGraph uses the UnGraph structure from the petgraph crate to internally represent this data. The PhysicalGraph maintains mappings between NodeId’s and NodeIndexes (from petgraph), allowing for efficient conversion between the two.

• TopologyGraph: Represents the topological graph of a transit network as a skew-symmetric graph. In this model, let G = (V, E) be the directed graph with a function σ mapping vertices of G to other vertices, satisfying the following properties:

  1. For every vertex v, σ(v) ≠ v.
  2. For every vertex v, σ(σ(v)) = v.
  3. For every edge (u, v), (σ(v), σ(u)) must also be an edge.

  In the context of the TopologyGraph, for each node v in V, there are two nodes in V_t, denoted as v_entry and v_exit. For each edge (u, v) in E, there are two directed edges in E_t: one from u_exit to v_entry and one from v_exit to u_entry. The mathematical representation of this is:

  • V_t = {v_entry, v_exit | v ∈ V}
  • E_t = {(u_exit, v_entry), (v_exit, u_entry) | (u, v) ∈ E}

  This skew-symmetric model is based on the definition by Goldberg & Karzanov (1996). It is particularly useful for scenarios such as rail switches where the directionality of edges matters. The TopologyGraph uses the StableDiGraph structure from the petgraph crate for internal representation and maintains mappings between custom NodeId’s/EdgeId’s and petgraph’s NodeIndexes/EdgeIndexes.

Future Work

TransitGrid will include several major components:

• Graph Operations: Functions to add and remove nodes and edges from the graphs.

• Graph Algorithms: Algorithms for finding the shortest path between two nodes, taking into account the current state of the Topology Graph.

We’re excited about the possibilities that TransitGrid can offer, and we’re looking forward to seeing what the community can build with it.

License

TransitGrid is licensed under the MIT License.

Modules

• algorithms
  TransitNet is a Rust library for representing, manipulating, and performing computations on transit networks. It provides a set of core data structures and algorithms that are commonly used in transit network analysis.
• core
  This module provides basic structures for representing a transit network. It provides TransitNode and TransitEdge structures, along with ID types for them. The TransitNode represents a node in the transit network, while the TransitEdge represents a connection between two nodes. The module also provides Accessability, an enum for representing the accessibility of nodes in the network.
• graphs
  This module contains the definition and implementation of various types of graphs used to represent and manipulate transit networks.
• operations
  This module provides abstractions and implementations for modifying a transit network. A transit network is represented as a graph, where each node is a TransitNode (a point in the transit network where a vehicle can stop) and each edge represents a path (TransitEdge) between two transit nodes. The main trait provided by this module is TransitNetworkModifier.
• prelude
  The prelude module re-exports the most commonly used items from the core, graphs, and operations modules,