[META] Trainruns reordering (automated and manual)

[louisgreiner]

Description: META issue

Currently, the trainruns that share a part of their paths are ordered (top to bottom or left to right) using some characteristics:

• trainrun name (alphebetical - ascending)
• trainrun category (alphebetical - ascending)
• trainrun departure time (ascending)
• ...

Which is a good heuristic, but it often results on trainruns crossing other trainruns, especially inside a node ("port to port"), here an example:

The solution would be:

• automated algorithms:
  • reordering: enhance the existing ordering algorithm on a heuristic that tries to reduce the number of trainrun crossing trainrun on the reticular
  • transition distance reduction: move ports to other available ports to avoid trainruns "crossing" the nodes
• manually reordering: allow user to manually set the input and output ports of a trainrun inside a node

The first step will be to update the data model and change a bit the already existing algorithm. The two automated tasks (reordering and transition distance reduction) may be independent, as for the manual one.

All of these tasks will be done in a common feature branch.

Sub-issues

• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/634
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/635
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/637
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/636

[aiAdrian]

Thanks for this feature request! I would recommend making the new port ordering heuristic configurable—either via project settings or the user's local profile. By default, it should be disabled to preserve the existing behavior. If stored in project settings, a data migration will be necessary to ensure compatibility.

[shenriotpro]

I'd like to see examples of what users dislike

re I: I'd like to fix these

terminal reordering

double swap (may also need II)

[shenriotpro]

Some relevant papers from @Math-R

https://arxiv.org/pdf/1306.2079

In practice, it is desirable to avoid gaps between adjacent lines; to this end, every line is drawn so that it starts and terminates at the topmost or bottommost end of a port; see Fig. 2(b). In fact, many manually created maps follow this periphery condition introduced by Bekos et al. [5]. Formally, we say that a line order πuv at the port of u satisfies the periphery condition if πuv = (l1 . . . lp . . . lq . . . l|Luv|), where u is a terminal for the lines l1, . . . , lp, lq, . . . , l|Luv| and u is an intermediate station for the lines lp+1, . . . , lq−1. The problem is known as MLCM with periphery condition.

Our Results. Table 1 summarizes our contributions and previous results. We first prove that the unconstrained variant MLCM is NP-hard even on caterpillars (paths with attached leaves), thus, answering an open question of Benkert et al. [6] and Nollen- ¨ burg [14].

https://arxiv.org/pdf/1209.4227

To find an ordering of paths we iterate over the edges of Ge in any order, and build the order for each edge. Let Puv be a set of paths passing through the edge uv. We fix a direction of the edge, and construct the ordering on it by sorting Puv. To define the order between two paths π1, π2 ∈ Puv we walk along their common edges starting from u until the paths end or the following cases happen ; If we find an edge which was previously processed by the algorithm, we reuse the order of π1 and π2 generated for this edge. If we find a fork node f, by which we mean the end of the common sub-path of the two paths, then the order between π1 and π2 is determined according to the positions of the next nodes of the paths following f, the path turning to the left is smaller. Otherwise, if such a fork node is not found (which means that the paths end at the same node), we walk along the common sub-path in the reverse direction starting from node v, and again looking for a previously processed edge or a fork. The above procedure determines a consistent order for all pairs except of the pairs of coincident paths; such paths are ordered arbitrarily on the edge.

[aiAdrian]

The Current Version appears quite compact, whereas the PoC Version ? looks somewhat messy. It's a trade-off between minimizing the free space between nodes and reducing the number of transition line crossings.

PoC version ? Terminal reordering can be a very precise method for reducing the number of crossings — however, the current sorting logic assumes that train names are ordered alphabetically. This will no longer be the case, as introducing terminal reordering gives higher priority to the travel path than to train names. That could be quite an interesting approach, but again, it's a trade-off between readability within the node's internal layout (transitions) and a more global perspective.

Experiment 1	Experiment 2

Terminal reordering can solve some problems by allowing bidirectional reordering. However, care must be taken to ensure readability is not compromised by overly complex reordering. Timetable planners often think in terms of train groups or categories, which ideally should be kept together. Filtering must also be taken into account in the sorting concept.

In Experiments 1 and 2, an attempt was made to distinguish between sorting and the number of crossings within the nodes. In Olten, there is currently a significant visual issue, which I believe should take priority over reordering. The question is simply how to remedy this deficiency.

I see a simple approach – shifting the rows by half – but that could again be visually messy.

netzgrafik_experimental.json

[louisgreiner]

Very nice experiments! Thanks!

You're totally right, a reordering considering the number of transitions crossing is not ideal as well, in both cases we have contexts on which that fit and other that don't... And you are also very right on the fact that planners usually work with groups of trains, sometimes in groups that make sense (same category), sometimes not (or less predictable)

In any case, I think the "ideal" solution would be to allow the user to set the trains that are not well positioned through the first ordering. So the key is to find the heuristic that results in fewer trains that the planners will need to reorder manually.

(also, proposing different algorithms / heuristics could directly benefit to the planners, depending on their context or habits)

How did you re-order the trains in your experiments? Could we find the code somewhere?

We'll keep thinking on another heuristic in the next few weeks, and on an UI to manually re-order the trains (ports), it would be interesting to think on that together 👍

[louisgreiner]

2025-10-20 UX point of view on manual re-ordering

Participants: @thibautsailly @louisgreiner

[!NOTE] Below notes have been integrated in the core of the issue, Section III. Manual ports reordering

UX/UI

(better mock-ups to come):

The manual re-ordering feature should be accessible when a node is currently edited (= double-clicked (node details are opened on the right side)):

• when at this state, all the ports of the node are displayed, so the ones that are:
  • already occupied
  • not occupied (all the possible ports that the size of the node allows)
  • +1 new not occupied port on each side (= the node will then grow in size when edited)
• this state makes the ports look different and introduce a new component: a handle
  • edited port:
    • three states:
      • empty (white background): port is not already occupied
      • occupied (grey background): port is already occupied
      • receiving (light grey / other color background): port is not already occupied, but the user is currently dragging a train on this port -> "preview state"
  • handle: next to each already occupied port of the node, outside of the node; this can be grabbed by the user to drag the train to another port (already occupied or not)
    • three states:
      • rest (grey background)
      • hover (highlighted)
      • activated (more highlighted, with a shade?): used clicks and drags the handle; the handle snaps to the nearest port (making this port "receiving")

Few thoughts on Implementation Plan

• display all ports (occupied or not) and additional empty one for each side of the node when node is edited
• being able to store a "forced-by-user" port
  • should the data model be updated?
• adapt the port allocation algorithm to take into account the "forced-by-user" ports
• trainrunSection.view:
  • path: nothing to do (normally) (keep only 4 points for path drawing)
  • (create and replace port with edited port new component)
  • create new handle component
  • allow to drag the handle and make it snap to nearest port

Scope reduction proposition:

• edited port UI? The handle seems necessary, but the edited port "curvy" shape might not (for a first version)

Later:

• allow more than 4 points for the trainrunSection's path to prevent bad drawings

Next steps

• Precise the Acceptance Criteria
• Write the Implementation Plan

[louisgreiner]

Workflow + technical considerations (III. Manual ports reordering)

Participants: @SharglutDev @akctarus @Math-R @jacomyal @SarahBellaha @louisgreiner

[!NOTE] Below notes have been integrated in the core of the issue, Section III. Manual ports reordering

wip

• resize à la mano le noeud : plus de choses à faire / feature différente / assez proche de ce que fait Viriato
  • modèle de données accepte pas ça pour l'instant
• drag en dehors du noeud agrandit le noeud automatiquement (= pas de nouveau port sur chaque côté par défaut)
• "+1" port vide entre deux déjà existants
  • dans quel sens décaler les autres ports
  • problème : que faire des ports "locked"
• swap : change de position avec un port en particulier, le swappant prend la valeur locked et le swappé non
• insert :
  • dans quel sens décaler les autres ports
  • problème : que faire des ports "locked"
• comment différencier un port locked d'un port pas locked
  • à l'aide d'un cadenas au niveau des ports locked
  • ou autre bordure / couleur port / etc / thibaut on compte sur toi
• rajouter la possibilité de unlock un port (= reset)
  • au niveau du noeud pour tous les ports -> pas ouf
  • ou au niveau d'un port -> cliquer sur
• déplacer un port en dehors du noeud édité :
  • cancel l'action
  • prévoir une zone de snapping en bordure du noeud pour pas cancel trop prématurément
• feature flèche (clavier, haut/bas ou gauche/droite uniquement (pas possible diago)) :
  • un peu doublon de la feature drag au sein du noeud qui agrandit le noeud
  • doit ajouter une sélection de port au sein de l'édition du noeud
• ports "locked": à voir avec l'algo automatique

modèle de données

  "trainrunSections": [
    {
      "id": 509,
      "sourceNodeId": 156,
      "sourcePort": {
        "portId": 1033,
        "locked": true
      },

ou

  "nodes": [
    {
      "id": 128,
      "betriebspunktName": "Lausanne",
      "fullName": "Lausanne",
      "positionX": -3072,
      "positionY": 544,
      "ports": [
        {
          "id": 1207,
          "trainrunSectionId": 596,
          "positionIndex": 0,
          "positionAlignment": 2,
          "locked": true
        },

[louisgreiner]

I split the different issues and keep this one as a meta for tracking all of them:

• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/634
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/635
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/637
• https://github.com/OpenRailAssociation/netzgrafik-editor-frontend/issues/636

[aiAdrian]

@louisgreiner Excellent idea to split the task (meta) into differnt topics. I guess this will be a very "hard" work to get everthing running.