Mar 15

HOW TO : fix guake terminal position on multi-monitor

HOW TO : fix guake terminal position on multi-monitor

Hello everyone ! Today I want to talk about guake terminal , it is a great on linux , because it s so handy.

The only problem with that is if you get multiple monitor it starts to freak out so there is a bit of fixing to do!

Since I run on a 3 monitor setup I got this problem right away and I was quite bothered from it.

I started googling (of course!) and run into this guy post :

http://brightbyte.de/page/Guake_on_the_right_screen

This guy modified slightly the .py of guake which you can actually find in  /usr/lib/guake/guake.py

BEWARE : This fix works for sure on Ubuntu 12.04 I did not try it on later version , I know that guake is not located in the same directory.

Now following the direction in that post kinda gets the job done , on my case I got guake on the right screen but I want it to have it in the middle screen, I got a laptop in the middle and

one monitor left one monitor right.
What I did was playing with this line :

monitor = screen.get_n_monitors() – 2

By default was -1 , I first tried  to remove the -1 and was on the left , so I tried -2 and got the job done , so based on the amount of

monitors you got your fix might be different.
I also changed  the width = 80 to width = 100  because I like it full screen.

Here how it looks :

temp

That’s it  folks!

Mar 02

TUTORIAL FOR ANIMATORS: add extra deformation to a rig

TUTORIAL FOR ANIMATORS: add extra deformation to a rig

extraMod

Hello everyone since lately I have been asked from  many animators to add some extra deformations on top of their

rigs I decided to make a video tutorial out of it in order to help other fellows animators out there to do so!

Here is the video tutorial :

How to modify a maya rig to add extra deformation : FOR ANIMATORS from Marco Giordano on Vimeo.

If you like it please subscribe to the channel and share the video around

Cheers

M.

Jan 31

IMAGE PROCESSING : PYCUDA

IMAGE PROCESSING : PYCUDA

Hello everyone today we are talking about pycuda , I will tell you my experience and will show you some tests! Let s jump into it!

Everything started a couple of weeks ago with the start of an image processing course on Coursera.com , I actually decided to just had a quick look around on the course rather than really follow it, but it is really interesting

so I am taking the course in order to get the certificate. I hope I can manage it with the other 3 courses I am taking , but so far looks good.

The first week we just did some theory of image processing so I decided to have a quick look and mess around , you can actually read what I did in my previous post here.

It was quite a straight forward task , but the computation was talking like 5-6 seconds for a 1440×900 picture, so I decided to try PyCuda and doing the processing on my GPU.

It was not too easy to make Pycuda up and running but with some googling I got it done , I will actually make a post about that in the near future.

Pycuda is deeply boundwith Numpy , in order to send stuff on the GPU you can create GPU data like gpu_array and so on or create Numpy data that have straight conversion to C data.

That was the source of all my problems and frustration . It took me a while to figure out how the data was moved to the GPU and back and also understand the way Numpy handles

the arrays /matrices.

In the way I am used to work with matrices , I would have loved to parse the image by going left to right and top to bottom (row major style) , instead Numpy was converting straight from a PIL

image object to a column major matrix, which is ok , I am just not so used to, when you copy the array on the gpu memory you don’t get the same matrix shape.

I was using a 3 dimensional matrix on the host , something like matrixImage[column][row][rgb], instead  on the gpu I got a matrixImage[column*row*rgb] , which is a 1D matrix, took me a while to figure

out that actually , luckily I found a guy explaining it in a random stackoverflow post!

Once all those small technicalities were settled I could finally work on the kernel which was uber simple for a black and withe effect.

Here is the code I used , in order to make it run you need to have :

- pillow , or PIL

- numpy

