Introducción de Grafos Dinámicos

Crear un grafo

Para crear un grafo, instanciamos un objeto de Graph y pasamos como parámetros lo siguinte:

- sources ([int]): una lista de nodos fuentes
- targets ([int]): una lista de nodos destinos
- weights ([int]): una lista de sus respectivos pesos.
In [1]:
from graph.Graph import Graph

sources = [1, 2, 3, 0, 5, 1, 1, 3]
targets = [0, 0, 0, 5, 0, 2, 3, 1]
weights = [2, 2, 4, 1, 1, 3, 2, 2]

graph = Graph(sources, targets, weights)

graph.print_r()
Source:  [1 2 3 0 5 1 1 3]
Target:  [0 0 0 5 0 2 3 1]
Weight:  [2 2 4 1 1 3 2 2]
Vertex:  [0 1 2 3 5]

Graficar

Para graficar el grafo, la librería cuenta con una implementación de networkx. Solo falta usar el comando draw:

with_weight (boolean)[default=True][opcional]: Si muestra los pesos de cada arco (edge)
In [2]:
graph.draw(with_weight=False)

Métodos dinámicos

Los grafos dinámicos cuentan con un conjunto de métodos para modificar la estructura del propio grafo, la mayoría posee una visualización gráfica.

Insertar un Arco (Incremental Edge)

Para agregar un arco al grafo utilizamos el método dynamic_incremental_edge con los siguientes parámetros:

source (int): Nodo fuente
target (int): Nodo destino
weight (int) [opcional]: Peso del arco
In [3]:
graph.dynamic_incremental_edge(source=3, target=5)
graph.draw(with_weight=False)

Actualizar un arco (Update Edge)

Para actualizar un arco por su peso utilizamos el método vertex_update con los siguientes parámetros:

source (int): Nodo fuente del arco a actualizar
target (int): Nodo destino del arco a actualizar
weight (int) [default=1] [optional]: Peso del arco a actualizar
In [4]:
graph.vertex_update(source=3, target=0)
graph.draw()

Eliminar un arco (Remove edge)

Para eliminar un arco del grafo utilizamos el método dynamic_decreasing_edge con los siguientes parámetros:

source (int): Nodo fuente del arco a eliminar
target (int): Nodo destino del arco a eliminar
In [5]:
graph.dynamic_decreasing_edge(source=1, target=2)
graph.draw(with_weight=False)

Insertar un nodo (Incremental vertex)

Para insertar un nodo al grafo utilizamos el método dynamic_incremental_node con los siguientes parámetros:

node (int): Nodo a agregar

sources ([int]): Lista de nodos fuentes del grafo al nuevo nodo
w_sources ([int]): Pesos de los arcos de la lista de nodos fuentes

targets ([int]): Lista de nodos destinos del grado desde el nuevo nodo
w_targets ([int]): Pesos de los arcos de la lista de nodos objetivos
In [6]:
graph.print_r()
graph.dynamic_incremental_node(node=6, sources=[2, 0, 5], w_sources=[2, 4, 5], targets=[5], w_targets=[2])
print('---Incremental vertex---')
graph.print_r()
graph.draw()
Source:  [1 2 3 0 5 1 3 3]
Target:  [0 0 0 5 0 3 1 5]
Weight:  [2 2 1 1 1 2 2 1]
Vertex:  [0 1 2 3 5]
---Incremental vertex---
Source:  [1 2 3 0 5 1 3 3 2 0 5 6]
Target:  [0 0 0 5 0 3 1 5 6 6 6 5]
Weight:  [2 2 1 1 1 2 2 1 2 4 5 2]
Vertex:  [0 1 2 3 5 6]

Eliminar un nodo (Decreasing vertex)

Para elimnar un nodo al grafo utilizamos el método dynamic_decreasing_node con los siguientes parámetros:

node (int): Nodo a eliminar
In [7]:
graph.print_r()
graph.dynamic_decreasing_node(node=5)
graph.draw()
Source:  [1 2 3 0 5 1 3 3 2 0 5 6]
Target:  [0 0 0 5 0 3 1 5 6 6 6 5]
Weight:  [2 2 1 1 1 2 2 1 2 4 5 2]
Vertex:  [0 1 2 3 5 6]

Grafo aleatorio

Crear grafo aleatorio

Para crear un grafo con parámetros aleatorios usamos el médoto creategraph con los siguientes parámetros:

total_nodes (int): Número de nodos que tendrá el grafo
pro_edges (float [0 <-> 1]): Probabilidad que entre nodos exista un arco, entre uno y cero.
weights ([int]) [opcional]: Lista de los pesos para asignar aleatoriamente a los arcos. Por defecto de uno a nueve.
directed (boolean) [opcional]: Si el grafo es dirigido. Por defecto True.
In [8]:
random_graph = Graph.creategraph(total_nodes=5, pro_edges=0.85)
random_graph.print_r()
random_graph.draw()
Source:  [0. 0. 0. 1. 1. 2. 2. 3.]
Target:  [1. 2. 4. 2. 4. 3. 4. 4.]
Weight:  [2. 9. 8. 2. 1. 7. 6. 6.]
Vertex:  [0. 1. 2. 3. 4.]

Insertar un arco aleatorio (random insert edge)

Para insertar un arco aleatorio al grafo utilizamos el método dynamic_incremental_random_edge con los siguientes parámetros:

weights ([int]) [opcional]: Lista de los pesos para asignar aleatoriamente a los arcos. Por defecto de uno a nueve
In [9]:
random_graph.dynamic_incremental_random_edge()
random_graph.draw()

Eliminar un arco aleatorio (random delete edge)

Para eliminar un arco aleatorio del grafo utilizamos el método dynamic_decreasing_random_edge, sin parámetros.

In [10]:
random_graph.dynamic_decreasing_random_edge()
random_graph.draw()

Actualizar arco aleatorio (random update edge)

Para actualizar el peso de un arco aleatorio del grafo utilizamos el método vertex_update_random, sin parámetros.

In [11]:
random_graph.vertex_update_random()
random_graph.draw()

Insertar nodo aleatorio (Random insert vertex)

Para insertar un nodo aleatorio al grafo utilizamos el método dynamic_incremental_random_node con los siguientes parámetros:

num_edges (int) [opcional]: Número de arcos que tendrá el nuevo nodo. Por defecto (1)
weights ([int]) [opcional]: Lista de los pesos para asignar aleatoriamente a los arcos. Por defecto de uno a nueve
In [12]:
random_graph.dynamic_incremental_random_node(num_edges=2)
random_graph.draw()
5.0

Eliminar nodo aleatorio (random delete vertex)

Para eliminar un nodo aleatorio al grafo utilizamos el método dynamic_decreasing_random_node, no posee parámetros

In [13]:
random_graph.dynamic_decreasing_random_node()
random_graph.draw()