Tourner en rond

On souhaite se diriger à l'intérieur d'une ville, et notamment savoir s'il est possible de tourner en rond.

On représente la circulation dans une ville par un graphe orienté, où chaque sommet correspond à un lieu de la ville et chaque arête au sens de circulation entre deux lieux.

Exemple de plan de circulation

flowchart LR
    A([Lycée]) --> B([Mairie])
    B --> A
    B --> E([Médiathèque])
    C([Port]) --> B
    B --> C
    D([Ecole]) --> G([Maison])
    E --> B
    E --> D
    G --> E
    E --> F([Stade])
    F --> G

Pour aller au Stade depuis le Lycée, on pourra emprunter le chemin Lycée - Mairie - Médiathèque - Stade.

Il est à noter que depuis la Médiathèque, on peut revenir à la Médiathèque en passant par l'Ecole puis la Maison.

Imaginons maintenant qu'il y a des travaux sur certaines routes qui sont désormais fermées. La circulation devient alors :

flowchart LR
    A([Lycée]) --> B([Mairie])
    B --> E([Médiathèque])
    C([Port]) --> B
    D([Ecole]) --> G([Maison])
    E --> D
    E --> F([Stade])
    F --> G

Dans ce nouveau graphe, il n'y a plus de chemin possible depuis la Maison vers le Port.

De plus, quel que soit le lieu, il n'existe pas de chemin qui part de ce lieu et qui y revient.

On représente ce graphe par un dictionnaire dans lequel :

les clés sont les chaînes de caractères correspondant aux noms des lieux,
les valeurs associées sont des listes de chaînes de caractères représentant les lieux vers lesquels on peut se diriger.

1. Fonction existe_chemin

On se demande si, connaissant un plan de circulation, il est possible de se rendre d'un point de départ à un point d'arrivée.

Vous devez donc d'écrire une fonction existe_chemin qui :

prend en paramètre un dictionnaire graphe représentant une telle circulation, une chaîne de caractères depart qui représente le lieu de départ et une chaîne de caractères arrivee qui représente le lieu d'arrivée ;
renvoie True si un chemin existe entre le lieu de départ et le lieu d'arrivée, False sinon.

Exemples

>>> circulation = {
...   "Lycee": ["Mairie"],
...   "Port": ["Mairie"],
...   "Mairie": ["Lycee", "Mediatheque", "Port"],
...   "Mediatheque": ["Mairie", "Ecole", "Stade"],
...   "Ecole": ["Maison"],
...   "Stade": ["Maison"],
...   "Maison": ["Mediatheque"],
... }
>>> existe_chemin(circulation, "Lycee", "Mediatheque")
True

>>> circulation_en_travaux = {
...   "Lycee": ["Mairie"],
...   "Port": ["Mairie"],
...   "Mairie": ["Mediatheque"],
...   "Mediatheque": ["Ecole", "Stade"],
...   "Ecole": ["Maison"],
...   "Stade": ["Maison"],
...   "Maison": [],
... }
>>> existe_chemin(circulation_en_travaux, "Maison", "Port")
False

Aide

On pourra utiliser un parcours du graphe.

À ce titre, on fournit les classes Pile et File dont on donne les interfaces ci-dessous.

Ces deux classes sont déjà importées dans les différents éditeurs.

Interface de la classe Pile

p = Pile() : crée une pile vide et l'affecte à la variable p;
p.est_vide() : renvoie le booléen indiquant si la pile p est vide ;
p.empile(x) : empile l'élément x dans la pile p;
p.depile() : dépile un élément de la pile p si elle n'est pas vide et le renvoie. Provoque une erreur si la pile est vide.

La classe Pile

class Pile:
    def __init__(self):
        """Initialise une pile vide"""
        self.valeurs = []

    def est_vide(self):
        """Renvoie un booléen : la pile est-elle vide ?"""
        return len(self.valeurs) == 0

    def empile(self, element):
        """Empile un élément au sommet de la pile"""
        self.valeurs.append(element)

    def depile(self):
        """
        Dépile un élément au sommet et le renvoie.
        Provoque une erreur si la pile est vide.
        """
        if self.est_vide():
            raise ValueError("Erreur, pile vide")
        else:
            return self.valeurs.pop()

    def __repr__(self):
        """Affiche la pile, en indiquant le sommet"""
        return f"| {' | '.join([str(x) for x in self.valeurs])} | <- sommet"

Interface de la classe File