- Pycuda (and its dependencies

CODE

import PIL
from PIL import Image
import time

import pycuda.driver as cuda
import pycuda.autoinit
from pycuda.compiler import SourceModule
import numpy

def blackWhite(inPath , outPath , mode = "luminosity",log = 0):

    if log == 1 :
        print ("----------> SERIAL CONVERSION")
    totalT0 = time.time()

    im = Image.open(inPath)
    px = numpy.array(im)

    getDataT1 = time.time()

    print ("-----> Opening path :" , inPath)

    processT0 =  time.time()
    for x in range(im.size[1]):
        for y in range(im.size[0]):

            r = px[x][y][0]
            g = px[x][y][1]
            b = px[x][y][2]
            if mode == "luminosity" :
                val =  int(0.21 *float(r)  + 0.71*float(g)  + 0.07 * float(b))

            else :
                val = int((r +g + b) /3)

            px[x][y][0] = val
            px[x][y][1] = val
            px[x][y][2] = val

    processT1= time.time()
    #px = numpy.array(im.getdata())
    im = Image.fromarray(px)
    im.save(outPath)

    print ("-----> Saving path :" , outPath)
    totalT1 = time.time()

    if log == 1 :
        print ("Image size : ",im.size)
        print ("get and convert Image data  : " ,getDataT1-totalT0 )
        print ("Processing data : " , processT1 - processT0 )
        print ("Save image time : " , totalT1-processT1)
        print ("total  Execution time : " ,totalT1-totalT0 )
        print ("\n")

def CudablackWhite(inPath , outPath , mode = "luminosity" , log = 0):

    if log == 1 :
        print ("----------> CUDA CONVERSION")

    totalT0 = time.time()

    im = Image.open(inPath)
    px = numpy.array(im)
    px = px.astype(numpy.float32)

    getAndConvertT1 = time.time()

    allocT0 = time.time()
    d_px = cuda.mem_alloc(px.nbytes)
    cuda.memcpy_htod(d_px, px)

    allocT1 = time.time()

    #Kernel declaration
    kernelT0 = time.time()

    #Kernel grid and block size
    BLOCK_SIZE = 1024
    block = (1024,1,1)
    checkSize = numpy.int32(im.size[0]*im.size[1])
    grid = (int(im.size[0]*im.size[1]/BLOCK_SIZE)+1,1,1)

    #Kernel text
    kernel = """

    __global__ void bw( float *inIm, int check ){

        int idx = (threadIdx.x ) + blockDim.x * blockIdx.x ;

        if(idx *3 < check*3)
        {
        int val = 0.21 *inIm[idx*3] + 0.71*inIm[idx*3+1] + 0.07 * inIm[idx*3+2];

        inIm[idx*3]= val;
        inIm[idx*3+1]= val;
        inIm[idx*3+2]= val;
        }
    }
    """

    #Compile and get kernel function
    mod = SourceModule(kernel)
    func = mod.get_function("bw")
    func(d_px,checkSize, block=block,grid = grid)

    kernelT1 = time.time()

    #Get back data from gpu
    backDataT0 = time.time()

    bwPx = numpy.empty_like(px)
    cuda.memcpy_dtoh(bwPx, d_px)
    bwPx = (numpy.uint8(bwPx))

    backDataT1 = time.time()

    #Save image
    storeImageT0 = time.time()
    pil_im = Image.fromarray(bwPx,mode ="RGB")

    pil_im.save(outPath)
    print ("-----> Saving path :" , outPath)

    totalT1 = time.time()

    getAndConvertTime = getAndConvertT1 - totalT0
    allocTime = allocT1 - allocT0
    kernelTime = kernelT1 - kernelT0
    backDataTime = backDataT1 - backDataT0
    storeImageTime =totalT1 - storeImageT0
    totalTime = totalT1-totalT0

    if log == 1 :
        print ("Image size : ",im.size)
        print ("get and convert Image data to gpu ready : " ,getAndConvertTime )
        print ("allocate mem to gpu: " , allocTime )
        print ("Kernel execution time : " , kernelTime)
        print ("Get data from gpu and convert : " , backDataTime)
        print ("Save image time : " , storeImageTime)
        print ("total  Execution time : " ,totalTime )
        print ("\n")

As you can see there is not too much stuff going on, but I know you guys want to see some benchmarsk :D and I am not going to disappoint you!

Before starting here is a couple of stats on my hardware

CPU :

i7 4900MQ  full specks here : http://ark.intel.com/products/75131

GPU :

NVidia GTX 780 M  : full specs here

1K IMAGE

I started by working on a 1K images , here down you can see the source , the serial result and the cuda result , for full image click on it.

image1K

image1KBW

image1KBWCuda

Here is some nice debug prints outline the performance :

LOG :

----------> SERIAL CONVERSION
-----> Opening path : C:/Users/Marco/Desktop/jessTest.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestLuminosity.jpg
Image size : (1440, 900)
get and convert Image data : 0.04000210762023926
Processing data : 4.67326807975769
Save image time : 0.03500199317932129
total Execution time : 4.748272180557251

----------> CUDA CONVERSION
-----> Saving path : C:/Users/Marco/Desktop/jessTestLuminosityCuda.jpg
Image size : (1440, 900)
get and convert Image data to gpu ready : 0.042001962661743164
allocate mem to gpu: 0.006000041961669922
Kernel execution time : 0.04200291633605957
Get data from gpu and convert : 0.010999917984008789
Save image time : 0.03200197219848633
total Execution time : 0.13300681114196777

OOOOOH YEAAAH that s the good stuff :D a nice ~40X performance speed up , that s quite impressive considering that the computing part of the black and white filter is so small that is not really
taking full advantage of the GPU.

3K IMAGE image3K
image3KBWimage3KBWCuda

LOG :

----------> SERIAL CONVERSION
-----> Opening path : C:/Users/Marco/Desktop/image3K.jpg
-----> Saving path : C:/Users/Marco/Desktop/image3KBW.jpg
Image size : (2494, 1663)
get and convert Image data : 0.07900404930114746
Processing data : 14.747843980789185
Save image time : 0.10500597953796387
total Execution time : 14.931854009628296

----------> CUDA CONVERSION
-----> Saving path : C:/Users/Marco/Desktop/image3KBWCuda.jpg
Image size : (2494, 1663)
get and convert Image data to gpu ready : 0.09000515937805176
allocate mem to gpu: 0.014000892639160156
Kernel execution time : 0.03500199317932129
Get data from gpu and convert : 0.03200197219848633
Save image time : 0.10600614547729492
total Execution time : 0.27701616287231445

I am gonna shoot out the rest of the test and then we can discuss about it :D

4K IMAGE
Remember the order of the pictures is : source , serial , cuda.

Harry Potter and the Deathly Hallows Part 1
image4KBW
image4KBWCuda

LOG


----------> SERIAL CONVERSION
-----> Opening path : C:/Users/Marco/Desktop/image4K.jpg
-----> Saving path : C:/Users/Marco/Desktop/image4KBW.jpg
Image size : (4096, 2440)
get and convert Image data : 0.17701005935668945
Processing data : 35.46102809906006
Save image time : 0.2350139617919922
total Execution time : 35.87305212020874

----------> CUDA CONVERSION
-----> Saving path : C:/Users/Marco/Desktop/image4KBWCuda.jpg
Image size : (4096, 2440)
get and convert Image data to gpu ready : 0.21601200103759766
allocate mem to gpu: 0.029001951217651367
Kernel execution time : 0.03500223159790039
Get data from gpu and convert : 0.07800483703613281
Save image time : 0.23401308059692383
total Execution time : 0.592034101486206

Lets move forward!
5K IMAGE

image5Kimage5KBWimage5KBWCuda

LOG :

</pre>
----------> SERIAL CONVERSION
-----> Opening path : C:/Users/Marco/Desktop/image5K.jpg
-----> Saving path : C:/Users/Marco/Desktop/image5KBW.jpg
Image size : (5184, 3456)
get and convert Image data : 0.27501511573791504
Processing data : 67.43985795974731
Save image time : 0.39202213287353516
total Execution time : 68.10689520835876
----------> CUDA CONVERSION
-----> Saving path : C:/Users/Marco/Desktop/image5KBWCuda.jpg
Image size : (5184, 3456)
get and convert Image data to gpu ready : 0.33801889419555664
allocate mem to gpu: 0.0760049819946289
Kernel execution time : 0.22401213645935059
Get data from gpu and convert : 0.18601083755493164
Save image time : 0.40102314949035645
total Execution time : 1.2250699996948242
<pre>

9K IMAGE
Hell yeah :D I found a 9K image and I am not afraid to use it ! The original png I downloaded was  ~160MB!
The actual JPG i used in the code was 50 mb and the site doesn’t let me upload that size , so I had to compress it to a 70% but the processed Image is coming out
from the HD version aaand I actually lost the one converted serially so I will just add the cuda one .

image9Kcompimage9KBWCuda

And here the LOG for the fat 9k resolution.

</pre>
----------> SERIAL CONVERSION
-----> Opening path : C:/Users/Marco/Desktop/image9K.png
-----> Saving path : C:/Users/Marco/Desktop/image9KBW.png
Image size : (9000, 4637)
get and convert Image data : 0.6430368423461914
Processing data : 144.94929099082947
Save image time : 11.3296480178833
total Execution time : 156.92197585105896
----------> CUDA CONVERSION
-----> Saving path : C:/Users/Marco/Desktop/image9KBWCuda.jpg
Image size : (9000, 4637)
get and convert Image data to gpu ready : 2.886164903640747
allocate mem to gpu: 0.12500715255737305
Kernel execution time : 0.037001848220825195
Get data from gpu and convert : 0.3350191116333008
Save image time : 1.0140578746795654
total Execution time : 4.3972508907318115
<pre>

Alright , as you guys can see the GPU totally nailed the CPU and of course that was expcected , even though not on that extend , I expected  the conversion and memory “travels”
back and forth from host and device memory was going to be a huge factor, but if we see the log actually the major part of the time is spent in coverting the data in a way
that first the gpu can understand it and then in a way PIL can save the image.

Here is a plot of the performances of CPU vs GPU for this task

chart_totalTime

Looks like from those simple data the gain in performance is not completely linear , but again those are simple data , I should have taken like 20 -30 runs of the same code and take an average
of it so what you see here might not be 100% true , but I can confidently say a good 90% is .

Here a plot representing the time spent in data conversion :

chart_dataConvertion
The time spent in converting the data for the 5K compared to the 9k is quite bigger , that might also be due to the implementation of the numpy arrays.

Here another plot of the memory allocation time :

chart_memoryAllocation
Here everything looks pretty normal no surprises .
The surprises actually starts here in the kernel execution time plot :

chart_kernelAgain this data is not completely accurate but if we look the deltas between each sample we can say that the kernel pretty much took the same time on all the pictures,
Now that might be due to the python clock not being able to have enough fine time sampling? or simply because I did not reach full usage of the GPU yet so It can still easily handle that amount
of pixels without breaking a sweat.

Last thing I wanted to check was if I actually got the same exact result out of the CPU and GPU , so I subtracted the 1k images and that s the result :

image1KDiff

No , your monitor is not dirty , the thing you see in the image is a small delta between the two images , now beware that I actually bumped up the delta for a factor of 10 in order to make it more visible ,

so It s pretty much nothing, now if I have to say where this delta is coming from I would say most likely from the many conversions back and fort that happened to the memory during the whole process?

If you have an idea don’t be shy and shoot it out!

That s it folks ! I hope you enjoyed that as much as I did (the good and bad times of the development XD).

I am still a noob in this huge and wild world of massive parallel computing so any feedback is more than welcome !

cheers

M.

Jan 20

Simple image processing.

Simple image processing.

Hello everyone , today I am having a quick chat about image processing!

Lately I have become more and more interested in different areas of computer science , mostly in robotics.

It s such an awesome world, being able to create something that moves and reacts!

My wildest dream would be to make a little car that moves around being aware of it s surroundings , exactly

like showed in this course : https://www.edx.org/course/ethx/ethx-amrx-autonomous-mobile-robots-1342

(by the way the course starts in a week!).

I am well aware that it s a really complicated task and I have so much to learn , but people that knows me can tell you that does’t scare me and I am willing to put all my effort in learning new stuff.

I started by playing around with Arduino which is amazing , I will make a post about that later.

Ialso  started  having a look at an image processing course on Coursera (it just started).

I don’t think I am going to complete it because I have 3 main courses I am following already: calculus , linear algebra and Cuda programming , but I will keep an eye on it and try to do as much as I can since I will need this stuff sooner or later.

In the first week they explained generic stuff about human vision , image structure etc , then they showed some simple operations that can be done on photo , so I decided to get my hands dirty and try it myself.

 

I googled around and found a nice python library called PIL which is exactly what I needed to do my image processing

here is the full code

</pre>
import PIL
from PIL import Image
import time

inPath = "C:/Users/Marco/Desktop/"
outPath = "C:/Users/Marco/Desktop/"

&nbsp;

def blackWhite(inPath , outPath , mode = "luminosity"):
 t0 = time.time()
 print "-----> Opening path :" , inPath
 im = Image.open(inPath)
 for x in range(im.size[0]):
 for y in range(im.size[1]):
 r,g,b = im.getpixel((x,y))
 if mode == "luminosity" :
 val = int(0.21 *float(r) + 0.71*float(g) + 0.07 * float(b))

 else :
 val = int((r +g + b) /3)

 im.putpixel((x,y),(val,val,val))

 im.save(outPath)
 print "-----> Saving path :" , outPath
 t1 = time.time()
 print "Execution time : " , t1-t0

def imageDiff (im1 , im2 , outPath , mult = 5):
 t0 = time.time()
 print "-----> Opening path :" , inPath
 imm1 = Image.open(im1)
 imm2 = Image.open(im2)
 for x in range(imm1.size[0]):
 for y in range(imm1.size[1]):
 r1,g1,b1 = imm1.getpixel((x,y))
 r2,g2,b2 = imm2.getpixel((x,y))

 imm1.putpixel((x,y),(abs(r1-r2)*mult,abs(g1-g2)*mult,abs(b1-b2)*mult))

 imm1.save(outPath)
 print "-----> Saving path :" , outPath
 t1 = time.time()
 print "Execution time : " , t1-t0

def inverse(inPath , outPath ):
 t0 = time.time()
 print "-----> Opening path :" , inPath
 im = Image.open(inPath)

 for x in range(im.size[0]):
 for y in range(im.size[1]):
 r1,g1,b1 = im.getpixel((x,y))

 im.putpixel((x,y),(255-r1,255-g1,255-b1) )

 im.save(outPath)
 print "-----> Saving path :" , outPath
 t1 = time.time()
 print "Execution time : " , t1-t0




blackWhite(inPath + "jessTest.jpg", outPath + "jessTestLuminosity.jpg" , "luminosity")
blackWhite(inPath + "jessTest.jpg", outPath + "jessTestAverage.jpg" , "average")
imageDiff(inPath + "jessTestLuminosity.jpg" ,
 inPath + "jessTestAverage.jpg" ,
 outPath + "jessTestDiff.jpg" )

inverse(inPath + "jessTest.jpg", outPath + "jessTestNegative.jpg")
inverse(inPath + "jessTestDiffLow.jpg", outPath + "jessTestDiffNegativeLow.jpg")
inverse(inPath + "jessTestDiff.jpg", outPath + "jessTestDiffNegativeHigh.jpg")
<pre>

It s quite simple code , PIL handled all the heavy lifting.

Here is the output log
#######################
-----> Opening path : C:/Users/Marco/Desktop/jessTest.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestLuminosity.jpg
Execution time : 4.65300011635
-----> Opening path : C:/Users/Marco/Desktop/jessTest.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestAverage.jpg
Execution time : 4.05799984932
-----> Opening path : C:/Users/Marco/Desktop/
-----> Saving path : C:/Users/Marco/Desktop/jessTestDiff.jpg
Execution time : 5.70700001717
-----> Opening path : C:/Users/Marco/Desktop/jessTest.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestNegative.jpg
Execution time : 3.94000005722
-----> Opening path : C:/Users/Marco/Desktop/jessTestDiffLow.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestDiffNegativeLow.jpg
Execution time : 3.83899998665
-----> Opening path : C:/Users/Marco/Desktop/jessTestDiff.jpg
-----> Saving path : C:/Users/Marco/Desktop/jessTestDiffNegativeHigh.jpg
Execution time : 3.8220000267

########################################################

 

As you can see the process is quit slow , 3-5 seconds per processed image , there are a lot of things that can be done in order  to improve the performance , first of all using c++ , parallel algorithm (cpu or gpu) , also googling around  I found out  that the getpixel() and setpixel() are really slow and it s better to access directly the raw data.

Enough talk let see some output.

Here is the original image :

jessTest

 

 

Now I am going to convert it to Black and white , I have used two differents modes , one to enhance luminosity and one which is the simple average of the rgb.

Luminosity :

jessTestLuminosity

 

 

 

 

 

This is by using simple average :
jessTestAverage

 

 

They might look exactly the same but actually they are slightly different , so what I did was doing a difference  of the two

images , here is the result :

jessTestDiffLow

 

 

It was quite hard to see something so what I did was multiplying the delta for a factor of 5 and here is the result :

jessTestDiff

 

 

As last just for fun I created a function to create a negative effect , here is the result on the colored image :

 

jessTestNegative

 

 

and as last the two difference as negative , first the low and following the high (the multiplied delta)

 

 

jessTestDiffNegativeLowjessTestDiffNegativeHigh

 

 

That s it folk!

 

See ya next time

 

 

Dec 20

ALGORITHM : quick-find trees implementation

ALGORITHM : quick-find trees implementation

weightedGraph9

Hi everyone!

As you might know I am studying a lot of math and algorithms lately! I have am also following an algorithm course hosted on Coursera by Princeton University.

The mentor explained in great detail  the quick-find algorithm, the argument is uber interesting!

We started by working on the brute force approach and then from it making it  better and implementing better performance.

If you are interested you can check this page

The course actually use Java so I jumped right on it and starting using Java as-well.  To be honest I did not expect it to be that easy , It s basically a simplified version of C++ ,

you can place it between C++  and C , simple as C but all the goodies from C++ without having to work with pointers memory management etc etc.

Even though I implemented those algorithms in Java as-well my main focus was on Python just because I am more comfortable with it, I started by building a class with some nice methods ,

as a plus I implemented a class for the nodes so that if in the future I will need, I can easily expand those nodes rather than work with simple indexes in an array.

I was a bit worried about debugging so I decided that my class needed to be able to draw itself! I googled around and found Pydot , a really nice python lib to draw trees.

If you need to install it check my previous post.

Let s get started!

I am skipping the quick find implementation which is the simplest and jumping right away to the union-find version.

The test I used on all the trees was the same and looked like that :


def test2():
    qft = WCUFTree()
    for i in range(10) :
        qft.addNode()
    counter = 1
    for i in [(4,3),(3,8),(6,5),(9,4),(2,1),(5,0),(7,2),(6,1),(9,1)] :
        qft.union(i[0],i[1])
        qft.drawTree('weightedCompressedGraph' + str(counter))
        counter += 1

/*
This is a sample output of the code :</pre>
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph1.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph2.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph3.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph4.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph5.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph6.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph7.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph8.png
----> Graph saved in : D:/PROGETTI_IN_CORSO/python/algorytm/dynamicConnection/weightedCompressedGraph9.png

*/

In the test I am just adding ten nodes and then performing some unions in a loop, also after every union I am calling the drawTree() method I wrote so I can save a png representing the status of the Tree Here is the result for standard union-find tree.

UNION-FIND

union(4,3)

graph1

union(3,8)

graph2

union(6,5)

graph3

union(9,4)

graph4

union(2,1)

graph5

union(5,0)

graph6

union(7,2)

graph7

union(6,1)

graph8

union(9,1)

graph9

So here is the standard union-find tree, as you can see is quite deep already with just a couple of nodes , what we can do in order to try to reduce the computation

is to weight the connection in order to have a more balanced tree.

WEIGHTED UNION FIND

Let s perform the same test on a weighted union find tree and let see what we get

union(4,3)weightedGraph1

union(3,8)

weightedGraph2

union(6,5)

weightedGraph3

union(9,4)

weightedGraph4

union(2,1)

weightedGraph5

union(5,0)

weightedGraph6

union(7,2)

weightedGraph7

union(6,1)

weightedGraph8

union(9,1)

weightedGraph9

Now the tree result more balanced an also way less deep , that speeds up quite a bit the computation already!We can push  even a bit further by applying a path compression

WEIGHTED UNION FIND  WITH PATH COMPRESSION

Let see what happens if I apply a path compression to the tree!

union(4,3)

weightedCompressedGraph1

union(3,8)

weightedCompressedGraph2

union(6,5)

weightedCompressedGraph3

union(9,4)

weightedCompressedGraph4

union(2,1)

weightedCompressedGraph5

union(5,0)

weightedCompressedGraph6

union(7,2)

weightedCompressedGraph7

union(6,1)

weightedCompressedGraph8

union(9,1)

weightedCompressedGraph9

As you can see at the end the tree is completely flattened out , but that s its peculiarity and what we were looking for!

Well guys that s all for now! Let s see what will come up next :D Looking forward to learn more and more about algorithms!

Dec 17

Pydot and trees : easy way to draw trees in python

Pydot and trees : easy way to draw trees in python

Hi everyone today I would like to talk to you about pydot.

Pydot is a python library that lets you quickly draw nice trees.

The reason why I started looking for this kind of library is because I am following an online Algorithm Course hosted  by Princeton University and a big chunk of the course is about trees.

The Pydot lib is uber easy to use and there is a quick example of  it s usage here.

That s  the result :

example1_graph

I decided to write this post because setting up all the dependencies of the lib gave me a bit of trouble , so I thought might be useful to write them down.

First of all you need to use python 2.7.6 , that s the one I used , the first step was to install latest pydot lib which is version 1.0.28 (I think).
Next I installed  pyparsing 2.1.0 and Graphviz 2.34.
Finally tried then to run the example code and problems started to show up.

1)First error I got was I could not import dot_parser module , I tried to import manually and was giving error:
“cannot import _noncomma module”, googling  around I found out that module is not in the package of latest release of pyparsing .
So I uninstalled version 2.0.1 and installed v 1.5.7 and then the _noncomma module was there.

2) The next error was :  ”GraphViz’s executables not found” .
The reason for that seems to be coming from the fact that Pydot or Graphvis  is not adding a registry key so Pydot
cannot find the Graphviz executable.
Yes you guessed correctly pydot is a python wrap around Graphviz lib.
I googled again and came across this fix .
go and find the module pydot.py in your python27 folder, go to line 486 and replace :
all the code between for potentialKey in potentialKeys: and break with this code

for potentialKey in potentialKeys:

	try:

		path = "C:\Program Files (x86)\Graphviz2.30"

		# The regitry variable might exist, left by old installations
		# but with no value, in those cases we keep searching...
		if not path:
			continue

		# Now append the "bin" subdirectory:
		#
		path = os.path.join(path, "bin")
		progs = __find_executables(path)
		if progs is not None :
			#print "Used Windows registry"
			return progs

	except Exception, excp:
		#raise excp
		pass
	else:
		break

The variable path is the path to your grapviz installation , in my case was not Graphviz2.30 but Graphviz2.34

I hope that was clear enough !
I will be posting soon my trees implementations with drawings

Older posts «