import sys
adj =[]
n = None
for i in range(20):
a = []
for j in range(20):
a.append(-1)
adj.append(a)
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:
adj[origin][destination] = 1
def display():
global n
for i in range(1,n+1):
for j in range(1,n+1):
print "%4d" %(adj[i][j]),
print ""
def insert_node():
global n
n += 1
print "The inserted node is %d " %n
for i in range(1,n+1):
adj[i][n] = 0
adj[n][i] = 0
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):
adj[j][i]=adj[j][i+1]
adj[i][j]=adj[i+1][j]
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
adj[u][v] = 1
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
adj[u][v] = 0
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"
print "Enter your choice: ",
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 "
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)
adj =[]
n = None
for i in range(10):
a = []
for j in range(10):
a.append(-1)
adj.append(a)
def buildadjm(adj, n):
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),
adj[i][j] = int(raw_input())
def dfs(x, visited, adj, n):
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):
dfs(j,visited,adj,n);
visited = []
print "Enter the number of nodes in graph maximum = 10: "
n = int(raw_input())
buildadjm(adj, n);
for i in range(n):
visited.append(0)
for i in range(n):
if(visited[i] == 0):
dfs(i,visited,adj,n);
import sys
class edge:
u = 0
v = 0
weight = 0
link = None
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):
tmp.link = front
front = tmp
else:
q = front
while(q.link != None and q.link.weight <= tmp.weight):
q = q.link
tmp.link = q.link
q.link = tmp
if(q.link == None):
tmp.link = None
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)
front = front.link
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
import sys
class node:
predecessor = 0
dist = 0
status = 0
class edge:
u = 0
v = 0
adj = []
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)
adj.append(a)
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:
adj[origin][destin]=wt
adj[destin][origin]=wt
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 "%3d" %(adj[i][j]),
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):
if(adj[current][i] < state[i].dist):
state[i].predecessor = current
state[i].dist = adj[current][i]
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
weight = weight+adj[u1][v1]
return count, weight
path = []
tree = []
for i in range(10):
ob = edge()
ob.u = 0
ob.v = 0
tree.append(ob)
create_graph()
print "Adjacency matrix is: "
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
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()
adj.append(ob)
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:
adj[origin][destin] = wt
def display():
for i in range(1, n+1):
for j in range(1, n+1):
print "%3d" %(adj[i][j]),
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):
newdist = state[current-1].dist + adj[current-1][i-1]
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]
sdist += adj[u][v]
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"