14/12/2019, 02:52:30 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: [Codigo] Algoritmo FR - Grafos  (Leído 845 veces)
0 Usuarios y 1 Visitante están viendo este tema.
dresuer
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 112



Ver Perfil
« : 12/04/2018, 02:34:26 am »

Hola, aplicando el algoritmo de FR así me quedó el programa.

gg.py:
Código:
#! /usr/bin/python
import math
import sys
import string
import time
import Gnuplot as gp
import random
import numpy

def iniciar_vertices(V,ancho,alto):
''' Resultado: pos['A'] = coordenadas de A'''
pos = {}
for v in V:
pos[v] = (random.random()*ancho,random.random()*alto)
print pos[v]
return pos


def fa(x,k):
return (x*x)/k

def fr(x,k):
return (k*k)/x

def cool(t):
if t > 1:
return t - 0.5
elif t > 0:
return t - 0.1
else:
return 0

def modulo_vector(x,y):
return math.sqrt((x)**2+(y)**2)

def run_layout(grafo,ancho,alto,M=250):
(V,E) = grafo
V = set(V)
area = ancho*alto
k = 0.5*math.sqrt(area/len(V))

t = 50

disp = {}
for v in V:
disp[v] = (0,0)

pos = iniciar_vertices(V,ancho,alto)

for i in range(0,M):
for v in V:
disp[v] = (0,0)
# Fuerza repulsion
for u in V:
if (u != v):
Delta = tuple(numpy.subtract(pos[v],pos[u]))
x,y = Delta
Modulo_Delta = modulo_vector(x,y)
if Modulo_Delta == 0:
return(-1)

Delta_sobre_modulo = tuple(d/Modulo_Delta for d in Delta)
aux = tuple(q*fr(Modulo_Delta,k) for q in Delta_sobre_modulo)
disp[v] = tuple(numpy.add(disp[v],aux))

# Fuerza atraccion.
for (g,h) in E:
Delta = tuple(numpy.subtract(pos[g],pos[h]))

x,y = Delta
Modulo_Delta = modulo_vector(x,y)

Delta_sobre_modulo = tuple(float(d)/float(Modulo_Delta) for d in Delta)
aux = tuple(p*fa(Modulo_Delta,k) for p in Delta_sobre_modulo)

disp[g] = tuple(numpy.subtract(disp[g],aux))
disp[h] = tuple(numpy.add(disp[h],aux))

# Limitamos desplazamiento.
for v in V:
a,b = disp[v]
displen = modulo_vector(a,b)
if displen == 0:
return(-1)
aux = tuple( (dd/(displen)*t) for dd in disp[v])
pos[v] = tuple(numpy.add(pos[v],aux))

a,b = pos[v]

pos[v] = (min(ancho/2,max(-ancho/2,a)),
   min(alto/2,max(-alto/2,b)))
print pos[v]

t = cool(t)

graficar(pos,V,E)



comando_vertice = 'set object %s circle center %s,%s size 5 fc rgb "blue" fs solid border lc rgb "blue" '
comando_arista = 'set arrow nohead from %s,%s to %s,%s filled back lw 2 lc rgb "blue"'


def graficar(pos,V,E):
g = gp.Gnuplot()
g('set terminal wxt size 1000,550')
g('set terminal wxt persist')
g('set key off')
g('set terminal wxt background "white"')
g('set title "FR"')
g('unset xtics')
g('unset ytics')
g('unset border')
g('unset key')
g('set xrange [-100:700]; set yrange [-250:350]')

# dibujamos vertices
id_vertice = 1


for v in V:
x,y = pos[v]
cmd = (comando_vertice) % (id_vertice,x,y)
#print "Comando:",cmd
g(cmd)
id_vertice += 1
# dibujamos aristas

E=[(x,y) if x>y else (y,x) for (x,y) in E]
for ar in E:
a,b = pos[ar[0]]
c,d = pos[ar[1]]
cmd = (comando_arista) % (a,b,c,d)
g(cmd)
g('plot NaN')

def lee_grafo_archivo(file_path):
count = 0
with open(file_path,'r') as f:
cantidad = int(f.readline())

Vertices = []
for i in range(0,cantidad):
elem = f.readline().strip()
Vertices.append(elem)

Aristas = []
for line in f:
elem = line.strip().split()
Aristas.append(tuple(elem))

G = (Vertices,Aristas)

print G
return G

def main():
if len(sys.argv) < 2:
print 'Uso: python gg.py <archivo>'
return

G = lee_grafo_archivo(sys.argv[1])
dibujar = run_layout(G,1000,550,250)
while dibujar == -1:
dibujar = run_layout(G,1000,550,250)


if __name__ == '__main__':
main()

Acá tienen algunos archivos de grafos para probar:

Petersen:
Código:
10
A
B
C
D
E
F
G
H
I
J
A B
B C
C D
D E
E A
A F
B G
C H
D I
E J
F H
H J
J G
G I
I F

k8:
Código:
8
A
B
C
D
E
F
G
H
A B
A C
A D
A E
A F
A G
A H
B C
B D
B E
B F
B G
B H
C D
C E
C F
C G
C H
D E
D F
D G
D H
E F
E G
E H
F G
F H
G H

Ese texto lo guardan como k8.tgf y lo ejecutan python gg.py k8.tgf

Igual todavía el codigo no está perfecto porque en un caso unos vertices toman la misma posición y al restarlos da (0,0) el modulo da 0 entonces se produce una división por cero que rompe todo, yo para que el programa siga funcionando agregué un condicional de que si pasaba eso retorne -1 y que lo vuelva a ejecutar hasta que no devuelva -1, pero no es una buena solución, si alguien me podría dar una mano en eso sería genial.

Pueden dibujar cualquier cosa para probar ya sea k4 k6, c4, c8, cualquiera, tienen que respetar ese formato solamente.

En esta linea esta el error de la division por 0:
Código:
def fr(x,k):
return (k*k)/x

Requerimientos para poder ejecutar el script:
Código:
sudo apt-get install python-pip
sudo apt-get install python-dev
sudo pip install numpy
wget http://downloads.sourceforge.net/project/gnuplot-py/Gnuplot-py/1.8/gnuplot-py-1.8.tar.gz
tar xzf gnuplot-py-1.8.tar.gz
cd gnuplot-py-1.8/
sudo python setup.py install
sudo apt-get install gnuplot-x11
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!