exercises_3_4_5.py

file=open("IsPath.txt","w")          #open file for isPath function
fileBfs=open("bfs.txt","w")          #open file for bfs function
fileDfs=open("dfs.txt","w")          #open file for dfs function

class graph(object):
    def __init__(self,gDictionary=None): 
        if gDictionary is None:
             gDictionary={}
        self.gDictionary =gDictionary


    def Vertices(self):                          #return vertices function
        Vertices=list(self.gDictionary.keys())      #saves dictionarty keys in list as vertices
        return Vertices
       

    def getEdges(self):                          #returns edges function
        edge=[]                                          
        for vert in self.gDictionary:             #iterates through dictionary keys and values 
            for nxt in self.gDictionary[vert]:    
                if {nxt,vert} not in edge:         
                    edge.append({vert,nxt})         
        return edge


    def addVertice(self,vert):                     #add vertice function
        if vert not in self.gDictionary:
            self.gDictionary[vert]=[]
    

    def addEdge(self,edge):                        #add edges function
        edge=set(edge)                               
        (vert1,vert2)=tuple(edge)                  
        if vert1 in self.gDictionary:
            self.gDictionary[vert1].append(vert2)
        else:
            self.gDictionary[vert1]=[vert2]


    def isPath(self,v,w,path=[]):           #check if path exist between two nodes
        path= path + [v]
        if v==w:                             #if we find the 2nd node                
            return path 
        for i in self.gDictionary[v]:           #going through the graph
            if i not in path:
                path2= self.isPath(i,w,path)     #creating a new path variable for recursion
                if path2:
                    return path2
        return None
            
        
    def isConnected(self,vert):                     #compares the number of nodes in graph and the nodes 
        graphLen=len(self.gDictionary)             #in a dfs of a node in the graph to show if graph is connected              
        dfsLen=len(self.dfs(int(vert)))
        if graphLen != dfsLen:
            return False
        elif graphLen == dfsLen:
            return True


    def dfs(self,vert):
        visited=[]
        stack=[vert]                          #using list as stack
        while stack:                           
            v =stack.pop()
            if v not in visited:
                visited.append(v)
                for n in self.gDictionary[v]:    
                    stack.append(n)
        return visited
    

    def bfs(self, vert):      
        visited=[]
        que=[vert]                           #using list as queue
        while que:
            v=que.pop(0)
            if  v not in visited:
                visited=visited+[v]
                que=que+ self.gDictionary[v]
        return visited


undGraph = {               #unweighted and undirected graph
    0: [1, 3],
    1: [0, 2],
    2: [1, 4],
    3: [0],
    4: [0, 2],
    5: [],
}


graph=graph(undGraph)

print("Vertices::",graph.Vertices())            #get vertices and print
print("Edges::",graph.getEdges())               ##get edges and print

print("Adding node [7] to the graph")       
graph.addVertice(7)                                 #add a vertice

print("Adding Edge {5,7}")
graph.addEdge({7,5})                              #add an edge 

print("Vertices::",graph.Vertices())             #get vertices
print("Edges::",graph.getEdges())                #get edges
print("Graph:: ",undGraph)


#DFS                                              #printing dfs of a node and and insert it in a file 
dfsInput=int(input("Write a node for DFS:: "))
dfsVar=graph.dfs(dfsInput)
print("This is DFS: ",dfsVar)
for i in dfsVar:
    fileDfs.write(str(i))
fileDfs.close()
print("Dfs was written in file dfsVar.txt")

#BFS                                              #printing bfs of a node and and insert it in a file 
bfsInput=int(input("Write a node for BFS:: "))
bfsVar=graph.bfs(bfsInput)
print("This is BFS: ",bfsVar)
for i in bfsVar:
    fileBfs.write(str(i))
fileBfs.close()
print("Bfs was written in file bfsVar.txt")

#IsConnected                                       #output of isConnected function
if graph.isConnected(input("Write a vertice to check if graph is connected:  "))==True:
    print("Graph is Connected ")
else:
    print("Graph is NOT Connected")

#isPath                                                #input to isPath function and insert the output to a file
print("Checking if path exists between 2 Nodes::")     #then printing
node1=int(input("First Node: "))
node2=int(input("Second Node: "))
isPathVar=graph.isPath(node1,node2)
if isPathVar == None:
    print("No Path found between ",node1," and ",node2)
else:
    for i in isPathVar:
        file.write(str(i))
        file.write(" ")

    file.close()
    print("Path exists and  written to file IsPath.txt")
    file=open("IsPath.txt","r")
    print("Path::",file.read())
    file.close()