Python: outil de visualisation pour les graphes

Question

Guys J'ai posé cette question, mais n'a pas reçu un seul commentaire ou répondre

Je veux simuler un algorithme de recherche sur un graphique de loi de puissance et que vous voulez voir visuellement le mouvement de l'algorithme de un noeud à l'autre sur le graphique. Comment je fais ça?

Answer 1

Vous pouvez adapter ce code complètement différent, je suis d'avoir écrit pour Find the most points enclosed in a fixed size circle :)

Le bit utile est:

Il utilise le système de fenêtrage de base Tkinter pour créer un cadre contenant une toile; il fait ensuite un algorithme, appelant son propre 'draw()' pour changer la toile, puis 'update()' pour redessiner l'écran, avec un délai. De voir à quel point il est facile de tracer dans tkinter, vous pouvez peut-être passer à des versions interactives, etc.

import random, math, time 
from Tkinter import * # our UI 

def sqr(x): 
    return x*x 

class Point: 
    def __init__(self,x,y): 
     self.x = float(x) 
     self.y = float(y) 
     self.left = 0 
     self.right = [] 
    def __repr__(self): 
     return "("+str(self.x)+","+str(self.y)+")" 
    def distance(self,other): 
     return math.sqrt(sqr(self.x-other.x)+sqr(self.y-other.y)) 

def equidist(left,right,dist): 
    u = (right.x-left.x) 
    v = (right.y-left.y) 
    if 0 != u: 
     r = math.sqrt(sqr(dist)-((sqr(u)+sqr(v))/4.)) 
     theta = math.atan(v/u) 
     x = left.x+(u/2)-(r*math.sin(theta)) 
     if x < left.x: 
      x = left.x+(u/2)+(r*math.sin(theta)) 
      y = left.y+(v/2)-(r*math.cos(theta)) 
     else: 
      y = left.y+(v/2)+(r*math.cos(theta)) 
    else: 
     theta = math.asin(v/(2*dist)) 
     x = left.x-(dist*math.cos(theta)) 
     y = left.y + (v/2) 
    return Point(x,y) 

class Vis: 
    def __init__(self): 
     self.frame = Frame(root) 
     self.canvas = Canvas(self.frame,bg="white",width=width,height=height) 
     self.canvas.pack() 
     self.frame.pack() 
     self.run() 
    def run(self): 
     self.count_calc0 = 0 
     self.count_calc1 = 0 
     self.count_calc2 = 0 
     self.count_calc3 = 0 
     self.count_calc4 = 0 
     self.count_calc5 = 0 
     self.prev_x = 0 
     self.best = -1 
     self.best_centre = [] 
     for self.sweep in xrange(0,len(points)): 
      self.count_calc0 += 1 
      if len(points[self.sweep].right) <= self.best: 
       break 
      self.calc(points[self.sweep]) 
     self.sweep = len(points) # so that draw() stops highlighting it 
     print "BEST",self.best+1, self.best_centre # count left-most point too 
     print "counts",self.count_calc0, self.count_calc1,self.count_calc2,self.count_calc3,self.count_calc4,self.count_calc5 
     self.draw() 
    def calc(self,p): 
     for self.right in p.right: 
      self.count_calc1 += 1 
      if (self.right.left + len(self.right.right)) < self.best: 
       # this can never help us 
       continue 
      self.count_calc2 += 1 
      self.centre = equidist(p,self.right,radius) 
      assert abs(self.centre.distance(p)-self.centre.distance(self.right)) < 1 
      count = 0 
      for p2 in p.right: 
       self.count_calc3 += 1 
       if self.centre.distance(p2) <= radius: 
        count += 1 
      if self.best < count: 
       self.count_calc4 += 4 
       self.best = count 
       self.best_centre = [self.centre] 
      elif self.best == count: 
       self.count_calc5 += 5 
       self.best_centre.append(self.centre) 
      self.draw() 
      self.frame.update() 
      time.sleep(0.1) 
    def draw(self): 
     self.canvas.delete(ALL) 
     # draw best circle 
     for best in self.best_centre: 
      self.canvas.create_oval(best.x-radius,best.y-radius,\ 
       best.x+radius+1,best.y+radius+1,fill="red",\ 
       outline="red") 
     # draw current circle 
     if self.sweep < len(points): 
      self.canvas.create_oval(self.centre.x-radius,self.centre.y-radius,\ 
       self.centre.x+radius+1,self.centre.y+radius+1,fill="pink",\ 
       outline="pink") 
     # draw all the connections 
     for p in points: 
      for p2 in p.right: 
       self.canvas.create_line(p.x,p.y,p2.x,p2.y,fill="lightGray") 
     # plot visited points 
     for i in xrange(0,self.sweep): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="blue") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="blue") 
     # plot current point 
     if self.sweep < len(points): 
      p = points[self.sweep] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="red") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="red") 
      self.canvas.create_line(p.x,p.y,self.right.x,self.right.y,fill="red") 
      self.canvas.create_line(p.x,p.y,self.centre.x,self.centre.y,fill="cyan") 
      self.canvas.create_line(self.right.x,self.right.y,self.centre.x,self.centre.y,fill="cyan") 
     # plot unvisited points 
     for i in xrange(self.sweep+1,len(points)): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="green") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="green") 

