# Chapter 9: Graphs¶

## Example 1, page no. 314¶

In [1]:
import sys
n = None

for i in range(20):
a = []
for j in range(20):
a.append(-1)

def create_graph():
global n
print "Enter number of nodes: ",
n = int(raw_input())
max_edges = n*(n-1)
for i in range(1,max_edges):
print "Enter edge %d(0 0) to quit: " %i
origin = int(raw_input())
destination = int(raw_input())
if ((origin==0) and (destination==0)):
break
if ( origin > n or destination > n or origin<=0 or destination<=0):
print "Invalid edge! "
i -= 1
else:

def display():
global n
for i in range(1,n+1):
for j in range(1,n+1):
print ""

def insert_node():
global n
n += 1
print "The inserted node is %d " %n
for i in range(1,n+1):

def delete_node(u):
global n
if(n == 0):
print "Graph is empty "
return
if ( u>n ):
print "This node is not present in the graph "
return
for i in range(u, n):
for j in range(1, n+1):
n -= 1

def insert_edge(u, v):
global n
if (u > n):
print "Source node does not exist"
return
if(v > n):
print "Destination node does not exist"
return

def del_edge(u,v):
global n
if (u>n or v>n or adj[u][v]==0):
print "This edge does not exist"
return

create_graph()
while(1):
print "1.Insert a node"
print "2.Insert an edge"
print "3.Delete a node"
print "4.Delete an edge"
print "5.Dispaly"
print "6.Exit"
choice = int(raw_input())
if choice == 1:
insert_node()
elif choice == 2:
print "Enter an edge to be inserted: ",
origin = int(raw_input())
destin = int(raw_input())
insert_edge(origin, destin)
elif choice == 3:
print "\nEnter a node to be deleted: ",
node = int(raw_input())
delete_node(node)
elif choice == 4:
print "Enter an edge to be deleted: ",
origin = int(raw_input())
destin = int(raw_input())
del_edge(origin,destin)
elif choice == 5:
display()
elif choice == 6:
sys.exit()
else:
print "Wrong choice "

Enter number of nodes: 3
Enter edge 1(0 0) to quit:
1
2
Enter edge 2(0 0) to quit:
2
3
Enter edge 3(0 0) to quit:
3
1
Enter edge 4(0 0) to quit:
0
0
1.Insert a node
2.Insert an edge
3.Delete a node
4.Delete an edge
5.Dispaly
6.Exit
-1    1   -1
-1   -1    1
1   -1   -1
1.Insert a node
2.Insert an edge
3.Delete a node
4.Delete an edge
5.Dispaly
6.Exit
The inserted node is 4
1.Insert a node
2.Insert an edge
3.Delete a node
4.Delete an edge
5.Dispaly
6.Exit
-1    1   -1    0
-1   -1    1    0
1   -1   -1    0
0    0    0    0
1.Insert a node
2.Insert an edge
3.Delete a node
4.Delete an edge
5.Dispaly
6.Exit

An exception has occurred, use %tb to see the full traceback.

SystemExit

To exit: use 'exit', 'quit', or Ctrl-D.


## Example 2, page no. 321¶

In [5]:
from collections import deque

class MyBFS:
def __init__(self, n, e, src):
self.node = n
self.edges = e
self.source = src
self.color = ['W' for i in range(0,n)]
self.graph = color= [[False for i in range(0,n)] for j in range(0,n)]
self.queue = deque()
self.parent = [-1 for u in range(0,n)]

self.create_graph()
self.traversal()

def create_graph(self):
for u,v in self.edges:
self.graph[u][v], self.graph[v][u] = True, True

def traversal(self):

self.queue.append(self.source)
self.color[self.source] = 'B'

while len(self.queue):
u =  self.queue.popleft()
for v in range(0,self.node):
if self.graph[u][v] == True and self.color[v]=='W':
self.color[v]='B'
self.queue.append(v)
self.parent[v]=u

def show_path(self, destin):
if destin == self.source:
print destin,
elif self.parent[destin] == -1:
print "No Path"
else:
self.show_path(self.parent[destin])
print "-> ",destin,

e = []
print "Enter Number of nodes: ",
n = int(raw_input())
for i in range(n):
print "Enter edges (0 0) to quit: ",
origin = int(raw_input())
destin = int(raw_input())
if(origin == 0 and destin == 0):
break
temp = [origin, destin]
e.append(temp)

print "Enter source: "
src = int(raw_input())
print "Enter destination to be searched: "
destin = int(raw_input())
#sample [(0,1),(0,3),(1,2),(1,5),(2,7),(3,4),(3,6),(4,5),(5,7)]
bfs = MyBFS(n, e, src)
print "BFS Traversal"
bfs.show_path(destin)

 Enter Number of nodes: 10
