#!/usr/bin/env python3 # TP1 info601 # NOM : Alan Turing # groupe L3-info-00101101 import random import sys from getopt import GetoptError from getopt import gnu_getopt as getopt from typing import Any, List, Optional from graph import CylinderGrid, Graph, Grid, HexGrid, RectGrid def main_test(*args: str) -> None: """fonction de test appelée depuis la ligne de commande avec l'option -T / --test `args[0]`, `args[1]`, etc. contiennent les chaines données sur la ligne de commande. Par exemple, $ python3 maze-ALAN.py -T pomme poire appellera cette fonction avec `args=["pomme", "poire"]`. """ print("fonction main_test") G = Graph.from_file(args[0]) print(f"le graphe contient {G.N} sommets") ... # # P = [int(args[i]) for i in range(1, len(args))] # if is_path(G, P): # print("la liste des sommets donnée forme un chemin dans le graphe") # else: # print("la liste des sommets donnée ne forme PAS un chemin dans le graphe") def degre_max(G: Graph) -> int: """renvoie le degré maximal du graphe `G`""" ... return 0 def is_path(G: Graph, P: List[int]) -> bool: """renvoie vrai si les sommets de `P` forment un chemin dans le graphe `G`""" ... return False def DFS(G: Graph, v0: int, v1: Optional[int] = None) -> List[Optional[int]]: """Fait un parcours en profondeur ("depth first search") sur le graphe `G` en partant du sommet `v0`. Si le sommet `v1` est donné, le parcours est stoppé dès que le sommet `v1` est rencontré. La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit lors du parcours.""" ... return [] def BFS0(G: Graph, v0: int, v1: Optional[int] = None) -> List[Optional[int]]: """Fait un parcours en largeur ("breadth first search") naïf sur le graphe `G` en partant du sommet `v0`. Ce parcours est obtenu en modifiant une ligne du parcours en profondeur : le sommet courant est récupéré dans la première case du tableau "ATraiter". Si le sommet `v1` est donné, le parcours est stoppé dès que le sommet `v1` est rencontré. La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit lors du parcours.""" ... return [] def BFS(G: Graph, v0: int, v1: Optional[int] = None) -> List[Optional[int]]: """Fait un parcours en largeur ("breadth first search") sur le graphe `G` en partant du sommet `v0`. Ce parcours est obtenu en modifiant le parcours en profondeur : le tableau "ATraiter" est une file (type `deque` de Python) plutôt qu'un tableau. Si le sommet `v1` est donné, le parcours est stoppé dès que le sommet `v1` est rencontré. La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit lors du parcours.""" ... return [] def pred_to_path(Pred: List[Optional[int]], v0: int, v1: int) -> List[int]: """extrait le chemin de v0 à v1 du tableau `Pred` renvoyé par un parcours ATTENTION à l'ordre du résultat : le tableau doit commencer par `v0`, finir par `v1`, et deux sommets consécutifs doivent correspondre à une arête du graphe de départ. Note: vous pouvez supposer que `v1` a bien été atteint par le parcours.""" P: List[int] = [] ... return P def random_search(G: Graph, v0: int, v1: Optional[int] = None) -> List[Optional[int]]: """Fait un parcours aléatoire sur le graphe `G` en partant du sommet `v0`. À chaque étape, un sommet aléatoire est extrait du tableau `ATraiter`. Si le sommet `v1` est donné, le parcours est stoppé dès que le sommet `v1` est rencontré. La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit lors du parcours.""" ... return [] def braid_maze(G: Graph, M: Graph, prob: float = 1.0) -> None: """Supprime les culs de sacs dans le labyrinthe `M` sur la grille `G`. Chaque cul de sac est supprimé avec probabilité `prob`. Un cul de sac est n'importe quel sommet de degré 1 dans `M`. Pour le supprimer, il suffit d'ajouter une arête (une "porte") vers une case voisine pour augmenter le degré du sommet.""" ... ######################################### # NE MODIFIEZ PAS LA SUITE DU PROGRAMME # ######################################### def error(*args: Any, **kwargs: Any) -> None: kwargs["file"] = sys.stderr print(*args, **kwargs) def pred_2_cells(Pred: List[Optional[int]], v2: Optional[int] = None, chars: str = "·x ") -> List[str]: C = [chars[2]] * len(Pred) for s, p in enumerate(Pred): if p is not None: C[s] = chars[1] while v2 is not None: C[v2] = chars[0] v2 = Pred[v2] return C ALGORITHMS = ["DFS", "BFS0", "BFS1", "BFS", "BFS_opt", "random_search"] def help(exe: str) -> None: print( f"""usage {exe} [OPTIONS] ARGS where OPTIONS can be -A ALGO / --algorithm=ALGO which search algorithm to use --start=N start search from vertex N (default: 0, except when option --randomize is given) --end=N stop the search when vertex N is reached (default: only stop when all reachable vertices have been seen) -R WxH / --rect=WxH use a rectangular grid of specified width and height -C WxH / --cyl=WxH use a cylindrical grid of specified width and height -H WxH / --hex=WxH use hex grid of specified width and height -r / --randomize randomize neighboors order in the graph, and starting vertex -B PROB / --braid PROB "braid" the resulting maze by removing deadends with probability PROB -q / --quiet don't show the result -v / --verbose always show the result -o FILE / --output FILE save the resulting graph in the file (or stdin) -h / --help this message -T / --test call the `main_test` function with the arguments All other options are ignored. --random-graph generate a random maze to stdout ALGO can be a comma separated list of algorithms taken among {", ".join(ALGORITHMS)} ARGS can have several forms If --random-graph is given, ARGS should be of the form N Dmin Dmax where N is the number of nodes. For each node, a random number (between Dmin and Dmax) of random neighboors are chosen. If -R / -C / -H is given, and ARGS is empty, the algorithm is used to generated a spanning tree on the corresponding grid. The "--end" option is ignored and the result is shown as a grid. If neither -R, -C nor -H is given, ARGS should be of the form FILE, and the algorithm is used to perform a search. When the file contains a grid graph, the result is shown as a grid, otherwise, the raw Pred array is printed. """ ) def main(argv: List[str]) -> None: if len(argv) == 1: help(argv[0]) exit(1) RECT = "rect" CYL = "cyl" HEX = "hex" FILE = "file" GEN = "generate" SEARCH = "search" short_options = "A:R:C:H:rqvo:B:PhT" long_options = [ "algorithm:", "rect=", "cyl=", "hex=", "start=", "end=", "randomize", "quiet", "verbose", "output=", "braid=", "help", "test", "random-graph", ] try: opts, args = getopt(argv[1:], short_options, long_options) except GetoptError as err: error(err) exit(2) algorithms = [] grid = FILE braid_prob = 0.0 quiet = False verbose = False output_filename = None randomize = False v0s = None v0 = None v1s = None v1 = None size = None for o, a in opts: if o in ["-T", "--test"]: return main_test(*args) elif o in ["--random-graph"]: try: n = int(args[0]) dmin = int(args[1]) dmax = int(args[2]) except (IndexError, ValueError): error("*** expected 3 numbers N Dmin Dmax") exit(3) G = Graph.random_graph(n, dmin, dmax, symmetric=True) G.to_file("-") return elif o in ["-A", "--algorithm"]: algorithms.extend(a.split(",")) elif o in ["-R", "--rect"]: grid = RECT try: w, h = a.split("x") size = (int(w), int(h)) except ValueError: error("*** size of grid must have the form 'WIDTHxHEIGHT'") exit(3) elif o in ["-C", "--cyl"]: grid = CYL try: w, h = a.split("x") size = (int(w), int(h)) except ValueError: error("*** size of grid must have the form 'WIDTHxHEIGHT'") exit(3) elif o in ["-H", "--hex"]: grid = HEX try: w, h = a.split("x") size = (int(w), int(h)) except ValueError: error("*** size of grid must have the form 'WIDTHxHEIGHT'") exit(3) elif o in ["--start"]: v0s = a elif o in ["--end"]: v1s = a elif o in ["-r", "--randomize"]: randomize = True elif o in ["-B", "--braid"]: try: braid_prob = float(a) except ValueError: error(f"*** braid probabilit should be a number between 0 and 1 (got '{a}')") exit(3) elif o in ["-q", "--quiet"]: quiet = True verbose = False elif o in ["-v", "--verbose"]: quiet = False verbose = True elif o in ["-o", "--output"]: output_filename = a elif o in ["-h", "--help"]: help(argv[0]) exit(0) if grid != FILE and len(args) > 0: error("for grids, argument is empty") exit(1) elif grid == FILE and len(args) != 1: error("in file mode, a single argument is expected") exit(1) if grid == FILE: mode = SEARCH filename = args[0] G = Graph.from_file(filename) else: assert size is not None mode = GEN width = size[0] height = size[1] v1 = None # in generation mode, we don't want the search to stop before the end! if grid == RECT: G = RectGrid.full(width, height) elif grid == CYL: G = CylinderGrid.full(width, height) elif grid == HEX: G = HexGrid.full(width, height) if randomize: G.randomize() if v0s is None: if randomize: v0 = random.randrange(G.N) else: v0 = 0 else: try: if "," in v0s: assert isinstance(G, Grid) x, y = v0s.split(",") v0 = G.idx(int(x), int(y)) else: v0 = int(v0s) except (ValueError, AttributeError): error(f"invalid vertex '{v0s}'") exit(2) if v1s is not None: try: if "," in v1s: assert isinstance(G, Grid) x, y = v1s.split(",") v1 = G.idx(int(x), int(y)) else: v1 = int(v1s) except (ValueError, AttributeError): error(f"invalid vertex '{v1s}'") exit(2) if not algorithms: algorithms = ["DFS"] elif "all" in algorithms: algorithms = ALGORITHMS for algo in algorithms: if algo in ALGORITHMS: try: Pred = globals()[algo](G, v0, v1=v1) except Exception as err: error(f"error encountered: {err}\n") continue else: error(f"unknown algorithm: '{algo}'") exit(1) if len(algorithms) > 1: print(f"algorithm: {algo}") M: Graph if mode == GEN: assert isinstance(G, Grid) if grid == RECT: M = RectGrid(G.width, G.height) elif grid == CYL: M = CylinderGrid(G.width, G.height) elif grid == HEX: M = HexGrid(G.width, G.height) M.pred2edges(Pred) if mode == GEN and braid_prob > 0: try: braid_maze(G, M, braid_prob) except NameError: error("IL FAUT DÉFINIR LA FONCTION `BRAID_MAZE(g, m)` POUR UTILISER CETTE FONCTIONNALITÉ.") exit(7) C = None elif mode == SEARCH: M = G C = pred_2_cells(Pred, v1, chars=".x ") C[v0] = "@" if v1 is not None: C[v1] = "$" if Pred[v1] is not None: l = 0 v = v1 while v is not None: v = Pred[v] l += 1 print(f"found a path of length {l}") if output_filename is not None: if grid == RECT: header = f"%rect {width} {height}" elif grid == CYL: header = f"%cyl {width} {height}" elif grid == HEX: header = f"%hex {width} {height}" else: header = "" assert isinstance(M, Grid) M.to_file(output_filename, header=header) continue if not quiet: if isinstance(M, (RectGrid, CylinderGrid, HexGrid)): M.show(C="".join(C) if C else None) else: if (G.N < 256 and not quiet) or verbose: print("Pred =", Pred) if v1 is None: print(f"The corresponding tree contains {1+len(Pred)-Pred.count(None)} nodes.") else: if Pred[v1] is not None: print(f"path from {v0} to {v1}: {pred_to_path(Pred, v0, v1)}") else: print(f"{v1} is not reachable from {v0}") if len(algorithms) > 1: print() if __name__ == "__main__": main(sys.argv) # vim: textwidth=100 foldmethod=indent