## Friday, February 24, 2012

### Longest Path Algorithm Implemented in Python

Here I write down the longest path algorithm implementation I did in Python language. Since finding the longest path algorithm is considered as an intractable problem, you will notice that when the number of vertexes in the graph increases the time to find the longest path increases in an exponential way.

The input graph to the program is given as a separate configuration file which also I have shown separately.

longest_path.py file
``````1:  #!/usr/bin/python
2:  import string
3:  import time
4:
5:  # represents a vertex in the graph
6:  class Vertex:
7:       def __init__(self, name):
8:            self.name = name           # name of the vertex
9:            self.visited = 0          # access flag 1=visited, 0=not visited
10:
11:
12:  # represents an edge in the graph
13:  class Edge:
14:       def __init__(self, v, u, length):
15:            self.start = v
16:            self.end = u
17:            self.length = length
18:
19:
20:  # read a text file and generate the graph according to declarations
21:  def generateGraph(V, E):
22:
23:       file = open("graph_def_v11", "r")
24:       line = file.readline()
25:       line = line[:-1]
26:       while line:
27:            taglist = string.split(line)
28:            if taglist[0] == 'vertex':
29:                 V.append(Vertex(taglist[1]))
30:            elif taglist[0] == 'edge':
31:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))
32:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))
33:            line = file.readline()
34:            line = line[:-1]
35:       file.close()
36:
37:
38:  # returns the edges list of vertex v
39:  def pickEdgesList(v, E):
40:       vu = []
41:       for edge in E:
42:            if edge.start == v.name:
43:                 vu.append(edge)
44:       return vu
45:
46:  def pickVertexByName(V, A):
47:       for vertex in V:
48:            if vertex.name == A:
49:                 return vertex
50:
51:  def LP(V, E, A):
52:       #print("in LP")
53:       dist = 0
54:       maxa = 0
55:       v = pickVertexByName(V, A)
56:       v.visited = 1
57:       vu = pickEdgesList(v, E)
58:       for edge in vu:
59:            u = pickVertexByName(V, edge.end)
60:            if u.visited == 0:
61:                 dist = edge.length + LP(V, E, u.name)
62:                 if dist > maxa:
63:                      maxa = dist
64:       v.visited = 0
65:       return maxa
66:
67:
68:  def main():
69:       print('Starting Longest Path Algorithm...')
70:       t1 = time.time()
71:       # graph elements
72:       V = []
73:       E = []
74:       generateGraph(V, E)
75:       maxa = LP(V, E, 'a')
76:       print 'max=', maxa
77:       t2 = time.time()
78:       print t2-t1
79:
80:
81:  main()
``````

The content of the graph configuration file which is saved as graph_def is as follows.

``````1:  vertex a
2:  vertex b
3:  vertex c
4:  vertex d
5:  ------------
6:  edge a b 1
7:  edge a c 1
8:  edge a d 1
9:  edge b c 1
10:  edge b d 1
11:  edge c d 1
``````

You can run this program on a Linux machined by typing the following line on the terminal,

python longest_path.py

cheers!