Created
February 15, 2019 12:58
-
-
Save sounakmoju/08200628380e654b56f4abb9eff8bbef to your computer and use it in GitHub Desktop.
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: | |
def __init__(self,gdict=None): | |
if gdict is None: | |
gdict = {} | |
self.gdict = gdict | |
def getVertices(self): | |
return list(self.gdict.keys()) | |
def getedges(self): | |
edges=[] | |
for vrtx in self.gdict: | |
for nextvertex in self.gdict[vrtx]: | |
if {nextvertex,vrtx} not in edges: | |
edges.append({nextvertex,vrtx}) | |
return edges | |
def addvertex(self,vrtx): | |
if vrtx not in self.gdict: | |
self.gdict[vrtx]=[] | |
def addedge(self,edge): | |
edge=set(edge) | |
(vrtx1,vrtx2)=tuple(edge) | |
if vrtx1 in self.gdict: | |
self.gdict[vrtx1].append(vrtx2) | |
else: | |
self.gdict[vrtx1]=[vrtx2] | |
def findpath(self,start,end,path=None): | |
if path is None: | |
path=[] | |
path=path+[start] | |
if start==end: | |
return path | |
if start not in self.gdict: | |
return None | |
for vertex in self.gdict[start]: | |
extended_list=findpath(vertex,end,path) | |
if extended_list: | |
return path | |
return None | |
def adjacency_matrix(self): | |
import numpy as np | |
n=len((self.gdict.keys())) | |
a=np.zeros((n,n)) | |
self.names=list(self.gdict.keys()) | |
self.vindices=dict(zip(self.names,range(len(self.names)))) | |
print(self.vindices) | |
for me in self.gdict: | |
for j in self.gdict[me]: | |
for el in self.vindices: | |
if el==me: | |
for u in self.vindices: | |
if u==j: | |
a[self.vindices[el],self.vindices[u]]=1 | |
return a | |
g = {"a" : ["b","c"], | |
"b" : ["a", "d"], | |
"c" : ["d"], | |
"d" : ["e"], | |
"e" : ["d"] | |
} | |
graph1 = graph(g) | |
print(graph1.adjacency_matrix()) | |
print(graph1.getVertices()) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment