The Path Project

Wednesday 6 April 2011

Update: added function to show most popular nodes:

I have now added a small script in the distribution function so that it also displays the four most popular nodes..

Download the latest version here:

http://www.4shared.com/file/HoSbn4i7/shortestpath_2.html

Please rename the downloaded file to shortestpath.py

You can directly see the code and copy it onto a shortestpath.py text file here:

http://pastebin.com/DVr2hjDM

ALWAYS make sure you download or use the file in the most recent update.. Look through the archives to find the most recent post

Now paste this file in your home directory if you are using linux, or in your python directory, in windows wherever you have installed python. Details on all the available in-built functions so far in the shortest path module will be followed in subsequent posts.

Sunday 3 April 2011

Node distribution function:

syntax: distribution(graph)
This walks 10000 times randomly in the graph and finds the various intersections of the graphs.. Finally it
will print the list "c" containing all the intersections and a graph which gives the node numbers on the x axis and the number of walks that have intersected at that node, i.e no. of flags placed in that node on the y axis..

Eg:
Import shortestpath as sp
sp.distribution(G) //Where G is a graph

This will plot the final graph

You can download the shortestpath module here:

http://www.4shared.com/file/Ysb5ADzo/shortestpath.html

Now paste this file in your home directory if you are using linux, or in your python directory, in windows wherever you have installed python. Details on all the available in-built functions so far in the shortest path module will be followed in subsequent posts.

Note: networkx and matplotlib have to be installed for this to work

Compare lists function:

Syntax: compare(list,list)
WARNING: AN EMPTY LIST NAMED "c" MUST BE CREATED BEFORE CALLING THIS FUNCTION WITH THE: "c = []" COMMAND

This compares two lists and finds the first common element in both the lists..
It returns 1 if a match is found or 0 if a match is not found in the 2 input lists..
If a match is found, it stores the match in a list "c".. If called repeatedly on different lists, it will store all the matches in list "c"..'''

Eg:
import shortestpath as sp
a = [1,2,3,4]
b= [5,6,7,2]
sp.compare(a,b)

This example will return 1.. also it will create a list c in which the number 2 will be present.

You can download the shortestpath module here:

http://www.4shared.com/file/Ysb5ADzo/shortestpath.html

Move to a random neighbour:

Syntax: rand(Node,graph)

This returns one of the neighbours of a given node, i.e it returns the next node in a walk starting from the given input node..

Eg:
import shortestpath as sp
sp.rand(2,G)

Download the shortestpath module here:

http://www.4shared.com/file/Ysb5ADzo/shortestpath.html

Random walk function added:

Syntax: walk(graph,source,destination)

This returns a list of nodes which constitute a random walk

between the source and destination nodes in which the graph is traversed

from the one node in the list to the next node respectively

Eg:

import shortestpath as sp

sp.walk(G,2,7) //Where G is the graph name, 2 and 7 are . // The source and the destination nodes

Download the shortestpath module here:

http://www.4shared.com/file/Ysb5ADzo/shortestpath.html

Let's Begin

Our aim:
To find an optimal shortest path between any two nodes in a random graph..
To begin with, we are going to work on a non-weighted graph to just find a totally path between two nodes in a graph. We predominantly use python in our projects. You can import shortestpath in your python program to use our functions.
To do this, just download this file:

http://www.4shared.com/file/Ysb5ADzo/shortestpath.html