Chapter 9: Graphs

Example 1, page no. 314

In [1]:
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 "
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
Enter your choice: 5
   -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
Enter your choice: 1
 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
Enter your choice: 5
   -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
Enter your choice: 6
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)
    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);
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
    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
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

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
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()
    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"
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
The adjacency matrix is: 
  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.