----- Grafs ----- .. topic:: Definició de graf Estructura de dades formada per un conjunt de **vèrtexs** (o nodes) :math:`V` juntament amb un conjunt d\'**arestes** (o *arcs*) :math:`E`, les quals són parelles de dos elements de :math:`V`. .. figure:: graf1.svg :align: center :height: 240 .. rubric:: Exemples: | - Xarxa de carreteres d'un territori | - Relació d'amistat entre persones | - Poliedre | - Sistema fluvial (rius amb afluents) | - Mol·lècules * Existeixen també grafs **dirigits**, també anomenats digrafs, en els quals les arestes estan **orientades** (no són **simètriques**, és a dir, :math:`(a,b) \neq (b,a)`). * De vegades les arestes d'un graf tenen informació associada (**etiquetes** o **atributs**): distància entre ciutats, nivell d'amistat, etc. També pot ser que els nodes tinguin etiquetes. Glossari -------- * **Vèrtexs**, també anomenats **nodes**. * **Arestes**, també anomenades **arcs**. Poden ser **orientades** o no. * **Graf no dirigit** (o simètric) / **graf dirigit** (digraf, no simètric). * **Veïns** d'un vèrtex `v`: altres vèrtexs que estan units amb una aresta amb `v`. Així, es diu que dos vèrtex són veïns (o adjacents o incidents) si i només si els uneix una aresta. En grafs dirigits, es distingeix entre **predecessors** d'un vèrtex (=veïns que tenen una aresta que arriba al node) i **successors** d'un vèrtex (=veïns als quals arriba una aresta des d'un node). * **Grau** d'un vèrtex: Nombre de veïns del vèrtex. En grafs dirigits, es distingeix el **grau d'entrada** (*in-degree*) del **grau de sortida** (*out-degree*). * **Camí**: Seqüència de vèrtexs tal que cada dos vèrtexs consecutius de la sequència són veïns en el graf. **Camí simple**: camí que no passa dues vegades pel mateix node. * **Cicle** (o bucle): Camí que comença i acaba en el mateix vèrtex. * En un graf no dirigit `G`, dos vèrtexs `u` i `v` s'anomenen **connexos** si `G` conté un camí des de `u` fins a `v`. * **Component connexa** d'un graf `G`: subgraf (o conjunt de nodes) format per tots els nodes que són connexos en `G` amb un node donat. Operacions dels grafs --------------------- **Operacions elementals**, a vegades anomenades *operacions d'edició* sobre grafs, que creen un graf nou des de l'original per un canvi simple, local: * Crear un graf buit * Afegir un node al graf * Afegir una aresta al graf * Treure un node del graf * Treure una aresta del graf * Consultar els nodes d'un graf * Consultar les arestes d'un graf * Consultar els veïns d'un node **Operacions no elementals** (de més alt nivell): * Obtenir les components connexes d'un graf * Donats dos nodes, saber si existeix un camí entre ells * Donats dos nodes, obtenir el camí de longitud mínima que els uneix (si existeix) * Fusionar dos grafs * Obtenir un subgraf * etc Biblioteca networkx ------------------- Biblioteca de Python, molt completa, per a treballar amb grafs, tant grafs no dirigits (:py:class:`networkx.Graph`) com dirigits (:py:class:`networkx.DiGraph`). També multigrafs, tant dirigits com no (:py:class:`networkx.MultiDiGraph` i :py:class:`networkx.Graph`). .. rubric:: Exemples d'ús: operacions elementals Visiteu https://networkx.org/documentation/stable/tutorial.html .. literalinclude:: graph-nx.txt :language: pycon .. rubric:: Representació gràfica Per a dibuixar un graf/digraf amb els nodes es pot fer així. Cal tenir instal·lat el mòdul :py:mod:`matplotlib`: .. code:: python >>> import networkx as nx >>> import matplotlib.pyplot as plt >>> g = nx.tetrahedral_graph() # creem un graf qualsevol >>> nx.draw(g, with_labels=True) >>> plt.show() .. rubric:: Operacions no elementals * Operacions de més alt nivell: degree, add_path, subgraph, ... :py:mod:`networkx.classes.function` * Nodes aïllats: :py:mod:`networkx.algorithms.isolate` * Components connexes: :py:mod:`networkx.algorithms.components` * Camins mínims: :py:mod:`networkx.algorithms.shortest_paths.generic` * Camins: :py:mod:`networkx.algorithms.simple_paths` * Ancestres i descendents: :py:func:`~networkx.algorithms.dag.ancestors`, :py:func:`~networkx.algorithms.dag.descendants` * Recorreguts en amplada i en profunditat: :py:mod:`networkx.algorithms.traversal.breadth_first_search` i :py:mod:`networkx.algorithms.traversal.depth_first_search` Multigrafs ---------- Un **multigraf** és un graf que admet més d'una aresta entre dos nodes (:py:class:`networkx.MultiGraph`, :py:class:`networkx.MultiDiGraph`). Dues arestes entre dos mateixos nodes s'anomenen **arestes paral·leles**. La forma d'accedir a les arestes canvia, ja que cal iterar per totes les arestes paral·leles. Sovint, les diferents arestes paral·leles tenen assignada informació diferent. .. figure:: multigraf1.svg :align: center :height: 200 .. rubric:: Exemples: | - Xarxa de carreteres de diferents tipus d'un territori | - Mails enviats entre persones | - Vols diaris entre aeroports | - Préstecs monetaris .. rubric:: Exemples d'ús de multigrafs amb networkx .. literalinclude:: multigraph-nx.txt :language: pycon Recorreguts en amplada i en profunditat d'un graf ------------------------------------------------- Serveixen per recórrer els nodes o arestes d'una component connexa d'un graf, o bé per a fer-hi una cerca, partint d'un node inicial. Ambdós es basen en recórrer els veïns, recursivament, però es diferencien en la manera com ho fan. .. rubric:: Recorregut en amplada o BFS (*Breath First Search*) * Partint d'un node, el visita; després, visita els seus veïns no visitats; després, els veïns dels veïns no visitats; etc. .. rubric:: Recorregut en profunditat o DFS (*Depth Fisrt Search*) * Per fer un recorregut en profunditat partint d'un node inicial, cal visitar-lo, triar un veí no visitat i fer-ne un recorregut en profunditat. Quan no queden més veïns no visitats d'un node, es tira enrere en el camí recorregut buscant d'altres veïns no visitats fins que no en queda cap. .. rubric:: Exemples de recorreguts amb networkx .. figure:: digraf1.svg :align: center :height: 260 .. literalinclude:: dfs-bfs-nx.txt :language: pycon