f = File() : crée une file vide et l'affecte à la variable f;
f.est_vide() : renvoie le booléen indiquant si la file f est vide ;
f.enfile(x) : enfile l'élément x dans la file f;
f.defile() : défile un élément de la file f si elle n'est pas vide et le renvoie. Provoque une erreur si la file est vide.

La classe File

from collections import deque


class File:
    """Classe définissant une structure de file"""

    def __init__(self):
        self.valeurs = deque([])

    def est_vide(self):
        """Renvoie le booléen True si la file est vide, False sinon"""
        return len(self.valeurs) == 0

    def enfile(self, x):
        """Place x à la queue de la file"""
        self.valeurs.appendleft(x)

    def defile(self):
        """Retire et renvoie l'élément placé à la tête de la file.
        Provoque une erreur si la file est vide
        """
        if self.est_vide():
            raise ValueError("La file est vide")
        return self.valeurs.pop()

    def __repr__(self):
        """Convertit la file en une chaîne de caractères"""
        if self.est_vide():
            return "∅"
        return f"(queue) {' -> '.join(str(x) for x in self.valeurs)} (tête)"

Version videVersion à trous (profondeur)Version à trous (largeur)

Évaluations restantes : 10/10

.128013s3o_8bcdufvg/T0ly n7apS.r1Fme,(P2=4V:}twk{i9][5hx)6050i0D0N0v0R0q0b0s0h0q0v0b0b0I010N0R0w010406050b0j0C0C0v0z0r040x0d0q0j0@0d0t050n0~1012140|0w041d1k051n0n1n1p1k0|0i0R0l0,0.0:0=0W0R0m0W0q1D0W0N0`050%0g0q0D1y0/0;011C1E1G1E0N1M1O1K0N0g0d0i141L0z1l0N0W0,170b0w0v0t0=0H011Q1A010k0)0D0t0v0C0D1K1=1@1|1S1 1O22240`0a0s0G0z0d0w0d0b0R1a0t0s0#1:0z0z0D0h2p1d270t1l0n1.2C0N1,1+1-0i290=1G0t212m1K1v1x0-1R2M0R2O0t1(1w1K0w2v1l2A2C2*0}1?2q2U1}2Z0z110q0`0s0A2z2.0{2-282:1S2=2@2_0H2|1@2~2A2L01330v2^040s0c372B0|3a310=3d3f0s0J3j392.3b3p2_0V3t3l3v3n3c0d2?3e2_0Z3A2 2/1z323F343g0u3K3m3N3o3P3H3g0f3T3C3V3E3G3q0S3#303%3x040A0p3,3M2V3(3Q0A2{1e2}3B3-3^3/0A363}383 3@2;3X3f0A3i453k3L3w4a0`0A3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0A3+4K4o3O4w0H3=4Q484S3Q0H3|2*4u4B4H0H444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0H4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0c4V5h4M3Q0c4#2}1m2(1d2S2F0i2J3b0h1(251l5v1o5t2,4m055A0#2)4`1S0h0A0`030s0K0D0z2n1b0s0v0l2w0s0j2q1?0z5A0j5W0s210s2%0d0k1b0#5-5/0N2r1b0h5%2O5;203?3b0P0`0#0k3t4-3^0O2_6a4=320k0`0D0X0R0b0N0D0e0h0W0D0C2X6f5N0=0_040F6w503c0`0m0z0v0w6s6C55016z0E3t0s6b2;670D5*0N6L3b6O6Q6S320`120z1w0D0D6Y3D6z0Y0L3A0s6@6R6g3o0`0w634m6_6x010d0`0I6#6`6E040G6~2,776z0F0Y6?6^6$6{040l6m2o0D0b76717304756 7j6N0`0Q0M7h6@7x0t6|7b5r777t0y6.3.6j0C6}1O7M3^7e7S6T040#6W7V1S6:7C706D66040O1C7R7w7J6d042Z6X7/717F047Q6-5I7J0`7L7~7_6j6n0e7m0#7!6y0`7f6=4t6^8f7(6M7`5,6H0t7@2*8h3b7t7v8o7E7G7.7c7s8089787Y7H387x7e7g8e8g7D777`7m2n6o7q826D6z0U8A8j0d5-1@8n7I716z0T7r6D8r8)6M0P0h0`0o0z0j7}4$8J8K717*0R697^6D7`6)6+8@2}8p3D0d7;6v8 8i6F6H6J948E7d0`8U8R9c048k8Z8A8%8d8^8_8f7x7*2v0N5-1c9b658/048;8?7%9v777*5@0z8,3w6j0%0w9g2B963%980`9a8t8L9d6I6K9l6Z9j8V0`9o8m9q0`0T9s3~9u9J8{9Y8~9!7s7;7?9O4B9Q6I9T3g7x9X049Z958u7l7n8P9:049?469^8_ac7|8A7K9,046tan9)6/8baq0$a4ag8H9tak9_900`8N7o8Q8x8S9+au7Nar9Ra58F9;a19W74aU3^8.8:8=a506aE8-0`9y9AaX1}aZ040B3e0ba$4%3%5P5R5T5V5X2q5!5$5(5;128k0+5:0.0z0m0D5`0$5}0t5 5(1P2ba$9w6U9|8#6D7;6RaN416iar6l6n6p6r6taa9h8$awbs7W6G9%aR9i046P9Ca27X6V128!bCaLbLa-6%04925#bJbD046;7%acbjbW0=8+bNaO0B8D2BaS6AaB9@7i9#ad8O7pb,72aWb/7T7z7B8I8`aF04b+bF1Sapcc7k21cbaK6M7Ucf8BbQ0zbSb?bKb_ajb{9`7+7-a59V3^a8a0c37Wcibo6Mcecj9Par8587b#bU8c9Icvc99.cqa67 7uc07`cGbTcI8zcm7`68b=5McQct3k9uacaHafcm8TaqcVag8(cEcdc29}7)9E9Ga$c=9K9{c!6(2u93c0a8bB9UacbH9fag9kcKbOc|c_9;aic;aDbl04a+0z9Bd28-d4a#cSc8a)ca3FdaaPazc b-99dzabb|dj9(dn3%c`c*9-8X8lcWb@9=dE8gdv8}de9 0dcWcA7Way9Sd,9YdP38d:bXc@b dqahd(d783cac-a7c)dU416j0tc$crb$6BdXdKd?d c:0{aDd)b|d}aJcH9*04dmerbOd=cPckaTdMc1cZeBa/d5b)d8dw0$a,eE9Ea;0*bk0n5K0D2C2%eT5u1w5w2F2H2D1%1)2F0v1NeW0n5v0|e-ay0)0b04.

