Je viens de m'apercevoir qu'un reseau ferré n'était pas vraiment un graphe, voir même pas du tout.

Prenons l'exemple simple d'un graphe connexe : Une graphe simple Comme on peut le voir, le noeud 3 est relié aux noeuds 1, 2 et 4. Si on suit la logique des graphes, les noeuds 1 et 2 sont reliés entre eux par le noeud 3, et un train, par exemple, pourrait passer par le noeud 3 pour aller du noeud 1 au noeud 2. Le probleme, c'est que ça ne marche pas à l'échelle d'une voie.

Prenons un exemple un peu plus proche de la réalité : Une graphe simple Dans cet exemple, les noeuds 1 et 2 sont effectivement reliés par le noeud 3, mais il serait impossible pour un train de passer sur l'autre voie du fait de l'orientation de l'aiguillage. En provenance de 1 ou de 2, les trains ne peuvent que aller vers 4 une fois passés 3.

Toutes ces explications pour montrer que les représentations classiques de graphes en mémoire ne fonctionnent pas pour des voies ferrées. En effet, si on reprend notre exemple, on peut poser les choses de la façon suivante :

{'links': {10: {'link': (1, 3)},
              11: {'link': (2, 3)},
              12: {'link': (3, 4)}},
 'node': {1: {'pos': (1, 1)},
          2: {'pos': (2, 1)},
          3: {'pos': (2, 2)},
          4: {'pos': (2, 3)}}}

Chaque noeud défini ses coordonnées, et chaque lien indique entre quel et quel noeud la liaison est faite. Le problème, c'est que de façon algorithmique, on ne sait absolument pas les chemins qui sont possibles de ceux qui ne le sont pas. Deux solutions à ce probleme :

  • on indique à chaque noeud les traversées qui sont possibles de celles qui ne le sont pas. Cela fait beaucoup de traitements pour indiquer les combinaisons possibles. D'autant plus que si on commence à faire un aiguillage triple connectés à un autre aiguillage tripe, cela fait 3 × 3 = 9 liaisons différentes. Le problème n'est pas un probleme de mémoire mais de traitement. Sans compter que les liaisons sont courrues d'avances (faciles à déterminer). Un autre probleme, plus génant, est que ce sont les noeuds qui portent cette informations, et qu'ils deviennent donc dépendants des liens. Cela entraine une boucle dans la structure de donnée, et ça c'est mal (en plus, en python, c'est potentiellement relou).
  • une autre solution, beaucoup plus élégante mais moins polyvalente, consiste à préciser à chaque bout de voie (dans le lien, donc) une étiquette précisant à quelle autre type de bout de voie il peut être connecté. Cette façon de faire est beaucoup plus complexe à comprendre, mais en terme d'implémentation, ça marche tout seul et c'est efficace.

Donc, pour chaque bout de pièce de rail, on associe une valeur parmis un ensemble de deux valeurs. J'ai pris l'ensemble booléen constitué de deux éléments (vrai et faux). Je ne sais pas si c'est tres pertinent vu que j'enlève complètement la sémantique de valeur de vérité dans ce cadre précis. Les bouts de pièces doivent être racordés de façon à ce qu'un bout de pièce "vrai" soit connecté à un bout de pièce "faux". Cela marche dans tous les cas puisque ces deux morceaux sont forcément en opposition (l'un en face de l'autre). Par contre, certaines pièces, comme des pièces en forme de U auront deux bouts avec la même valeur. Ce n'est pas génant du moment puisque les pièces qui y seront racordées seront à la valeur opposée.

De façon arbitraire, j'ai décidé que les valeurs "vrai" et "faux" seraient répartis de la façon suivante. C'est juste une convention qui marche à tous les coups, mais si à un moment elle n'est pas respectée, le système fonctionnera du moment que les "vrais" bouts sont connectés aux "faux" bouts. Un indicateur des valeurs de vérité à attribuer suivant le sens prit par la voie J'aurais pu intercaler "vrai" et "faux". La seule contrainte est que l'opposé d'une branche corresponde à l'opposé d'une valeur.

Cela fonctionne en deux dimensions. Si un jour quelqu'un s'amuse à faire une représentation en 3D, ça marchera aussi. Je part du principe qu'il n'y aura pas d'aiguillage à la verticale (Disgression en passant, le système de gestion accepte n'importe quel type de coordonées (qui sont considérés comme des étiquettes). Libre à vous de mettre en coordonnée "Chez ma grand mère").

Pour notre exemple, cela donnerais :

{'links': {10: {'link': (1, 3), 'side': (False, True)},
              11: {'link': (2, 3), 'side': (False, True)},
              12: {'link': (3, 4), 'side': (False, True)}},
 'node': {1: {'pos': (1, 1)},
          2: {'pos': (2, 1)},
          3: {'pos': (2, 2)},
          4: {'pos': (2, 3)}}}

Notez que la déduction que les noeuds 1 et 2 ne sont pas accessibles l'un à l'autre peut maintenant se faire puisque la valeur de vérité de chacun des bout est "vrai". Par contre, la troisième liaison est possible puisque la valeur est "faux". En image, cela donne : Le même graphe avec les indications de passage possible représentées par des valeurs de vérité

Pour ceux qui n'ont rien à faire, voici la structure de test sur laquelle je travaille. Elle est un peu différente, mais le principe est le même. Envoyez moi vos images :-)

{'junctions': {(1, 4): {'id': 80},
              (4, 1): {'id': 10},
              (4, 7): {'id': 70},
              (5, 1): {'id': 20},
              (5, 7): {'id': 60},
              (6, 1): {'id': 30},
              (6, 7): {'id': 50},
              (9, 4): {'id': 40},
              (9, 5): {'id': 90}},
'links': {5: {'link': ((1, 4), (4, 1)), 'side': (True, True)},
          15: {'link': ((4, 1), (5, 1)), 'side': (False, True)},
          25: {'link': ((5, 1), (6, 1)), 'side': (False, True)},
          35: {'link': ((6, 1), (9, 4)), 'side': (False, True)},
          45: {'link': ((9, 4), (6, 7)), 'side': (False, False)},
          55: {'link': ((6, 7), (5, 7)), 'side': (True, False)},
          65: {'link': ((5, 7), (4, 7)), 'side': (True, False)},
          75: {'link': ((4, 7), (1, 4)), 'side': (True, False)},
          85: {'link': ((9, 4), (9, 5)), 'side': (False, True)}}}