Enter edges (0 0) to quit: 0
1
Enter edges (0 0) to quit: 0
2
Enter edges (0 0) to quit: 1
3
Enter edges (0 0) to quit: 1
4
Enter edges (0 0) to quit: 2
5
Enter edges (0 0) to quit: 5
6
Enter edges (0 0) to quit: 3
7
Enter edges (0 0) to quit: 4
9
Enter edges (0 0) to quit: 7
8
Enter edges (0 0) to quit: 0
0
Enter source:
0
Enter destination to be searched:
9
BFS Traversal
0 ->  1 ->  4 ->  9


## Example 3, page no. 326¶

In [ ]:
adj =[]
n = None

for i in range(10):
a = []
for j in range(10):
a.append(-1)

for i in range(n):
for j in range(n):
print "Enter 1 if there is an edge from %d to %d, otherwise enter 0 " %(i,j),

visited[x] = 1
print "The node visited is %d\n" %x
for j in range(n):
if (adj[x][j] ==1 and visited[j] ==0):

visited  = []
print "Enter the number of nodes in graph maximum = 10: "
n = int(raw_input())
for i in range(n):
visited.append(0)
for i in range(n):
if(visited[i] == 0):

Enter the number of nodes in graph maximum = 10:


## Example 4, page no. 332¶

In [2]:
import sys

class edge:
u = 0
v = 0
weight = 0

front = None

father = []
tree = []
n = 0
wt_tree = 0
count = 0

def create_graph():
global n
print "Enter number of nodes: ",
n = int(raw_input())
max_edges = n*(n-1)/2
for i in range(1, max_edges+1):
print "Enter edge %d (0 0) to quit: " %i
origin = int(raw_input())
destin = int(raw_input())
if (origin==0 and destin == 0):
break
print "Enter weight for this edge: ",
wt = int(raw_input())
if(origin > n or destin> n or origin < 0 or destin <     0):
print "Invalid edge..."
i -= 1
else:
insert_pque(origin, destin, wt)
if(i<n-1):
print "Spanning tree is not possible..."
sys.exit()

def insert_pque(i, j, wt):
global front
tmp = edge()
tmp.u = i
tmp.v = j
tmp.weight = wt
if(front == None or tmp.weight < front.weight):
front = tmp
else:
q = front

def make_tree():
global n
global wt_tree
global count
global father
for i in range(n):
father.append(0)
temp = edge()
root_n1 = 0
root_n2 = 0
while(count<n-1):
print count
temp = del_pque()
node1 = temp.u
node2 = temp.v
print "n1 = %d" %node1
print "n2 = %d" %node2
while(node1>0):
root_n1 = node1
node1 = father[node1]
while(node2>0):
root_n2 = node2
node2 = father[node2]
print "root_n1=%d" %root_n1
print "root_n2=%d" %root_n2
if(root_n1!=root_n2):
insert_tree(temp.u, temp.v, temp.weight)
wt_tree = wt_tree + temp.weight
father[root_n2] = root_n1

def insert_tree(i, j, wt):
global count
global tree
print "This edge inserted in the spanning tree: ",
print count
count += 1
ob = edge()
ob.u = i
ob.v = j
ob.weight = wt
tree.append(ob)

def del_pque():
global front
tmp = edge()
tmp = front
print "Edge processed is %d->%d %d" %(tmp.u, tmp.v, tmp.weight)
return tmp

create_graph()
make_tree()
print "Edges to be included in spanning tree are: ",
print count
for i in range(0, count):
print tree[i].u, tree[i].v
print "Weight of the minimum spanning tree is: ", wt_tree

Enter number of nodes: 3
Enter edge 1 (0 0) to quit:
0
1
Enter weight for this edge: 5
Enter edge 2 (0 0) to quit:
1
2
Enter weight for this edge: 7
Enter edge 3 (0 0) to quit:
2
0
Enter weight for this edge: 8
0
Edge processed is 0->1 5
n1 = 0
n2 = 1
root_n1=0
root_n2=1
This edge inserted in the spanning tree:  0
1
Edge processed is 1->2 7
n1 = 1
n2 = 2
root_n1=1
root_n2=2
This edge inserted in the spanning tree:  1
Edges to be included in spanning tree are:  2
0 1
1 2
Weight of the minimum spanning tree is:  12


## Example 5, page no. 341¶

In [ ]:
import sys

class node:
predecessor = 0
dist = 0
status = 0

class edge:
u = 0
v = 0

n = 0
TEMP = 0
PERM = 1
FALSE = 0
TRUE = 1
infinity = 9999

for i in range(10):
a = []
for j in range(10):
a.append(-1)

def create_graph():
global n
global TEMP
global PERM
global FALSE
global TRUE
global infinity
print "Enter number of vertices: ",
n = int(raw_input())
max_edges=n*(n-1)/2
for i in range(1, max_edges+1):
print "Enter edge %d(0 0 to quit): " %i
origin = int(raw_input())
destin = int(raw_input())
if((origin==0) and (destin==0)):
break
print "Enter weight for this edge: ",
wt = int(raw_input())
if( origin > n or destin > n or origin<=0 or destin<=0):
print "Invalid edge! "
i -= 1
else:
if(i<n-1):
print "Spanning tree is not possible..."
sys.exit()

