Automatically re-order trainruns in nodes (crossings reduction)

[louisgreiner]

Description

Type	Size (weeks)
Spike	4

#634 will affect this issue.

Meta issue: #551

Trainrun lines are often crossing themselves, due to the already existing ordering algorithm.

The idea is propose another algorithm (the already existing one should be kept, user chooses which ordering algorithm to use) to reduce the crossings.

We could start with a simple heuristic (reduce the number of trainrun crossing trainrun inside the nodes / on the whole reticular) and iterate to improve it. The first draft of the implementation could be done as a PoC.

The idea is to iterate and improve the model empirically, by asking user's preferences at each iteration.

Important

The algorithm has to take into account that some ports can be locked (see III. Manual ports reordering).

Optimal solution (might never be implemented, not worth the complexity) would be this. We could take inspiration of it but full implementation may not be necessary.

Mock-ups

Acceptance Criteria

• User can choose which ordering algorithm to use between already existing one (alphabetical) and the new one (crossings reduction)
• The network graphic ordering algorithm configuration is saved (NetzgrafikDto.MetadataDto.OrderingAlgorithm: OrderingAlgorithm (enum))
• The trainruns are now sorted using the global context of the reticular, tending to have the less crossings between trainruns
• The algorithm should run in a reasonable time (not noticeable by the user), reasonable enough to keep call the network graphic reordering at each re-render (= after any action)

Pool of network graphics

Medium network graphic with different cases (medium_network.json)

IC1 and IC5 are crossing at Morges, whereas they could just be swapped at the beginning (morges.json):

IC2 and IC21 could stick to the right side (and IR26 and IR46 to the left), removing the crossings in Biasca and Bellinz. (biasca.json):

"Turning" trainruns happen to cross a lot (here with same path), depending on the nodes positions (left/bottom; bottom/right; ...): top left and bottom right cases are good, others not (turning.json):

IR70 and IR75 could stick on left, IC2 and IC46 on the middle and the trainruns that go to the right stick to the right:

Implementation Plan

Port model:

export interface PortDto {
	id: number; // unique identifier
	positionIndex: number; // position index starts at 0, ... for each PortAlignment group
	positionAlignment: PortAlignment; // defines corresponding PortAlignment group within the node
	trainrunSectionId: number; // reference to the connected trainrun section
	locked: boolean; // !! NEW FIELD !! default value is false
}

Considerations "How to detect a crossing?":

• Calculate crossings outside the nodes: TrainrunSection.path[0] and TrainrunSection.path[3] (mathematics involved, crossing of two segments (this can give some ideas))
• Calculate crossings inside the nodes: Port.positionIndex and Port.positionAlignment are key; the latter needs to be re-handled to consider trigonometric order
  • (Not sure it is really useful, considering the next bullet point) Re-order PortAlignment values for trigonometric order:
    • Note: this should not infer with old NetzgrafikDto files that have different references, since reordering is called at loadNetzgrafikDto

export enum PortAlignment {
  Right,
  Top,
  Left,
  Bottom,
}

• Do collapsed nodes need particular attention? It seems not.
• Do non-continuous trainruns need particular attention? It seems not.

Ideas:

• Can we pre-process the trainruns that have the SAME path (node's path)? To reduce the number of sections to order.
• Can we deal with Top<->Bottom and Left<->Right only pairs of sections in pre-processing?

Implementation:

• Add the input buttons for selecting the ordering algorithm (already existing algorithm is available here)
• Save the network graphic ordering algorithm configuration in the NetzgrafikDto.MetadataDto.OrderingAlgorithm: OrderingAlgorithm (enum)
• Create a pool of network graphic candidates (see above section but also real business cases: network graphic from SNCF Réseau)
  • At each iteration of enhancement of this algorithm, ask users' (and POs) preferences, and refine the algorithm taking the preferences into account
• New algorithm objective function is (if needed, Choco-solver is an open-source solver, can it be ported to TypeScript? if possible we should do this by ourselves (don't import another external lib)):
  • a) crossings inside the nodes
  • b) or crossing outside the nodes
  • c) or both (sum, or different weights) (this must be explored empirically)
  • d) or another track would be a:
    • simple rule, i.e.: "n maximum crossings inside a node"
    • relaxed rule, i.e.: "n maximum crossings inside a node" but +/- (margin)
  • => the different ordering methods (a), b), c), d)) can be chosen (by the user? or only using a configuration and do not make it available to the user?)
• Keep locked ports into account

Definition of Ready

• PO/UX-UI

  • Mock-ups are complete and validated
  • ACs are clear and have been reviewed by another refiner

• Technical

  • Implementation plan has been written and validated by another maintainer

• General

  • Validated by Adrian