Aplicacion de Grafos en Python [NetworkX, Grafos en Python]
La teoría de grafos también llamado el grafo de las gráficas, es un campo de las matemáticas y de las ciencias de la computación, que estudia las propiedades de las gráficas estructuras que constan de dos partes el conjunto de vértices, nodos o puntos; y el conjunto de aristas, lineas o lados.
Publicado en http://wp.me/p3nJhK-21 en abril 29, 2013
Entre las aplicaciones o importancia de los grafos esta el poder ordenar de una forma eficaz mediante algoritmos el trayecto del camino mas corto entre un punto y otro pasando por uno cuantos o muchos otros vértices(puntos)
Estos algoritmos se usan en economía, en teoría de juegos para tomar decisiones, en programación(cuando programamos en función de cuanta memoria debemos reservar) ya que necesitamos tomar una decisión, en arreglo de redes cableadas e alambrillas, en telefonía para no malgastar recursos(antenas de todo tipo) entre muchas otras aplicaciones.
para mas información:
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
Una acotación o deducción de mi parte es que mientras buscaba en la red algunas aplicaciones interesantes que veremos mas adelante y python+grafos es que la mayoría de los artículos son de brasil y están en portugués, lo que me dio a entender que en brasil le están metiendo mano a la teoría de grafos y no nos extrañe que su gran impulso económico(pasar de ser un país como Venezuela subdesarrollado o en vías de desarrollo) a ser una potencia tiene que ver y mucho con la aplicación de la teoría de grafos.
NetworkX es un paquete o librería para Python para la creación, manipulación y estudio de las estructuras, dinámicas y funciones de redes complejas... Por que si adivinaste una red de personas tipo Facebook también es un grafo :D y muy muy complicado.
NetworkX esta diseñado con el fin de poder ayudar a el estudio de dinámicas sociales, biología y diseño de redes... es de fácil uso y rápido desarrollo como veremos en esta serie.
NetworkX esta basada totalmente en Python por lo que podremos modelar nuestros algoritmos de una manera mas intuitiva con resultados inmediatos, por algo Google en su buscador usa grafos.
Instalación en Debian o Ubuntu
Yo lo instale en Knoppix :D
[code]apt-get install python-networkx[/code]
Al instalar esto se instalaran
[code]python-matplotlib python-matplotlib-data[/code]
que son paquetes necesarios para las imágenes de nuestros grafos!!! Vemos un poco de practica aunque no explicare el código por el momento lo dejare para otra entrada :S
[code]root@Microknoppix:/home/knoppix# python
Python 2.7.3 (default, Jan 2 2013, 16:53:07)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
import networkx as nx
g = nx.Graph()
g.add_edge('a','b', weight=0.1)
g.add_edge('b','c', weight=1.5)
g.add_edge('a','c', weight=1.0)
g.add_edge('c','d', weight=2.2)
print nx.shortest_path (g, 'b', 'd')
['b', 'c', 'd']
print nx.shortest_path (g, 'a', 'd', weight=True)
['a', 'c', 'd']
[/code]
para los entendidos este es el algoritmo de Dijkstra’s , lo que hace es buscar el punto mas corto entre dos puntos o vértices... sin embargo este grafo no esta ponderado es solo un ejemplo podrían meter mas datos mas vértices y ver los caminos mas cortos entre un punto y otro :D Por otro lado dejare este grafo medio feo porque en realidad no hace nada pero nos servirá mas adelante para graficar y ver mejor las cosas
[code]
root@Microknoppix:/home/knoppix# python
Python 2.7.3 (default, Jan 2 2013, 16:53:07)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
import networkx as nx
import matplotlib.pyplot as plt
n = 7
G1 = nx.complete_graph(n-1)
nx.draw_circular(G1, ax=plt.axes((.3, .01+.25*2, .3, .22)))
plt.show()
[/code]
pyplot es la librería que usa NetworkX junto a python para mostrar el grafo en un png se vería así
Las opciones de >>> nx.draw_circular(G1, ax=plt.axes((.3, .01+.25*2, .3, .22))) se pueden modificar para el tamaño del grafo y su posición en la gráfica.
Que Dios les Bendiga y les Guie siempre