Graphe trajets SNCF

algo_plus_court.md

Algorithme du plus court chemin

On souhaite aller de Lyon à Toulouse On commence par écrire une table de toutes les destinations possibles (on va utiliser Reachable)

Lyon            # 0 (depuis Lyon)  
Paris           # 107 (depuis Lyon)  
Rennes          # 107 + 114 = 221 (depuis Paris)
Londres         # 280 + 61  = 341 (depuis Calais)
                # 107 + 146 = 253 (depuis Paris)
Calais          # 107 + 173 = 280 (depuis Paris)
Bordeaux        # 107 + 155 = 262 (depuis Paris)
Toulouse        # 182 + 247 = 429 (depuis Montpellier)
                : 262 + 131 = 393 (depuis Bordeaux)
Montpellier     # 182 (depuis Lyon)
Marseille       # 125 (depuis Lyon)

On commence par Lyon, on récupère tous ses voisins (neighboursOf)

• Lyon ; ok
• Paris ; 107
• Montpellier ; 182
• Marseille ; 125 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Paris On récupère tous ses voisins :
  • Calais ; 173
  • Londres ; 146
  • Rennes ; 114
  • Bordeau ; 155
  • Lyon ; 107 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Marseille On récupère tous ses voisins :
  • Lyon : 125 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Montpellier
  • Toulouse : 247
  • Lyon : 182 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Rennes
  • Paris : 114 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Bordeaux
  • Paris : //
  • Toulouse : 131 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Calais
  • Londres : 61
  • Paris : 173 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Londres
• Paris : 146
• Calais : 61 On prend le plus petit de toutes les villes visitées :
• Il s'agit de Toulouse
• Toulouse est notre destination !
• La plus courte durée est donc 393' !

Toulouse <- Bordeaux en 393' Bordeaux <- Paris en 262' Paris <- Lyon en 107'

=> On a nos 3 trajets => On peut construire un itinéraire

