Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
AdvancedALgorithmsComplete/STD_3.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
77 lines (70 sloc)
4.82 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Graph(object): | |
def __init__(self, size): | |
self.adjMatrix = [] | |
for i in range(size): | |
self.adjMatrix.append([0 for i in range(size)]) | |
self.size = size | |
def addVer(self): | |
''' | |
Class method for adding vertices to the graph | |
Input: No input | |
Output: No output, class changes adjMatrix attribute instead | |
''' | |
for i in range(self.size): #repeat loop class attribute size number of times | |
self.adjMatrix[i].append(0) #add 0 at the end of a list under the index i in adjMatrix list | |
self.size += 1 #increase class attribute size by one | |
self.adjMatrix.append([0] * self.size) #append a list at the end of adjMatrix list consisting of 0 repeated class attribute size ammount of times | |
def addEdg(self,vtx1,vtx2): | |
''' | |
Class method for adding an edge to the graph | |
Input: No input | |
Output: No output, class changes adjMatrix attribute instead | |
''' | |
if self.adjMatrix[vtx1 - 1][vtx2 - 1] == 0: #if an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 is equal to zero | |
self.adjMatrix[vtx1 - 1][vtx2 - 1] = 1 #change value of an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 to 1 | |
self.adjMatrix[vtx2 - 1][vtx1 - 1] = 1 #change value of an element under index vtx1 - 1 in a list inside adjMatrix list under index vtx2 - 1 to 1 | |
else: #if an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 is not equal to zero | |
print('Edge already exist') | |
def remEdg(self,vtx1,vtx2): | |
''' | |
Class method for removing an edge from the graph | |
Input: No input | |
Output: No output, class changes adjMatrix attribute instead | |
''' | |
if self.adjMatrix[vtx1 - 1][vtx2 - 1] != 0: #if an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 is not equal to zero | |
self.adjMatrix[vtx1 - 1][vtx2 - 1] = 0 #change value of an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 to 0 | |
self.adjMatrix[vtx2 - 1][vtx1 - 1] = 0 #change value of an element under index vtx1 - 1 in a list inside adjMatrix list under index vtx2 - 1 to 0 | |
else: #if an element under index vtx2 - 1 in a list inside adjMatrix list under index vtx1 - 1 is equal to zero | |
print('Edge does not exist') | |
def printMat(self): | |
''' | |
Class method for printing out the graph as a matrix | |
Input: No input | |
Output: No output, class uses print statements instead | |
''' | |
print(" ",end='') #print blank space, do not go to next line after the print statement | |
for i in range(len(self.adjMatrix)): #repeat loop length of adjMatrix ammount of times | |
print(i+1,end=" ") #print i incremented by one, at the end of print statement, leave blank space instead of going to the next line | |
print("\n ", "-" * (len(self.adjMatrix) * 3 - 2)) #go to the next line and place empty spaces there, then print "-" number of times equal to lenth of adjMatrix multiplied by 3, subtracting 2 from that product | |
curVer = 1 #set value of variable current vertex to 1 | |
for i in self.adjMatrix: #outer loop, for every list in adjMatrix | |
print(curVer,end = "| ") #print value of curVer variable, then print | and spaces instead of going to the next line | |
for j in i: #inner loop, repeat for every element in the list i | |
print(j,end = " ") #print element of a list j, and create a space instead of going to the next line | |
print("\n") #go to the next line | |
curVer += 1 #increment the value of curVer variable by 1 | |
def main(): | |
g = Graph(6) | |
g.addVer() | |
g.addEdg(1,2) | |
g.addEdg(3,4) | |
g.remEdg(1,2) | |
print(g.adjMatrix) | |
print("\n") | |
g.printMat() | |
if __name__ == '__main__': | |
main() | |
#notes: | |
#we subtract 1 from v1 because vertices start from 1, and lists from 0 | |
# we do not check if vertices are the same in addEdg as edge can go from ver1 to ver1 | |
#in addEdg although comparison if self.adjMatrix[vtx1 - 1][vtx2 - 1] == 0 is not necessary, as replacing an edge would change 1 to 1, it would create need for unnecesary calculasions, and if our graph were weighted, overwrite the edge which would be better to do by a separate method |