def display():
global n
for i in range(1, n+1):
for j in range(1, n+1):
print ""

def all_perm(state):
global n
global n
global TEMP
global PERM
global FALSE
global TRUE
global infinity
for i in range(1, n+1):
if( state[i].status == TEMP ):
return FALSE
return TRUE

def maketree(tree):
global n
global TEMP
global PERM
global FALSE
global TRUE
global infinity
state = []
for i in range(n+1):
state.append(0)
weight=0
for i in range(1, n+1):
ob = node()
ob.predecessor=0
ob.dist = infinity
ob.status = TEMP
state[i] = ob
state[1].predecessor = 0
state[1].dist = 0
state[1].status = PERM
current = 1
count = 0
while( all_perm(state) != TRUE ):
for i in range(1, n+1):
if(adj[current][i] > 0 and state[i].status == TEMP):
state[i].predecessor = current
min = infinity;
for i in range(1, n+1):
if (state[i].status == TEMP and state[i].dist < min):
min = state[i].dist
current = i
state[current].status = PERM
u1 = state[current].predecessor
v1 = current
count += 1
tree[count].u=u1
tree[count].v=v1
return count, weight

path  = []

tree = []
for i in range(10):
ob = edge()
ob.u = 0
ob.v = 0
tree.append(ob)
create_graph()
display()
count, weight = maketree(tree)
print "Weight of spanning tree is: %d" %weight
print "Edges to be included in spanning tree are: "
for i in range(1, count+1):
print tree[i].u, tree[i].v

Enter number of vertices:

## Example 6, page no. 351¶

In [1]:
import sys

TEMP = 0
PERM = 1
infinity = 9999
adj = [[0 for i in range(100)] for j in range(100)]
n = 0

class node:
predecessor = 0
dist = 0
status = 0

for i in range(10):
ob = node()

def create_graph():
global TEMP
global PERM
global infinity
global n
print "Enter number of vertices: ",
n = int(raw_input())
max_edges = n*(n-1)
for i in  range (1, max_edges+1):
print "Enter edge %d(0 0 to quit): " %i
origin = int(raw_input())
destin = int(raw_input())
if((origin==0) and (destin==0)):
break
print "Enter weight for this edge: ",
wt = int(raw_input())
if ( origin > n or destin > n or origin<=0 or destin<=0):
print "Invalid edge! "
i -= 1
else:

def display():
for i in range(1, n+1):
for j in range(1, n+1):
print ""
def findpath(s, d, path, sdist):
global TEMP
global PERM
global infinity
global n
state = []
count = 0
sdist = 0
for i in range(1, n+1):
temp = node()
temp.predecessor = 0
temp.dist = infinity
temp.status = TEMP
state.append(temp)
state[s-1].predecessor = 0
state[s-1].dist = 0
state[s-1].status = PERM
current = s
while(current-1 != d):
for i in range(1, n+1):
if (adj[current-1][i-1] > 0 and state[i-1].status == TEMP):
if ( newdist < state[i-1].dist ):
state[i-1].predecessor = current-1
state[i-1].dist = newdist
min = infinity
current = 0
for i in range(1, n+1):
if(state[i-1].status == TEMP and state[i-1].dist < min):
min = state[i-1].dist
current = i-1
if(current==0):
return 0
state[current].status=PERM
while( current!=0 ):
count += 1
path[count] = current
current=state[current-1].predecessor
for i in range(count, -1, -1):
u = path[i]
v = path[i-1]
return count

path = []
create_graph()
print "The adjacency matrix is: "
display()
shortdist = 0
while(1):
print "\nEnter source node(0 to quit): ",
source = int(raw_input())
print "\nEnter destination node(0 to quit): ",
dest = int(raw_input())
if(source==0 or dest==0):
sys.exit()
count = findpath(source,dest,path,shortdist);
if(shortdist!=0):
print "\nShortest distance is: ", shortdist
print "\nShortest Path is: "
for i in range(count, 1, -1):
print path[i]
print path[i]
print ""
else:
print "There is no path from source to destination node"

Enter number of vertices: 3
Enter edge 1(0 0 to quit):
1
2
Enter weight for this edge: 8
Enter edge 2(0 0 to quit):
2
3
Enter weight for this edge: 7
Enter edge 3(0 0 to quit):
3
1
Enter weight for this edge: 5
Enter edge 4(0 0 to quit):
0
0
0   8   0
0   0   7
5   0   0

Enter source node(0 to quit): 2

Enter destination node(0 to quit): 3
2
There is no path from source to destination node

Enter source node(0 to quit): 0

Enter destination node(0 to quit): 0

An exception has occurred, use %tb to see the full traceback.

SystemExit

To exit: use 'exit', 'quit', or Ctrl-D.