Algorithme à implémenter :

 Algorithme à implémenter :
 - On fait une liste des villes atteignables
 - On note "non-visitées" toutes les villes
 - On note un score de 0 pour la ville de départ

 On prend, parmis toutes les villes non-visitées, celle qui a le score le plus petit : (au départ, c'est la ville de départ)
  Pour chacun de ses voisins, on calcule le coût de s'y rendre depuis la ville choisie 
   = score de la ville choisie + coût d'aller de choisie à voisin
   si ce coût est plus petit : on le garde et on note la ville de provenance
   si ce coût est plus grand : on ignore
  Si la ville qui a le score le plus petit est la ville d'arrivée : on s'arrête.
  On marque "visitée" la ville choisie
 On remonte les trajets, de l'arrivée, au départ.
 => On construit un Itinéraire.

exos.md

Exercice 0 : représenter les trajets et les durées
Exercice 1 : Écrire un algorithme prenant en entrée votre représentation et listant la liste des stations

function list_station(graph){
 => out : liste des stations
}

Exercice 2 : Écrire un algorithme prenant en entrée (le graphe et ) une ville de départ et listant tous ses voisins
Exercice 2.bis : listant les voisins par ordre de proximité

function list_voisins(graph, station_initiale){
  => out : liste des stations voisines de  station_initiale
}

Exercice 3 : Écrire un algorithme prenant en entrée (le graphe et ) une ville de départ et listant toutes les villes atteignables Exercice 3.bis : Écrire un algorithme prenant (le graphe et ) 2 villes et répondant si elles sont atteignables ou non.

Exercice 4.prepa : Helper : À partir d'une liste de trajet, renvoyer un objet Itineraire pouvant :

• lister des stations visitées (dans l'ordre),
• calculer la durée totale du trajet.

Exercice 4 : Trouver le chemin le plus court pour aller d'une ville de départ à une ville d'arrivée. En entrée : (le graphe et) 2 villes. En sortie, une liste de trajets..

graphe.js

const flat_graph = {
    "Londres" : {
        "Calais" : 61,
        "Paris" : 146
    },
    "Calais" : {
        "Paris" : 173,
        "Londres" : 61
    },
    "Paris" : {
        "Londres" : 146,
        "Calais" : 173,
        "Rennes" : 114,
        "Bordeaux" : 155,
        "Lyon" : 107
    },
    "Rennes" : { "Paris" : 114 },
    "Bordeaux" : {
        "Paris" : 155,
        "Toulouse" : 131
    },
    "Lyon" : {
        "Paris" : 107,
        "Montpellier" : 182,
        "Marseille" : 125
    },
    "Toulouse" : {
        "Bordeaux" : 131,
        "Montpellier" : 247
    },
    "Montpellier" : {
        "Toulouse" : 247,
        "Lyon" : 182
    },
    "Marseille" : { "Lyon" : 125 },
    "Berlin" : {"Zurich" : 536},
    "Zurich" : {"Berlin" : 536}
}


function Station(name){
  this.name = name;
}
Station.prototype.toString = function() {
  return "Station <"+this.name+">";
};

function Trajet(start, finish, time){
  this.start = start;
  this.finish = finish;
  this.time = time;
}


function Graph(hybrid_representation){

  this.stations = 
    Object.fromEntries(
        Object.entries(hybrid_representation)
              .map((entry) => {
                  [name, destinations] = entry;
                  return [name, new Station(name)];
                })
        )
  this.trajets = 
      Object.entries(hybrid_representation)
            .map((entry) => {
              [start_name, destinations] = entry;
              let start = this.getStation(start_name);
              return Object.entries(destinations)
                      .map(traj_entry => {
                        [finish_name, duration] = traj_entry;
                        let finish = this.getStation(finish_name);
                        return new Trajet(start, finish, duration)
                      })
            })
            .reduce( (total, current) => {
              return total.concat(current)
            }, [])
    
}

Graph.prototype.getStation = function(name) {
  return this.stations[name];
};

Graph.prototype.trajetsStartingAt = function(start) {
  let trajets_depuis_start = (
    this.trajets.filter(t => {
      return t.start == start;
    })
  )
  return trajets_depuis_start;
};
Graph.prototype.neigboursOf = function(start) {
  let trajets_depuis_start = this.trajetsStartingAt(start);
  return trajets_depuis_start.map(t => {
      return t.finish
  });
};
Graph.prototype.reachableStations = function(start, visited = []) {
  let isInitial = (visited.length == 0);

  if(!visited.find(c => c == start)){
    visited.push(start);
  }

  let trajets = this.trajetsStartingAt(start);

  trajets.forEach((t) => {
    if(!visited.find(c => c == t.finish)){
      visited = this.reachableStations(t.finish, visited)
    }
  })
  return visited;
};

Graph.prototype.canGoFromTo = function(start, finish){
  return !!this.reachableStations(start).find(s => s == finish);
}

Graphe.prototype.shortestPath = function(start, finish){
  
}

let tgv_france = new Graph(flat_graph)
//liste des stations
console.log("Liste des stations");
for(const [s, station] of Object.entries(tgv_france.stations)){
  console.log(station)
}

//Voisins de Calais
console.log("Voisins de Calais");
let calais = tgv_france.getStation("Calais");
for(station of tgv_france.neigboursOf(calais)){
  console.log(station);
}
//Voisins de Berlin
console.log("Voisins de Berlin");
let berlin = tgv_france.getStation("Berlin");
for(station of tgv_france.neigboursOf(berlin)){
  console.log(station);
}

console.log("Atteignable de Berlin");
for(station of tgv_france.reachableStations(berlin)){
  console.log(station);
}
console.log("Atteignable de Calais");
for(station of tgv_france.reachableStations(calais)){
  console.log(station);
}

let montpellier = tgv_france.getStation("Montpellier");
let lyon = tgv_france.getStation("Lyon");

console.log("Peut-on aller de Lyon à Montpellier");
console.log(tgv_france.canGoFromTo(lyon, montpellier));

console.log("Peut-on aller de Berlin à Montpellier");
console.log(tgv_france.canGoFromTo(berlin, montpellier));

graphe.php

<?php

// hybride liste
$graphe = [
    "Londres" => [
        "Calais" => 61,
        "Paris" => 146
    ],
    "Calais" => [
        "Paris" => 173,
        "Londres" => 61
    ],
    "Paris" => [
        "Londres" => 146,
        "Calais" => 173,
        "Rennes" => 114,
        "Bordeaux" => 155,
        "Lyon" => 107
    ],
    "Rennes" => [ "Paris" => 114 ],
    "Bordeaux" => [
        "Paris" => 155,
        "Toulouse" => 131
    ],
    "Lyon" => [
        "Paris" => 107,
        "Montpellier" => 182,
        "Marseille" => 125
    ],
    "Toulouse" => [
        "Bordeaux" => 131,
        "Montpellier" => 247
    ],
    "Montpellier" => [
        "Toulouse" => 247,
        "Lyon" => 182
    ],
    "Marseille" => [ "Lyon" => 125 ],
    "Berlin" => ["Zurich" => 536],
    "Zurich" => ["Berlin" => 536]
];

//représentation procédurale
class Station{
  public function __construct($name){
    $this->name = $name;
  }

  public function __toString(){
    return "Station <{$this->name}>";
  }
}

class Trajet{
  public function __construct(Station $start, Station $finish, $time){
    $this->start = $start;
    $this->finish = $finish;
    $this->time = $time;
  }
}

class Graph{
  private $stations;
  private $trajets;

  public function __construct($hybrid_representation){
      $this->stations = 
              array_combine(
                array_keys($hybrid_representation),
                array_map(
                    function($city_name){
                      return new Station($city_name);
                    },  
                    array_keys($hybrid_representation)
                )
              );

      $this->trajets = [];
      foreach($hybrid_representation 
                    as $start_name => $destinations){
        $start = $this->stations[$start_name];
        foreach($destinations as $finish_name => $time){
          $finish = $this->stations[$finish_name];
          $trajet = new Trajet($start, $finish, $time);
          $this->trajets[] = $trajet;
        }
      }
  }

  /**
   *  return Station
   **/
  public function getStation($name){
    //le graphe = $this
    return $this->stations[$name];
  }
    
  /**
   *  return Trajet
   **/
  public function getTrajet($start, $finish){
    //le graphe = $this
    $found = array_filter($this->trajets, function($t) use ($start, $finish){
      return $t->start == $start && $t->finish == $finish;
    });
    if(count($found) == 1){
      return current($found);
    }else{
      return null;
    }
  }

  /**
   *  return Station[]
   **/
  public function stations(){
    //le graphe = $this
    return $this->stations;
  }

  /**
   *  return Trajet[]
   **/
  public function trajetsStartingAt(Station $start){
    //on récupère tous les trajets dont Toulouse
    //est le point de départ
    $trajets_depuis_start = array_filter(
      $this->trajets, 
      function($t) use ($start){
        return $t->start == $start;
      });

    //on trie les trajets par temps
    usort($trajets_depuis_start, function($t1, $t2){
      return $t1->time > $t2->time;
    });

    return $trajets_depuis_start;
  }

  /**
   *  return Station[]
   **/
  public function neigboursOf(Station $start){
    //le graphe = $this
    $trajets_depuis_start = $this->trajetsStartingAt($start);
  
    //pour chaque trajet eligible
    //je renvois la ville de destination
    $neigbours = array_map(function($t){
      return $t->finish;
    }, $trajets_depuis_start);

    return $neigbours;
  }

  /**
   *  return Station[]
   **/
  public function reachableStations(Station $start, $visited = []){
      $isInitial = empty($visited);

      $visited[$start->name] = $start;
      $trajets = $this->trajetsStartingAt($start);

      foreach($trajets as $trajet){

        if(!in_array($trajet->finish, $visited)){
          $visited = $this->reachableStations($trajet->finish, $visited);
        }
      }

      if($isInitial){
        unset($visited[$start->name]);
      }

      return $visited;
  }

  /**
   *  return boolean
   **/
  public function canGoFromTo(Station $from, Station $to){
    return in_array($to, $this->reachableStations($from));
  }

  /**
   *  return Itineraire
   **/
  public function plusCourtChemin(Station $from, Station $to){
    return new Itineraire([]);
  }

}

class Itineraire{
  public function __construct(/*Trajet[]*/ $trajets){
    $this->trajets = $trajets;
    shuffle($this->trajets);
  }

  public function orderedTrajets() /* Trajet[] */{

    //on liste toutes les villes
    $departs = array_map(function($t){
      return $t->start;
    }, $this->trajets);
    $arrivals = array_map(function($t){
      return $t->finish;
    }, $this->trajets);

    $allcities = array_unique(array_merge($departs, $arrivals));

    // on trouve le départ et l'arrivée
    $true_start = array_diff($allcities, $arrivals);
    $true_arrival = array_diff($allcities, $departs);

    if(count($true_start) != 1){
      throw new Exception("Erreur sur les départs");
    }
    if(count($true_arrival) != 1){
      throw new Exception("Erreur sur les arrivées");
    }
    $true_start = current($true_start);
    $true_arrival = current($true_arrival);

    // on ordonne les stations dans le bon ordre
    $current_to = $true_start;
    $ordered_trajets = [];
    do{
      //tant qu'on est pas arrivé au bout
      foreach($this->trajets as $k => $trajet){
        // on cherche si un trajet part de là où on en est
        if($trajet->start == $current_to){
          // si c'est le cas, on ajoute ce trajet à la suite
          $ordered_trajets[] = $trajet;
          $current_to = $trajet->finish;
          break;
        }
      }
    }while($current_to != $true_arrival);
    

    return $ordered_trajets;

  }

  public function visitedStations() /* Station[] */{
    $ordered_trajets = $this->orderedTrajets();
    $stations = [];
    foreach($ordered_trajets as $trajet){
      if(empty($stations)){
        $stations[] = $trajet->start;
      }
      $stations[] = $trajet->finish;
    }
    return $stations;
  }


  public function duration() /* int */{
    $duration = 0;
    foreach($this->trajets as $trajet){
      $duration += $trajet->time;
    }
    return $duration;
  }
}

$paris = new Station("Paris");
$lyon = new Station("Lyon");
$montpellier = new Station("Montpellier");
$toulouse = new Station("Toulouse");
$rennes = new Station("Rennes");

$itineraire = new Itineraire([
    new Trajet($lyon, $montpellier, 182),
    new Trajet($montpellier, $toulouse, 247),
    new Trajet($paris, $lyon, 107),
  ]
);

$visited = $itineraire->visitedStations();
echo "Liste des stations de l'itinéraire\n";
foreach($visited as $station){
  echo "\t- ".$station."\n";
}
//Paris, Lyon, Marseille
echo $itineraire->duration();
//180

$tgv_france = new Graph($graphe);

echo "Liste des stations\n";
foreach($tgv_france->stations() as $station){
  echo "\t- ".$station."\n";
}

echo "Voisins de Calais :\n";
$initial = $tgv_france->getStation("Calais");
foreach($tgv_france->neigboursOf($initial) as $station){
  echo "\t- ".$station."\n";
}

echo "Voisins de Berlin :\n";
$initial = $tgv_france->getStation("Berlin");
foreach($tgv_france->neigboursOf($initial) as $station){
  echo "\t- ".$station."\n";
}

echo "Atteignable depuis Berlin :\n";
$initial = $tgv_france->getStation("Berlin");
foreach($tgv_france->reachableStations($initial) as $station){
  echo "\t- ".$station."\n";
}

echo "Atteignable depuis Londres :\n";
$initial = $tgv_france->getStation("Londres");
foreach($tgv_france->reachableStations($initial) as $station){
  echo "\t- ".$station."\n";
}
die();

echo "Peut-on aller de Lyon à Montpellier :\n";
$from = $tgv_france->getStation("Lyon");
$to = $tgv_france->getStation("Montpellier");
echo ($tgv_france->canGoFromTo($from, $to) ? "oui" : "non")."\n";//"yes"


echo "Peut-on aller de Berlin à Montpellier :\n";
$from = $tgv_france->getStation("Berlin");
$to = $tgv_france->getStation("Montpellier");
echo ($tgv_france->canGoFromTo($from, $to) ? "oui" : "non")."\n";//"no"


echo "Le plus court chemin pour aller de Calais à Toulouse est :\n";