GML, Lenguaje de Marcado para Grafos!!! NetworkX+Python III


gggr

Saludos, a la hora de escribir esta entrada me encontraba pensando en si escribirlo o no ya que buscando y buscando información y luego leyendo y leyendo información para hacer algo como un tutorial en español un poco mas sencillo de entender de lo normal y partiendo de lo básico para cuando se entre en materia de verdad no se sientan esos vacíos que normalmente sentimos al no entender algo debido a que nuestra base es algo floja, me di cuenta que este mundillo es muy divertido pero bastante complejo por lo que vi que no parecía buena idea ya que habían muchos ejemplos interesantes por ejemplo en http://stackoverflow.com pero al final mas bien estos ejemplos me impulsaron a escribir ya que no vi nada parecido a lo que yo quiero hacer y este Blog lo uso también como notas para la wifi de mis proyectos!!!

Que quiero lograr con estas entregas! Sondear la aplicación NetworkX para ver sus ventajas y limitaciones, incorporar otras librerías de python a NetworkX como es el caso de matploiit que visualizar el grafo agregándole colores y una vista interesante o Pylab que para nuestro propósito hace básicamente lo mismo, también enlazar Numpy a el programa para partir de una matriz dinámica de acceso o adyacencia, para terminar con grafos en nuestras vidas y ver una serie de entradas como la anterior donde les hable de sitios de interés en mi comunidad, bien podremos tomar un mapa y visualizar muchos datos que si no es con un grafo de precisión nunca lo haríamos….

Ya se que parece como si trato de reinventar la rueda, pero bueno yo creo que desde que existe la rueda no hay necesidad de ejecutar trabajos tan fuertes, pero ahí quienes no confían en la tecnología y continúan haciendo sus cuentas a mano, claro que si usted no sabe sumar aprenda y no use la calculadora :D, aquí trato de recopilar información para ver si a alguien algún día le sirve o mi mismo :D, mas todo lo hago con la idea de aplicarlo y vaya que se me ocurren muchas ideas de donde ampliarlo, que estoy tomando otro rumbo en el blog les aseguro que no el Blog es de Seguridad Informática y esta serie de grafos tendrá un final feliz hablando de Seguridad Informática :D, Disculpa que me extienda pero me gusta dejar las cosas claras!!!

Ahora si GML

El formato de ficheros de texto GML se utiliza para guardar en disco un grafo existente en memoria, basándose en su matriz de incidencia. Es fácilmente interpretable por un ser humano que conozca dicho formato. La ventaja es que esta formado por etiquetas y es fácilmente exportable!!!

Como usar GML en un grafo:

Ya que el lenguaje GML esta orientado a grafos le encontraremos mucha utilidad a la hora de usar un mismo objeto en otros grafos o simplemente para dividir el trajo y poder ver con mas claridad el código de la programación del grafo y de los Vértices y Aristas que lo forman!! de una manera resumida el archivo GML se llama cuando se crea el grafo asi:

G = nx.read_gml('archivo.gml')

Si nos fijamos G es el grafo y sus partes las lee NetworkX desde el archivo.gml, para trabajar con grafos hay que tomar siempre en cuenta las comillas mas que cualquier otra cosa :S

Básicamente el archivo GML esta formado por

graph

[

atributos del grafo si es dirigido o no, si es plano entre otros

vértices llamados nodos en ingles nodes

[ atributos del nodo, como id y label o etiqueta]

Aristas llamadas hojas en ingles edges

[ atributos de la arista o conexiones, como por ejemplo de donde sale origen o source, destino o target y otras etiquetas como el peso y la capacidad que es la que usaremos, hay muchas mas :S ]

]

Es importante saber que los nombres van en ingles por que es así como están declarados en la librería el no usarlos en un determinado caso puede causar problemas, en el caso de de los atributos de las hojas peso y capacidad se puede usar en realidad cualquier etiqueta en los casos que vamos a usar pero no en otros!!!

Ya que básicamente ya sabemos para qe sirve como se usa y cuales son sus ventajas veamos un ejemplo de GML y luego lo veremos funcionando en grafo sencillo….

graph

[directed 1

node [ id 1

label "C" ]

node [ id 2

label "CA" ]

node [ id 3

label "Br" ]

node [ id 4

label "BA"

]

edge [ source 3

target 4

capacidad 10

peso 12

]

edge [ source 2

target 4

Peso 20

CAP 11

]

edge [ source 1

target 4

P 15

C 12

]

]

En este ejemplo notamos que el grafo es dirigido lo que nos indica que contiene flechas del origen de un vértice a su destino, cada nodo o node tiene su etiqueta esto es muy funcional a la hora de tener grafos muy grandes y querer hacer algo con un vértice en particular, si seguimos bajando en el código vemos que nos encontramos con las conexiones o edges y tenemos un punto de origen → source y un punto de llegada → target, también observamos que el escritor se ha equivocado y coloco etiquetas raras como peso , capacidad, CAP entre otras y bueno no habíamos quedado que eran en ingles para nuestros fines la etiqueta que usemos no importa solo importara que tenga 2 items por ejemplo C 12….

Ahora nos preguntamos en el camino si he creado esta especie de tuplax o diccionario en el grafo, si quiero agregar enlaces o nodos tendré que modificar el archivo y solo asi conseguiré agregarlas, la respuesta es no, si quieres agregar nodos o edges siéntase libre de agregarla directamente luego de declarar el grafo como si fuera un grafo desde 0 😀

Aquí el código del grafo:

#!/usr/local/bin/python

#

# -*- coding: latin-1 -*-

import os, sys

#Grafo ponderado con GML

# Importamos las librerías, ojo trabajamos con pylab por que mas adelanta sera de

# mas provecho

import networkx as nx

import pylab

#creamos el grafo y leemos de una ves el archivo gml,

#ojo debes crear este archivo en la misma carpeta

G = nx.read_gml('ejemp1.gml',relabel=True)

#Agregamos mas conexiones

G.add_edge("CA", "C",calle="AvBolivar")

G.add_edge("C", "Br",Peso=18, Capacidad=15)

#Hacemos un tipo de alias para que se vea mas cómodo 😀

pos=nx.spring_layout(G)

# Cargamos el grafo con todos los periquitos

# versión 1

pylab.figure(1)

nx.draw(G,pos)

nx.draw_networkx_nodes(G,pos,node_size=2200,node_shape='o',node_color='orange')

nx.draw_networkx_edges(G,pos, width=2, font_color="b")

nx.draw_networkx_edge_labels(G,pos)

# ver el grafo llamado figure1

pylab.show()

Si nos fijamos hay comandos o cadenas nuevas de llamadas a la librería que no explicare si no hasta la otra entrada que es muy pronto, fijate en G.add_edge que es donde se agrego una conexión que no existía y quedan cosas en ell aire para la próxima que haremos varias vistas de este grafo y aprenderemos algunos atributos, ojo esta es la manera informal de hacerlo mas adelante veremos otras maneras quizá mas cómodas !!!

Anuncios

Un pensamiento en “GML, Lenguaje de Marcado para Grafos!!! NetworkX+Python III

  1. Pingback: Python y Grafos en la Vida Real | La Shell del Bit Pegajoso

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s