radius = 60 
diameter = radius*2 
width = 800 
height = 600 

points = [] 

# make some points 
for i in xrange(0,100): 
    points.append(Point(random.randrange(width),random.randrange(height))) 

# sort points for find-the-right sweep 
points.sort(lambda a, b: int(a.x)-int(b.x)) 

# work out those points to the right of each point 
for i in xrange(0,len(points)): 
    p = points[i] 
    for j in xrange(i+1,len(points)): 
     p2 = points[j] 
     if p2.x > (p.x+diameter): 
      break 
     if (abs(p.y-p2.y) <= diameter) and \ 
      p.distance(p2) < diameter: 
      p.right.append(p2) 
      p2.left += 1 

# sort points in potential order for sweep, point with most right first 
points.sort(lambda a, b: len(b.right)-len(a.right)) 

# debug 
for p in points: 
    print p, p.left, p.right 

# show it 
root = Tk() 
vis = Vis() 
root.mainloop() 

Answer 2

Vous pouvez utiliser matplotlib pour cela.

Voici un exemple simlple d'un maillage avec un point mis en évidence animé:

import matplotlib.pyplot as plt 
import time 

x_size = 4 
y_size = 3 

# create the points and edges of the mesh 
points = [(x,y) for y in range(y_size) for x in range(x_size)] 
vert_edges = [((i_y*x_size)+i_x,(i_y*x_size)+i_x+1) 
       for i_x in range(x_size-1) for i_y in range(y_size)] 
horz_edges = [((i_y*x_size)+i_x,((i_y+1)*x_size)+i_x) 
       for i_x in range(x_size) for i_y in range(y_size-1)] 
edges = vert_edges + horz_edges 

# plot all the points and edges 
lines = [] 
for edge in edges: 
    x_coords, y_coords = zip(points[edge[0]], points[edge[1]]) 
    lines.extend((x_coords, y_coords, 'g')) 
plt.plot(linewidth=1, *lines) 
x, y = zip(*points) 
plt.plot(x, y, 'o') 

# create the highlighted point 
point_plot = plt.plot([0], [0], 'ro')[0] 

# turn on interactive plotting mode 
plt.ion() 
plt.ylim(-1, y_size) 
plt.xlim(-1, x_size) 

# animate the highlighted point 
for i_point in range(1, len(x)): 
    point_plot.set_xdata([x[i_point]]) 
    point_plot.set_ydata([y[i_point]]) 
    plt.draw() 
    time.sleep(0.5) 

plt.show()