Grafs¶
Exemples:
Existeixen també grafs dirigits, també anomenats digrafs, en els quals les arestes estan orientades (no són simètriques, és a dir, \((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 (networkx.Graph) com dirigits (networkx.DiGraph). També multigrafs, tant dirigits com no (networkx.MultiDiGraph i networkx.Graph).
Exemples d’ús: operacions elementals
Visiteu https://networkx.org/documentation/stable/tutorial.html
>>> import networkx as nx
Grafs simètrics
---------------
>>> g = nx.Graph() # Creem un graf buit
>>> g.add_node('A') # hi afegim un vèrtex
>>> g.add_nodes_from('BCDEFGH') # hi afegim molts vèrtexs (<- iterable)
>>> g.add_edge('A', 'B') # hi afegim una aresta
>>> g.add_edges_from([('A','C'), ('B','C'), ('C','D'), ('C','E'), ('F','B'),
... ('F','E'), ('F','G'), ('G','H')]) # hi afegim moltes arestes
>>> len(g) # consultem el nombre de nodes. També g.number_of_nodes()
8
>>> g.number_of_edges() # consultem el nombre d'arestes
9
>>> g.nodes # consultem els nodes (-> iterable)
NodeView(('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'))
>>> for n in g: # recorrem els nodes; equivalent a ``for n in g.nodes:``
... print(n, end=',')
A,B,C,D,E,F,G,H,
>>> g.edges # consultem les arestes (-> iterable)
EdgeView([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'F'), ('C', 'D'), ('C', 'E'), ('E', 'F'), ('F', 'G'), ('G', 'H')])
>>> g.degree('B') # consultem el grau d'un node
3
>>> 'X' in g # consultem si el graf conté un node
False
>>> g.has_edge('E', 'F') # consultem si el graf conté una aresta
True
>>> g['C'] # consultem els veïns de C (-> iterable)
AtlasView({'A': {}, 'B': {}, 'D': {}, 'E': {}})
>>> g.remove_node('G') # esborrem un node: també existeix remove_nodes_from
>>> g.remove_edge('B', 'C') # esborrem una aresta; també existeix remove_edges_from
>>> g.edges
EdgeView([('A', 'B'), ('A', 'C'), ('B', 'F'), ('C', 'D'), ('C', 'E'), ('E', 'F')])
Arestes i vèrtexs amb atributs (etiquetes)
------------------------------------------
>>> g.add_edge('H', 'K', dist=24) # afegim una aresta amb l'atribut 'dist'
>>> g['H']['K'] # consultem una aresta
{'dist': 24}
>>> g['K']['H']['dist'] # consultem l'atribut 'dist' de l'aresta
24
>>> g['A']['B']['tipus'] = 'Autopista' # afegim l'atribut 'tipus' a l'aresta A-B
>>> g.edges(data=True) # consultem les arestes i les etiquetes (-> iterable)
EdgeDataView([('A', 'B', {'tipus': 'Autopista'}), ('A', 'C', {}), ('B', 'F', {}), ('C', 'D', {}), ('C', 'E', {}), ('E', 'F', {}), ('H', 'K', {'dist': 24})])
>>> g.edges(data='tipus') # consultem les arestes o les etiquetes `tipus`
EdgeDataView([('A', 'B', 'Autopista'), ('A', 'C', None), ('B', 'F', None), ('C', 'D', None), ('C', 'E', None), ('E', 'F', None), ('H', 'K', None)])
>>> g.add_node('X', nom='Xàtiva') # afegim un node amb l'atribut 'nom'
>>> g.nodes['X']['nom'] # consultem l'atribut 'nom' del vèrtex
'Xàtiva'
>>> g.nodes['A']['comarca'] = 'Montsià' # afegim un atribut a un vèrtex
>>> g.nodes(data=True) # consultem els vèrtexs i les etiquetes (-> iterable)
NodeDataView({'A': {'comarca': 'Montsià'}, 'B': {}, 'C': {}, 'D': {}, 'E': {}, 'F': {}, 'H': {}, 'K': {}, 'X': {'nom': 'Xàtiva'}})
Grafs dirigits
--------------
>>> g2 = nx.DiGraph() # creem un graf dirigit (=no simètric)
>>> g2.add_edges_from([[1,2], [2,1], [3,2], [3,4]])
>>> g2.edges # consultem les arestes orientades
OutEdgeView([(1, 2), (2, 1), (3, 2), (3, 4)])
>>> g2.succ[2] # consultem els successors d'un vèrtex
AtlasView({1: {}})
>>> g2.pred[2] # consultem els predecessors d'un vèrtex
AtlasView({1: {}, 3: {}})
>>> g2.in_degree(2) # consultem el grau d'entrada d'un node
2
>>> g2.out_degree(2) # consultem el grau de sortida d'un node
1
Representació gràfica
Per a dibuixar un graf/digraf amb els nodes es pot fer així. Cal tenir instal·lat el mòdul matplotlib:
>>> 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()
Operacions no elementals
Operacions de més alt nivell: degree, add_path, subgraph, …
networkx.classes.functionNodes aïllats:
networkx.algorithms.isolateComponents connexes:
networkx.algorithms.componentsCamins mínims:
networkx.algorithms.shortest_paths.genericCamins:
networkx.algorithms.simple_pathsAncestres i descendents:
ancestors(),descendants()Recorreguts en amplada i en profunditat:
networkx.algorithms.traversal.breadth_first_searchinetworkx.algorithms.traversal.depth_first_search
Multigrafs¶
Un multigraf és un graf que admet més d’una aresta entre dos nodes (networkx.MultiGraph, 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.
Exemples:
Exemples d’ús de multigrafs amb networkx
>>> import networkx as nx
>>> g = nx.MultiGraph() # Creem un multigraf buit
>>> r = g.add_edge('B','C', dist=40)
>>> r = g.add_edge('B','C', dist=30)
>>> r = g.add_edges_from([('A','B'), ('C','B'),
... ('A','C'), ('E','B')], dist=10)
>>> nx.add_path(g, 'CDBE', dist=20)
>>> g.edges(data=True)
MultiEdgeDataView([('B', 'C', {'dist': 40}), ('B', 'C', {'dist': 20}), ('B', 'C', {'dist': 10}), ('B', 'A', {'dist': 10}), ('B', 'E', {'dist': 10}), ('B', 'E', {'dist': 20}), ('B', 'D', {'dist': 20}), ('C', 'A', {'dist': 10}), ('C', 'D', {'dist': 20})])
>>> for vei in g['B']: # Recorregut dels veïns d'un node (el B)
... for i in g['B'][vei]: # Per cada índex de l'aresta
... print(vei, g['B'][vei][i]['dist'])
C 40
C 20
C 10
A 10
E 10
E 20
D 20
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.
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.
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.
Exemples de recorreguts amb networkx
>>> import networkx as nx
>>> g = nx.DiGraph() # creem el graf dirigit de l'exemple
>>> g.add_edges_from([(1,2), (1,3), (2,4), (2,5), (3,6), (11,8),
... (6,7), (3,8), (3,10), (6,8), (10,11),
... (4, 12), (7,1), (1,9), (9,11)])
>>> list(nx.bfs_edges(g, 1)) # recorregut en amplada de les arestes començant pel node 1
[(1, 2), (1, 3), (1, 9), (2, 4), (2, 5), (3, 6), (3, 8), (3, 10), (9, 11), (4, 12), (6, 7)]
>>> [1] + list(map(lambda t:t[1], nx.bfs_edges(g, 1))) # recorregut en amplada dels nodes començant pel node 1
[1, 2, 3, 9, 4, 5, 6, 8, 10, 11, 12, 7]
>>> list(nx.dfs_edges(g, 1)) # recorregut en profunditat de les arestes començant pel node 1
[(1, 2), (2, 4), (4, 12), (2, 5), (1, 3), (3, 6), (6, 7), (6, 8), (3, 10), (10, 11), (1, 9)]
>>> list(nx.dfs_preorder_nodes(g, 1)) # recorregut en profunditat dels nodes començant pel node 1
[1, 2, 4, 12, 5, 3, 6, 7, 8, 10, 11, 9]
>>> sorted(nx.descendants_at_distance(g, 1, 3)) # nodes a distància 3 del node 1
[7, 12]
>>> # Notem que els recorreguts en digrafs només segueixen l'orientació de les arestes:
>>> list(nx.bfs_edges(g, 2))
[(2, 4), (2, 5), (4, 12)]
