#!/usr/bin/env python # coding: utf-8 # # Table of Contents #
# # [ALGO1 : Introduction à l'algorithmique](https://perso.crans.org/besson/teach/info1_algo1_2019/) # # - [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : https://perso.crans.org/besson/teach/info1_algo1_2019/ # - Magistère d'Informatique de Rennes - ENS Rennes - Année 2019/2020 # - Intervenants : # + Cours : [Lilian Besson](https://perso.crans.org/besson/) # + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/) # - Références : # + [Open Data Structures](http://opendatastructures.org/ods-python.pdf) # # Cours Magistral 4 & 5 # # - Ce cours traite de graphes. # - On donne le type abstrait des graphes, et plusieurs implémentations de la même structure de données (plusieurs classes). # # - CM4 : On implémente le parcours en profondeur, qu'on illustre sur quelques exemples. # - CM5 : On implémente le parcours en largeur, qu'on illustre sur quelques exemples. # ---- # ## Type abstrait des $\alpha$ graphes # # On se donne un type $\alpha$ pour les sommets, et on va en fait se restreindre à $\alpha=$ `int`, et les sommets seront $\{0,\dots,n-1\}$ où $n = |S|$ pour des graphes $G = (S, A)$. # # On va écrire une classe qui implémente des opérations "plus haut niveau", en fonction des opérations bas niveau. # # Pour l'afficher, on va utiliser la librarie [networkx](https://networkx.github.io/documentation/stable/tutorial.html#drawing-graphs) # In[140]: import networkx as nx # In[170]: class BaseGraph(): def out_degree(self, vertex): return len(self.succ(vertex)) def in_degree(self, vertex): return len(self.pred(vertex)) def degree(self, vertex): return len(self.neighbors(vertex)) def is_vertex(self, vertex): """ Test presence of a vertex.""" return vertex in self.vertexes @property def vertexes(self): """ List of vertexes.""" return list(range(self.nb_vertexes)) def is_neighbor(self, u, v): """ Test neighborhood.""" return u in self.neighbors(v) @property def edges(self): """ Set of edges (pairs), in O(|A|) if well implemented.""" return {(u, v) for u in self.vertexes for v in self.neighbors(u)} @property def nb_edges(self): return len(self.edges) def draw(self): G = nx.DiGraph() if self.oriented else nx.Graph() G.add_nodes_from(self.vertexes) G.add_edges_from(self.edges) return nx.draw_kamada_kawai(G, with_labels=True, font_weight='bold') # ### Un premier exemple de graphe # # On va travailler avec le graphe exemple suivant, qu'il soit orienté ou non : # # | Orienté | Non orienté | # |---------|-------------| # | | | # In[183]: def defaultGraph(GraphClass, oriented=True): print(f"Creating empty graph with class {GraphClass}...") graph = GraphClass(oriented=oriented) n = 7 for i in range(n): print(f"Adding vertex {i}...") graph.add_vertex(i) for edge in [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]: print(f"Adding edge {edge}...") graph.add_edge(*edge) return graph # In[184]: plt.figure() defaultGraph(AdjMatrixGraph, oriented=True).draw() plt.figure() defaultGraph(AdjMatrixGraph, oriented=False).draw() # On va tester les différentes implémentations avec la petite fonction suivante, qui vérifie que l'on peut accéder à toute l'information contenu dans le graphe. # In[143]: def test_defaultGraph(GraphClass): for oriented in [True, False]: graph = defaultGraph(GraphClass, oriented=oriented) print(f"Graph:") print(graph) print(f"Number of vertexes: {graph.nb_vertexes}") print(f"Is the graph oriented? {graph.oriented}") print(f"Number of edges: {graph.nb_edges}") print(f"List of vertexes: {graph.vertexes}") print(f"List of edges: {graph.edges}") for i in graph.vertexes: print(f" List of neighbors of {i}: {graph.neighbors(i)} (degree {graph.degree(i)})") print(f" List of succ of {i}: {graph.succ(i)} (out degree {graph.out_degree(i)})") print(f" List of pred of {i}: {graph.pred(i)} (in degree {graph.in_degree(i)})") # ### Graphe aléatoire de taille $n$ # # On va étudier un graphe aléatoire suivant un modèle très simple : on fixe $n$ le nombre de sommets, et ensuite chaque arête $(i, j)$ est ajoutée dans le graphe avec une probabilité $p\in(0,1)$ fixée ([graphe d'Erdös-Rényi](https://en.wikipedia.org/wiki/Erd%C5%91s-R%C3%A9nyi_model)). # In[144]: import random # In[145]: def with_probability(p): return random.random() <= p # In[146]: def randomGraph(GraphClass, n=10, probability=0.1, oriented=True): graph = GraphClass(oriented=oriented) for i in range(n): graph.add_vertex(i) for i in range(n): for j in range(n): if with_probability(probability): graph.add_edge(i, j) return graph # In[147]: print(randomGraph(AdjMatrixGraph, 10, 0.1, oriented=True)) # In[189]: plt.figure(figsize=(4, 3)) randomGraph(AdjMatrixGraph, 10, 0.1, oriented=True).draw() # In[190]: plt.figure(figsize=(4, 3)) randomGraph(AdjMatrixGraph, 10, 0.5, oriented=True).draw() # In[191]: plt.figure(figsize=(4, 3)) randomGraph(AdjMatrixGraph, 10, 0.5, oriented=False).draw() # In[192]: plt.figure(figsize=(4, 3)) randomGraph(AdjMatrixGraph, 10, 0.9, oriented=True).draw() # ---- # ## Trois différentes implémentations # ### Graphes par matrice d'adjacence # In[173]: import numpy as np # In[174]: class AdjMatrixGraph(BaseGraph): def __init__(self, oriented=True, n=0): """ Takes O(n^2) time and space.""" self.oriented = oriented self.nb_vertexes = n self._matrix = np.zeros((n, n), dtype=bool) def __str__(self): return str(self._matrix) def is_vertex(self, vertex): """ Test presence of a vertex.""" return 0 <= vertex < self.nb_vertexes def add_vertex(self, m): """ Worst case is O(m^2) to extend the matrix. Best case is O(1) if nothing to do.""" if not self.is_vertex(m): n = self.nb_vertexes assert 0 <= m and n <= m self.nb_vertexes = m + 1 old_matrix = self._matrix[:,:] # extend the matrix self._matrix = np.zeros((m + 1, m + 1), dtype=bool) # copy the old matrix self._matrix[:n, :n] = old_matrix def add_edge(self, i, j): """ O(1) time.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes self._matrix[i, j] = True if not self.oriented: self._matrix[j, i] = True def remove_vertex(self, m): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def remove_edge(self, i, j): """ O(1) time.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes self._matrix[i, j] = False if not self.oriented: self._matrix[j, i] = False def merge_vertexes(self, i, j): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def pred(self, i): assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_neighbor(j, i)] def is_pred(self, u, v): """ O(1) time.""" return self._matrix[v, u] def succ(self, i): assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_neighbor(i, j)] def is_succ(self, u, v): """ O(1) time.""" return self._matrix[u, v] def neighbors(self, i): assert 0 <= i < self.nb_vertexes if self.oriented: return self.succ(i) else: return [j for j in self.vertexes if self.is_neighbor(i, j) or self.is_neighbor(j, i)] def is_neighbor(self, u, v): """ O(1) time.""" if self.oriented: return self._matrix[u, v] else: return self._matrix[u, v] or self._matrix[v, u] # Testons cette première implémentation : # In[175]: defaultGraph(AdjMatrixGraph) # In[176]: test_defaultGraph(AdjMatrixGraph) # ### Graphes par listes d'adjacence # In[177]: class AdjListsGraph(BaseGraph): def __init__(self, oriented=True, n=0): """ Takes O(n) time and space to allocate the empty lists.""" self.oriented = oriented self.nb_vertexes = n self._lists = [ [] for i in range(n) ] def __str__(self): return str(self._lists) def is_vertex(self, vertex): """ Test presence of a vertex.""" return 0 <= vertex < self.nb_vertexes def add_vertex(self, m): """ Worst case is O(m^2) to extend the matrix. Best case is O(1) if nothing to do.""" if not self.is_vertex(m): n = self.nb_vertexes assert 0 <= m and n <= m self.nb_vertexes = m + 1 self._lists = [ [] if i >= n else self._lists[i] for i in range(m + 1) ] def add_edge(self, i, j): """ O(1) time: append j in head of list of neighbors of i.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes if not self.is_neighbor(i, j): self._lists[i].append(j) if not self.oriented: if not self.is_neighbor(j, i): self._lists[j].append(i) def remove_vertex(self, m): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def remove_edge(self, i, j): """ O(1) time.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes self._lists[i].remove(j) if not self.oriented: self._lists[j].remove(i) def merge_vertexes(self, i, j): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def pred(self, i): """ Not trivial, has to check all lists, in O(|S|*|A|).""" assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_pred(j, i)] def is_pred(self, u, v): """ O(|S|) time in worst case.""" return u in self._lists[v] def succ(self, i): """ Create a new list, to be sure that we don't modify the underlying self._lists. In O(deg(i)).""" assert 0 <= i < self.nb_vertexes return list(self._lists[i]) def is_succ(self, u, v): """ O(|S|) time in worst case.""" return v in self._lists[u] def neighbors(self, i): assert 0 <= i < self.nb_vertexes if self.oriented: return list(self.succ(i)) else: return [j for j in self.vertexes if self.is_neighbor(i, j)] def is_neighbor(self, u, v): """ O(|S|) time in worst case.""" if self.oriented: return v in self._lists[u] else: return v in self._lists[u] or u in self._lists[v] # Testons cette première implémentation : # In[178]: defaultGraph(AdjListsGraph) # In[179]: test_defaultGraph(AdjListsGraph) # ### Graphes par liste d'arêtes # In[180]: class EdgesListGraph(BaseGraph): def __init__(self, oriented=True, n=0): """ Takes O(n) time and space to allocate the empty lists.""" self.oriented = oriented self.nb_vertexes = n self._edges = set() def __str__(self): return str(self._edges) def is_vertex(self, vertex): """ Test presence of a vertex.""" return 0 <= vertex < self.nb_vertexes def add_vertex(self, m): """ Worst case is O(m^2) to extend the matrix. Best case is O(1) if nothing to do.""" if not self.is_vertex(m): n = self.nb_vertexes assert 0 <= m and n <= m self.nb_vertexes = m + 1 def add_edge(self, i, j): """ O(1) time: append j in head of list of neighbors of i.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes if not self.is_neighbor(i, j): self._edges.add((i, j)) if not self.oriented: if not self.is_neighbor(j, i): self._edges.add((j, i)) def remove_vertex(self, m): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def remove_edge(self, i, j): """ O(1) time.""" assert 0 <= i < self.nb_vertexes and 0 <= j < self.nb_vertexes self._edges.remove((i, j)) if not self.oriented: self._edges.remove((j, i)) def merge_vertexes(self, i, j): """ TODO do it yourself, it's not hard!""" raise NotImplementedError def pred(self, i): assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_pred(j, i)] def is_pred(self, u, v): """ O(|S|) time in worst case.""" return (v, u) in self._edges def succ(self, i): assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_succ(i, j)] def is_succ(self, u, v): """ O(|S|) time in worst case.""" return (u, v) in self._edges def neighbors(self, i): assert 0 <= i < self.nb_vertexes return [j for j in self.vertexes if self.is_neighbor(j, i)] def is_neighbor(self, u, v): """ O(|S|) time in worst case.""" if self.oriented: return (u, v) in self._edges else: return (u, v) in self._edges or (v, u) in self._edges # Testons cette première implémentation : # In[181]: defaultGraph(EdgesListGraph) # In[182]: test_defaultGraph(EdgesListGraph) # ---- # ## Test numérique des complexités des différentes opérations # # On rappelle qu'on devrait obtenir les résultats suivants, avec $n=|S|$ et $m=|A|$, que l'on va valider expérimentalement. # # | Opérations | Matrice d'adjacence | Listes d'adjacence | Liste d'arêtes | # |:-----------|---------------------|--------------------|----------------| # | Création (vide) | temps et mémoire $O(n^2)$ si vide | temps et mémoire $O(n)$ si vide | temps et mémoire $O(1)$ si vide | # | Ajoute un sommet $u$ | $O(n^2)$ (recopie) | $O(1)$ | $O(1)$ | # | Retire un sommet $u$ | $O(n^2)$ (recopie) | $O(d(u))$ si orienté, $O(n+m)$ sinon | $O(n)$ (suppression des arêtes) | # | Ajoute un arc $(u,v)$ | $O(1)$ | $O(d(u))$ si orienté, $O(d(u)+d(v))$ sinon | $O(1)$ (si liste d'arêtes) ou $O(1)$ en amorti (si ensemble d'arêtes) | # | Retire un arc $(u,v)$ | $O(1)$ | $O(d(u))$ si orienté, $O(d(u)+d(v))$ sinon | $O(n)$ (si liste d'arêtes) ou $O(1)$ en amorti (si ensemble d'arêtes) | # | Liste des sommets | $O(n)$ | $O(n)$ | $O(n)$ | # | Liste des arcs | $O(n^2)$ tout parcourir | $O(n)$ parcourir les $n$ listes de tailles $d(u)$, et $\sum_u d(u) = n$ | $O(1)$ (si liste d'arêtes) ou $O(n)$ (si ensemble d'arêtes) | # | Liste des voisins du nœud $u$ | $O(n)$ | $O(d(u))$ ($O(1)$ si on ne crée pas de nouvelle liste) | $O(n)$ | # | Degré du nœud $u$ | $O(n)$ | $O(n)$ | $O(n)$ | # | Liste des voisins sortant du nœud $u$ | $O(n)$ | $O(n)$ | $O(n)$ | # | Degré sortant du nœud $u$ | $O(n)$ | $O(n)$ | $O(n)$ | # | Liste des voisins entrant du nœud $u$ | $O(n)$ | $O(n)$ | $O(n)$ | # | Degré entrant du nœud $u$ | $O(n)$ | $O(n)$ | $O(n)$ | # # In[62]: try: from tqdm import tqdm_notebook except ImportError: def tqdm_notebook(iterator, *args, **kwargs): return iterator # In[64]: def random_vertex(n): return random.randint(0, n+1) def random_edge(n): return (random_vertex(n), random_vertex(n)) # ### Un exemple # In[116]: probability = 0.5 n = 1000 graph = randomGraph(AdjMatrixGraph, n=n, probability=probability) get_ipython().run_line_magic('timeit', 'graph.is_vertex(random_vertex(n))') get_ipython().run_line_magic('timeit', 'graph.add_vertex(n + 5)') get_ipython().run_line_magic('timeit', 'graph.add_edge(*random_edge(n))') get_ipython().run_line_magic('timeit', 'graph.remove_edge(*random_edge(n))') get_ipython().run_line_magic('timeit', 'graph.pred(random_vertex(n))') get_ipython().run_line_magic('timeit', 'graph.is_pred(*random_edge(n))') get_ipython().run_line_magic('timeit', 'graph.succ(random_vertex(n))') get_ipython().run_line_magic('timeit', 'graph.is_succ(*random_edge(n))') get_ipython().run_line_magic('timeit', 'graph.neighbors(random_vertex(n))') get_ipython().run_line_magic('timeit', 'graph.is_neighbor(*random_edge(n))') # Sans voir l'évolution en fonction de $n$, difficile de conclure quoi que ce soit de ces premières expériences… # ### Tests pour différentes tailles de graphes # # On va stocker les temps de calculs dans une petite structure de la forme suivante, qui permettra d'afficher directement des courbes (le traitement est fait plus bas). # In[80]: times = { # clé sur n "100": { # clé sur p r"|A| \simeq |S|": { "AdjMatrixGraph": { "operation1": 0.12, # ..., "operationN": 0.12, }, "AdjListsGraph": { "operation1": 0.12, # ..., "operationN": 0.12, }, "EdgesListGraph": { "operation1": 0.12, # ..., "operationN": 0.12, }, }, }, } # In[117]: import timeit # In[118]: times = {} for n in tqdm_notebook([100, 200, 400, 800, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000], desc="n"): number = 20 if n <= 200 else 5 # nb of repetitions of each operations # print(f"\n\n For graphs with {n} vertexes:") times[n] = {} for probability, pname in tqdm_notebook([ (1.0/n, r"|A| \simeq |S|"), # p = 1/n => |A| ~= |S| (1.0/np.sqrt(n), r"|A| \simeq |S|^{3/2}"), # p = 1/sqrt(n) => |A| ~= |S|^(3/2) (0.1, r"|A| \simeq 0.1 |S|^2"), # p = 0.1 => |A| ~= 0.1 |S|^2 ], desc="proba"): times[n][pname] = {} # print(f"\n and link probability of {probability}:") for GraphClass in [AdjMatrixGraph, AdjListsGraph, EdgesListGraph]: # print(f"\n for class {GraphClass}...") graph = randomGraph(GraphClass, n=n, probability=probability) the_times = {} the_times["randomGraph"] = timeit.timeit( "randomGraph(GraphClass, n=n, probability=probability)", globals=globals(), number=number, ) # print("Time to create a new graph:", the_times["randomGraph"]) the_times["is_vertex"] = timeit.timeit( "graph.is_vertex(random_vertex(n))", globals=globals(), number=number, ) # print("Time to test presence of a vertex:", the_times["is_vertex"]) the_times["add_vertex"] = timeit.timeit( "graph.add_vertex(n + 2)", globals=globals(), number=number, ) # print("Time to add the next vertex n + 2:", the_times["add_vertex"]) the_times["pred"] = timeit.timeit( "graph.pred(random_vertex(n))", globals=globals(), number=number, ) # print("Time to compute pred:", the_times["pred"]) the_times["is_pred"] = timeit.timeit( "graph.is_pred(*random_edge(n))", globals=globals(), number=number, ) # print("Time to test pred:", the_times["is_pred"]) the_times["succ"] = timeit.timeit( "graph.succ(random_vertex(n))", globals=globals(), number=number, ) # print("Time to compute succ:", the_times["succ"]) the_times["is_succ"] = timeit.timeit( "graph.is_succ(*random_edge(n))", globals=globals(), number=number, ) # print("Time to test succ:", the_times["is_succ"]) the_times["neighbors"] = timeit.timeit( "graph.neighbors(random_vertex(n))", globals=globals(), number=number, ) # print("Time to compute neighbors:", the_times["neighbors"]) the_times["is_neighbor"] = timeit.timeit( "graph.is_neighbor(*random_edge(n))", globals=globals(), number=number, ) # print("Time to test neighbors:", the_times["is_neighbor"]) the_times["add_edge"] = timeit.timeit( "graph.add_edge(*random_edge(n))", globals=globals(), number=number, ) # print("Time to add an edge:", the_times["add_edge"]) times[n][pname][str(GraphClass)] = the_times # ### Afficher ces mesures de temps de complexités # In[103]: import matplotlib.pyplot as plt import seaborn as sns sns.set(context="notebook", style="whitegrid", palette="hls", font="sans-serif", font_scale=1.1) import matplotlib as mpl mpl.rcParams['figure.figsize'] = (10, 7) mpl.rcParams['figure.dpi'] = 120 # Il faut écrire une fonction qui va extraire les données de ce `times`, et les afficher. # # - J'ai choisi d'afficher une courbe différente pour chaque valeur de $p$, et de structure de données, # - Et sur chaque courbe, il y aura $n$ le nombre de sommets du graphe en abscisse, le temps (en milli secondes) en ordonnées, et des courbes pour chaque opérations. # In[193]: def plotComplexitiesOfOperations(times): values_n = list(times.keys()) values_p = list(times[values_n[0]].keys()) values_class = list(times[values_n[0]][values_p[0]].keys()) values_opname = list(times[values_n[0]][values_p[0]][values_class[0]].keys()) for class_name in values_class: for pname in values_p: data = { n: times[n][pname][class_name] for n in values_n } fig = plt.figure() for opname in values_opname: plt.semilogy(values_n, [ 1e6 * data[n][opname] for n in values_n ], label=opname, marker='o', lw=3, ms=12, alpha=0.7, ) plt.xlabel("Values of $n$") plt.ylabel("Measured time of operations (in milli-seconds)") name = class_name.replace("