Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save sounakmoju/08200628380e654b56f4abb9eff8bbef to your computer and use it in GitHub Desktop.
Save sounakmoju/08200628380e654b56f4abb9eff8bbef to your computer and use it in GitHub Desktop.
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