Prim's Algorithm In Python - The Network

Starting with a new Python Tkinter project we need to add a button labelled "Generate Network" and a Canvas object. A Tkinter Canvas object is often a good thing to use when you need to draw using x,y co-ordinates, but there are other ways of doing the same job.

Moving to the code. We need a list to hold the co-ordinates of the points:

Pos=[]

size is a constant that sets the size of the network in number of vertices.

size=8

The array to hold the network data can be defined as

Network=[]

We are going to have to set the structure of this two dimensional list of lists when we store data in it.

We can now write a method that fills both Pos and Network with random values and calls another function to draw the network:

def setnet(canvas):  
   global Network
   global Pos    
   Pos=[0 for j in range(size)]
   Network=[[0 for j in range(size)] 
                             for i in range(size)]
   maxlength =math.floor( min(canvas.winfo_width(),
                          canvas.winfo_height()) * 0.9)
   minlength = math.floor(maxlength / size)
   for i in range(size):
       p=Point()
       p.X=random.randint(minlength,maxlength)
       p.Y=random.randint(minlength,maxlength)
       Pos[i]=p
       for j in range(i+1):
           Network[i][j]=distance(Pos[i],Pos[j])
           Network[j][i]=Network[i][j]
   showNetwork(canvas, Network)

Network and Pos are  global variables but they still have to be initialized and we do this using list comprehensions. The points are generated randomly with co-ordinates between minlength and maxlength which are derived from the size of the Canvas object.

Notice that the distance array is made to be symmetric and the diagonal is also set to zero. The distance between points is computed using an additional function.

The distance function is simply the usual Euclidean formula:

def distance(a, b):
   return math.sqrt((a.X - b.X) **2 + (a.Y - b.Y) **2)

After generating the network it would be nice to view it. A drawing routine is quite easy – as long as you don't worry too much about efficiency. We can simply use Line objects to draw lines on the Canvas.

First we clear the Canvas of any child nodes it may already contain:

def showNetwork(canvas,Network):
    canvas.delete("all")

Next we draw a new Line for each pair of points that have a large enough distance between them:

for i in range(size):
        p1=Pos[i]
        for j in range(i):            
            if Network[i][j]>1:
                p2=Pos[j] 
                canvas.create_line(p1.X,p1.Y,p2.X,p2.Y)

Next we can plot suitable marker shapes at the position of each node: 

    for i in range(size):
       p1=Pos[i]
       canvas.create_rectangle(p1.X-5,p1.Y-5,
                               p1.X+5,p1.Y+5,
                  outline ="black",fill ="red",width = 2)

To try this our with need to place a button on the canvas in the main program:

top = tkinter.Tk()

C = tkinter.Canvas(top, bg="blue", 
                          height=height, width=width)

button=tkinter.Button(top,text="Generate Network",
                              command=lambda:setnet(C))
button.place(x=10,y=height-40)
C.pack()

You can now try the program out and see if it really does generate reasonable graphs. It should! You can size the canvas control to make best use of the space and the graph will adjust itself to fill it, more or less. It is fun just to see the range of graphs that can be produced.

A typical random graph with eight vertices

<ASIN:1565924533>

<ASIN:1584883960> 

<ASIN:1584883960>

<ASIN:0201000237>