Évaluations restantes : 10/10

.128013s3o_8bcdufvg/T0ly n7apS.r1Fme,(P2=4:}twk{i9][5hx)6050i0D0M0v0Q0q0b0s0h0q0v0b0b0I010M0Q0w010406050b0j0C0C0v0z0r040x0d0q0j0?0d0t050n0}0 11130{0w041c1j051m0n1m1o1j0{0i0Q0l0+0-0/0;0V0Q0m0V0q1C0V0M0_050$0g0q0D1x0.0:011B1D1F1D0M1L1N1J0M0g0d0i131K0z1k0M0V0+160b0w0v0t0;0H011P1z010k0(0D0t0v0C0D1J1;1?1{1R1~1N21230_0a0s0G0z0d0w0d0b0Q190t0s0!1/0z0z0D0h2o1c260t1k0n1-2B0M1+1*1,0i280;1F0t202l1J1u1w0,1Q2L0Q2N0t1%1v1J0w2u1k2z2B2)0|1=2p2T1|2Y0z100q0_0s0A2y2-0`2,272/1R2;2?2^0H2{1?2}2z2K01320v2@040s0c362A0{39300;3c3e0s0J3i382-3a3o2^0U3s3k3u3m3b0d2=3d2^0Y3z2~2.1y313E333f0u3J3l3M3n3O3G3f0f3S3B3U3D3F3p0R3!2 3$3w040A0p3+3L2U3%3P0A2`1d2|3A3,3@3.0A353|373~3?2:3W3e0A3h442A1l2%1c2R2E0i2I3a0h1%241k4i1n4g2+4d1k4n0!2(3#3@0O0_0!0k3s3K3a0N2^4G3T400k0_0D0W0Q0b0M0D0e0h0V0D0C2W4L4A1|0^040F4$3 2:0_0m0z0v0w4Y4,471R4)0E3s0s4H3C0t4D0D1=0z0M4^3a4{4}4 3-0_110z1v0D0D573C4)0X0K3z0s5p4~4M4.040w1 5a5s1R0d0_0I5x4%310_0G5w4v5b3@4)0F0X5o5q5K5t0l4S2n0D0b5D4-5z5B5Y4_0;4)0P0L5P5p5R5F5u5I2+5y0;5A040y5j5c044Z5v1N5{5L0_4+5J5?3b525456655E5(0_5O4v065q5r6c014C040N1B604v6j5Z5@4J042Y6a2)6s5%675:6q5=6k5^5`6b6t6C5W0M0e5T0!614(635m5,6i6A3v0_4n0j4;0t6y2|6X3C5^5C6r5.3n0_5 5i6J6B6H6R5/0!6=6`6d4*6f2)6h6W5-666m0Q4F6.6651045e5g6?6z6/010d6v4#7a6k7c4:4=4@6@580_0T6~6C6!6$6(377i4)0S5n6g74747i6m2u0M6#1b7n6K0O0h0_0o0z0j7g3}7I6*3$6m0k3E5$6Y5}0$0w7Y377#3@7k0_7m7h7b4/4;4?7/4e664)7w7t506Z0d6#1?7B7 6k7E7G727!6i7K7@797_6G6v6x7*847,4=7~3f7i7?047^6)7i7c5T2m4U5X833$4)8d7Z8f7J7`6D8s8u0_6I6F6K7c5~5;2|7D637x8U7-8O806e6V8K757o0_8B5V8E8S6B818!4P8$7x7E8o3$6,8}4B7T047V7X6V8h047M7O901|7S0_0B3d0b8s0{0n4x0D2B2$9m4h1v4j2E2G2C1$1(2E0v1M9p0n4i9j0!0$0(0b04.

Évaluations restantes : 10/10

.128013s3o_8bcdufvg/T0ly n7apS.r1Fme,(P2=4:}twk{i9][5hx)6050i0D0M0v0Q0q0b0s0h0q0v0b0b0I010M0Q0w010406050b0j0C0C0v0z0r040x0d0q0j0?0d0t050n0}0 11130{0w041c1j051m0n1m1o1j0{0i0Q0l0+0-0/0;0V0Q0m0V0q1C0V0M0_050$0g0q0D1x0.0:011B1D1F1D0M1L1N1J0M0g0d0i131K0z1k0M0V0+160b0w0v0t0;0H011P1z010k0(0D0t0v0C0D1J1;1?1{1R1~1N21230_0a0s0G0z0d0w0d0b0Q190t0s0!1/0z0z0D0h2o1c260t1k0n1-2B0M1+1*1,0i280;1F0t202l1J1u1w0,1Q2L0Q2N0t1%1v1J0w2u1k2z2B2)0|1=2p2T1|2Y0z100q0_0s0A2y2-0`2,272/1R2;2?2^0H2{1?2}2z2K01320v2@040s0c362A0{39300;3c3e0s0J3i382-3a3o2^0U3s3k3u3m3b0d2=3d2^0Y3z2~2.1y313E333f0u3J3l3M3n3O3G3f0f3S3B3U3D3F3p0R3!2 3$3w040A0p3+3L2U3%3P0A2`1d2|3A3,3@3.0A353|373~3?2:3W3e0A3h442A1l2%1c2R2E0i2I3a0h1%241k4i1n4g2+4d1k4n0!2(3#3@0O0_0!0k3s3K3a0N2^4G3T400k0_0D0W0Q0b0M0D0e0h0V0D0C2W4L4A1|0^040F4$3 2:0_0m0z0v0w4Y4,471R4)0E3s0s4H3C0t4D0D1=0z0M4^3a4{4}4 3-0_110z1v0D0D573C4)0X0K3z0s5p4~4M4.042a5i4v5r4%1R0d0_0I5a5s310_0B1 5j3$4)0F0X5o5q5b400_0l4S2n0D0b5E5z0;5B045D5x5R4(0_0P0L5P5p5*5G5u5J4v5;5#0_0y5K5S04205v5}5+4*625=0!54565^5F0;5l5/5y4-1R4C040N1B1N5Z6g5#4J042Y692)6f4_3n0_616a5!015$5|6A6o3b4P4T0e5U0!656c0_5N5n4v065q6U6v3v0_4n0j4;0t6t2|6W3C5$5(6u5_6H5?6m6F6w6C5{6N6/4E5@2+6b015M5O6S6V5Q6~6i0Q4F5)6~51045e5g5w6-6~0d6q4#796B7b4:4=4@6=580_0T6_7b6Z6#6%376.4)0S6R2)6T736V6.6i2u0M6!1b7l6G0O0h0_0o0z0j7f3}7H6)3$6i0k3E6n6?7b0#4=7X377!3@7i0_7k7g7m4/4;4?7.4e6~4)7u7r506Y0d6!1?7z7~6B7C7E7Y7Z746B76787^6G7=6r0d883f6.7+0$0w7}8p7h7j7O8j7*5T5V4U5Y825L0_8c458e7H8q6y6|2|6.6D7v4P0t6z6}8a6P8S5 8s8u7B0_717F8K738M045U2m8D6_808Z7,8t8=0_0S7)3a6+8}3C7R7T7V8u7G5:750_7L7N907#7S040B3d0b951c4x0D2B2$9m4h1v4j2E2G2C1$1(2E0v1M9p0n4i0{9C7,0(0b04.

2. Fonction contient_cycle

Un promeneur se demande s'il est possible, connaissant le plan de circulation, de faire au moins une promenade débutant et se terminant au même endroit de la ville : une promenade allant du Lycée au Lycée ou une autre allant du Port au Port, etc.

Si au moins une telle promenade existe, on dit que le graphe représentant le plan de circulation contient un cycle.

Vous devez donc d'écrire une fonction contient_cycle qui :

prend en paramètre un dictionnaire graphe représentant une telle circulation ;
renvoie True si le graphe contient un cycle, False sinon.

La fonction existe_chemin de la question précédente est déjà importée dans cet éditeur.

Exemple

>>> circulation = {
...   "Lycee": ["Mairie"],
...   "Port": ["Mairie"],
...   "Mairie": ["Lycee", "Mediatheque", "Port"],
...   "Mediatheque": ["Mairie", "Ecole", "Stade"],
...   "Ecole": ["Maison"],
...   "Stade": ["Maison"],
...   "Maison": ["Mediatheque"],
... }
>>> contient_cycle(circulation)
True

>>> circulation_en_travaux = {
...   "Lycee": ["Mairie"],
...   "Port": ["Mairie"],
...   "Mairie": ["Mediatheque"],
...   "Mediatheque": ["Ecole", "Stade"],
...   "Ecole": ["Maison"],
...   "Stade": ["Maison"],
...   "Maison": [],
... }
>>> contient_cyle(circulation_en_travaux)
False

Évaluations restantes : 10/10

.128013s3o_bcdufvg/Tly napSr1Fme,(P2=4:twki5hx)050h0z0H0s0K0o0b0q0g0o0s0b0b0E010H0K0t010406050b0i0y0y0s0v0p040u0d0o0i0)0d0r050m0:0=0@0_0.0t041219051c0m1c1e190.0h0K0k0X0Z0#0%0M0K0l0M0o1s0M0H0,050S0f0o0z1n0!0$011r1t1v1t0H1B1D1z0H0f0d0h0_1A0v1a0H0M0X0|0b0t0s0r0%0D011F1p010j0U0z0r0s0y0z1z1%1)1.1H1;1D1@1_0,0a0q0C0v0d0t0d0b0K0 0r0q0Q1#0v0v0z0g2e121|0r1a0m1Z2r0H1X1W1Y0h1~0%1v0r1?2b1z1k1m0Y1G2B0K2D0r1T1l1z0t2k1a2p2r2V0/1(2f2J1/2O0v0?0o0,0w2o2Z0-2Y1}2#1H2%2)0,0D2-1)2/2p2A012@0s2*040c2{2q0.2~2=0%31330F362}2Z2 3c0,0L3f1b2T122H2u0h2y2 0g1T1`1a3q1d3o2X132.053v0Q2U3h3a010J0,0Q0j3m391o1H0I0,0q3Q3J3S3b0j0,3v0r0)1?0H0e0g0p0Y0z3X2;3Z010+040B3;2!3?0r0,0l0v0s0t0M3:3D2|2:3|2K3@0,0O0G3f060q4h3W3R4a3M040j0d0v3f4j3Y4a3~041v0z0i4r482 0d3U042M4A4k2$3 4143452X4I1H3^4e46374i4V4s3=4l0,0K3P4T044X494J040z0N0K0b0H0z3,440y4G4%4B3K3^3`4`4P3b4K42443{2 3^0A4H4t4+4x4z4 5a4Q0,584%4)3i0,5c554|4c4S2V4g4W5u4{3?4m2k0H0i0v115j5w4l0g0,0n0v0i4N2.5t4h5F1/5y0R5B5D2V5k3K0J5H040x320b5M2|0.0m3G0z2r2S5.3p1l3r2u2w2s1S1U2u0s1C5;0m3q5+0Q0S0U0b04.