GRAPHSINPYTHON

ORIGINSOFGRAPHTHEORY
Beforewestartwiththeactualimplementationsof
graphsinPythonandbeforewestartwiththe
introductionofPythonmodulesdealingwithgraphs,we
wanttodevoteourselvestotheoriginsofgraphtheory.
TheoriginstakeusbackintimetotheKnigsbergofthe
[Link].
TheriverPregelflowedthroughthetown,creatingtwo
[Link]
[Link]
movedbythequestion,ifitwaspossibletotakeawalk
throughthetownbyvisitingeachareaofthetownand
crossingeachbridgeonlyonce?Everybridgemusthave
beencrossedcompletely,[Link]
halfwayontoabridgeandthenturnaroundandlater
[Link]
[Link]
solvedtheproblemin1735byprovingthatitisnot
[Link]
eachlandareaisirrelevantandthattheonlythingwhich
matteredistheorder(orthesequence)inwhichthe
[Link],eliminatingunnecessaryfactsandfocussingon
[Link],[Link]"land
area"asavertexandeachbridgeasanedge,wehave"reduced"theproblemtoagraph.

INTRODUCTIONINTOGRAPHTHEORYUSINGPYTHON
BeforewestartourtreatizeonpossiblePythonrepresentations
ofgraphs,wewanttopresentsomegeneraldefinitionsofgraphs
anditscomponents.
A"graph"1inmathematicsandcomputerscienceconsistsof
"nodes",alsoknownas"vertices".Nodesmayormaynotbe
[Link],whichisa
pictorialrepresentationofagraph,thenode"a"isconnected
withthenode"c",but"a"isnotconnectedwith"b".The
[Link]
edgesbetweenthenodesareundirected,thegraphiscalledan
[Link](node)
toanother,[Link]
iscalledanarc.
Thoughgraphsmaylookverytheoretical,manypractical
[Link]
modelproblemsorsituationsinphysics,biology,[Link],
graphsareusedtorepresentnetworksofcommunication,dataorganization,computationaldevices,theflowof
computation,
Inthelattercase,theareusedtorepresentthedataorganisation,likethefilesystemofanoperatingsystem,or
[Link],[Link],becausea
linkisadirectededgeoranarc.
Pythonhasnobuiltindatatypeorclassforgraphs,[Link]
forrepresentinggraphsinPython,[Link]
way:
graph={"a":["c"],
"b":["c","e"],
"c":["a","b","d","e"],
"d":["c"],
"e":["c","b"],
"f":[]
}

[Link],which
[Link].
Anedgecanbeseenasa2tuplewithnodesaselements,i.e.("a","b")
Functiontogeneratethelistofalledges:
defgenerate_edges(graph):
edges=[]
fornodeingraph:
forneighbouringraph[node]:
[Link]((node,neighbour))
returnedges
print(generate_edges(graph))
Thiscodegeneratesthefollowingoutput,ifcombinedwiththepreviouslydefinedgraphdictionary:

$python3graph_simple.py
[('a','c'),('c','a'),('c','b'),('c','d'),('c','e'),('b','c'),
('b','e'),('e','c'),('e','b'),('d','c')]
Aswecansee,thereisnoedgecontainingthenode"f"."f"isanisolatednodeofourgraph.
ThefollowingPythonfunctioncalculatestheisolatednodesofagivengraph:
deffind_isolated_nodes(graph):
"""returnsalistofisolatednodes."""
isolated=[]
fornodeingraph:
ifnotgraph[node]:
isolated+=node
returnisolated
Ifwecallthisfunctionwithourgraph,alistcontaining"f"willbereturned:["f"]

GRAPHSASAPYTHONCLASS
Beforewegoonwithwritingfunctionsforgraphs,wehavea
[Link]
thefollowinglistingofourclass,youcanseeinthe__init__
methodthatweuseadictionary"self.__graph_dict"forstoring
theverticesandtheircorrespondingadjacentvertices.
"""APythonClass
AsimplePythongraphclass,
demonstratingtheessential
factsandfunctionalitiesofgraphs.
"""
classGraph(object):
def__init__(self,graph_dict=None):
"""initializesagraphobject
IfnodictionaryorNoneisgiven,
anemptydictionarywillbeused
"""
ifgraph_dict==None:
graph_dict={}
self.__graph_dict=graph_dict
defvertices(self):
"""returnstheverticesofagraph"""

returnlist(self.__graph_dict.keys())
defedges(self):
"""returnstheedgesofagraph"""
returnself.__generate_edges()
defadd_vertex(self,vertex):
"""Ifthevertex"vertex"isnotin
self.__graph_dict,akey"vertex"withanempty
listasavalueisaddedtothedictionary.
Otherwisenothinghastobedone.
"""
ifvertexnotinself.__graph_dict:
self.__graph_dict[vertex]=[]
defadd_edge(self,edge):
"""assumesthatedgeisoftypeset,tupleorlist
betweentwoverticescanbemultipleedges!
"""
edge=set(edge)
(vertex1,vertex2)=tuple(edge)
ifvertex1inself.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1]=[vertex2]
def__generate_edges(self):
"""Astaticmethodgeneratingtheedgesofthe
graph"graph".Edgesarerepresentedassets
withone(aloopbacktothevertex)ortwo
vertices
"""
edges=[]
forvertexinself.__graph_dict:
forneighbourinself.__graph_dict[vertex]:
if{neighbour,vertex}notinedges:
[Link]({vertex,neighbour})
returnedges
def__str__(self):
res="vertices:"
forkinself.__graph_dict:
res+=str(k)+""
res+="\nedges:"
foredgeinself.__generate_edges():
res+=str(edge)+""
returnres
if__name__=="__main__":
g={"a":["d"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":[]
}
graph=Graph(g)
print("Verticesofgraph:")
print([Link]())
print("Edgesofgraph:")
print([Link]())
print("Addvertex:")

graph.add_vertex("z")
print("Verticesofgraph:")
print([Link]())

print("Addanedge:")
graph.add_edge({"a","z"})

print("Verticesofgraph:")
print([Link]())
print("Edgesofgraph:")
print([Link]())
print('Addinganedge{"x","y"}withnewvertices:')
graph.add_edge({"x","y"})
print("Verticesofgraph:")
print([Link]())
print("Edgesofgraph:")
print([Link]())

Ifyoustartthismodulestandalone,youwillgetthefollowingresult:
$[Link]
Verticesofgraph:
['a','c','b','e','d','f']
Edgesofgraph:
[{'a','d'},{'c','b'},{'c'},{'c','d'},{'c','e'}]
Addvertex:
Verticesofgraph:
['a','c','b','e','d','f','z']
Addanedge:
Verticesofgraph:
['a','c','b','e','d','f','z']
Edgesofgraph:
[{'a','d'},{'c','b'},{'c'},{'c','d'},{'c','e'},{'a','z'}]
Addinganedge{"x","y"}withnewvertices:
Verticesofgraph:
['a','c','b','e','d','f','y','z']
Edgesofgraph:
[{'a','d'},{'c','b'},{'c'},{'c','d'},{'c','e'},{'a','z'},{'y',
'x'}]

PATHSINGRAPHS
[Link]
problem,wewillhavetopresentsomeformaldefinitions.
Adjacentvertices:
Twoverticesareadjacentwhentheyarebothincidenttoacommonedge.
PathinanundirectedGraph:
ApathinanundirectedgraphisasequenceofverticesP=(v1,v2,...,vn)VxVx...xVsuchthatviisadjacentto
v{i+1}for1i<n.SuchapathPiscalledapathoflengthnfromv1tovn.
SimplePath:
Apathwithnorepeatedverticesiscalledasimplepath.
Example:
(a,c,e)isasimplepathinourgraph,aswellas(a,c,e,b).(a,c,e,b,c,d)isapathbutnotasimple
path,becausethenodecappearstwice.
Thefollowingmethodfindsapathfromastartvertextoanendvertex:

deffind_path(self,start_vertex,end_vertex,path=None):
"""findapathfromstart_vertextoend_vertex
ingraph"""
ifpath==None:
path=[]
graph=self.__graph_dict
[Link](start_vertex)
ifstart_vertex==end_vertex:
returnpath
ifstart_vertexnotingraph:
returnNone
forvertexingraph[start_vertex]:
ifvertexnotinpath:
extended_path=self.find_path(vertex,
end_vertex,
path)
ifextended_path:
returnextended_path
returnNone
Ifwesaveourgraphclassincludingthefind_pathmethodas"[Link]",wecancheckthewayofworkingofour
find_pathfunction:
fromgraphsimportGraph
g={"a":["d"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":[]
}
graph=Graph(g)
print("Verticesofgraph:")
print([Link]())
print("Edgesofgraph:")
print([Link]())
print('Thepathfromvertex"a"tovertex"b":')
path=graph.find_path("a","b")
print(path)
print('Thepathfromvertex"a"tovertex"f":')
path=graph.find_path("a","f")
print(path)
print('Thepathfromvertex"c"tovertex"c":')
path=graph.find_path("c","c")
print(path)
Theresultofthepreviousprogramlookslikethis:
Verticesofgraph:
['e','a','d','f','c','b']
Edgesofgraph:
[{'e','c'},{'a','d'},{'d','c'},{'b','c'},{'c'}]
Thepathfromvertex"a"tovertex"b":
['a','d','c','b']
Thepathfromvertex"a"tovertex"f":
None
Thepathfromvertex"c"tovertex"c":
['c']

Themethodfind_all_pathsfindsallthepathsbetweenastartvertextoanendvertex:
deffind_all_paths(self,start_vertex,end_vertex,path=[]):
"""findallpathsfromstart_vertexto
end_vertexingraph"""
graph=self.__graph_dict
path=path+[start_vertex]
ifstart_vertex==end_vertex:
return[path]
ifstart_vertexnotingraph:
return[]
paths=[]
forvertexingraph[start_vertex]:
ifvertexnotinpath:
extended_paths=self.find_all_paths(vertex,
end_vertex,
path)
forpinextended_paths:
[Link](p)
returnpaths
Weslightlychangedourexamplegraphbyaddingedgesfrom"a"to"f"andfrom"f"to"d"totestthepreviously
definedmethod:
fromgraphsimportGraph
g={"a":["d","f"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":["d"]
}
graph=Graph(g)
print("Verticesofgraph:")
print([Link]())
print("Edgesofgraph:")
print([Link]())
print('Allpathsfromvertex"a"tovertex"b":')
path=graph.find_all_paths("a","b")
print(path)
print('Allpathsfromvertex"a"tovertex"f":')
path=graph.find_all_paths("a","f")
print(path)
print('Allpathsfromvertex"c"tovertex"c":')
path=graph.find_all_paths("c","c")
print(path)
Theresultlookslikethis:
Verticesofgraph:
['d','c','b','a','e','f']
Edgesofgraph:
[{'d','a'},{'d','c'},{'c','b'},{'c'},{'c','e'},{'f','a'},{'d',
'f'}]
Allpathsfromvertex"a"tovertex"b":
[['a','d','c','b'],['a','f','d','c','b']]
Allpathsfromvertex"a"tovertex"f":

[['a','f']]
Allpathsfromvertex"c"tovertex"c":
[['c']]

DEGREE
Thedegreeofavertexvinagraphisthenumberofedges
connectingit,[Link]
visdenoteddeg(v).ThemaximumdegreeofagraphG,denoted
by(G),andtheminimumdegreeofagraph,denotedby(G),
arethemaximumandminimumdegreeofitsvertices.
Inthegraphontherightside,themaximumdegreeis5atvertex
candtheminimumdegreeis0,[Link].
Ifallthedegreesinagrapharethesame,thegraphisaregular
[Link],alldegreesarethesame,andsowe
canspeakofthedegreeofthegraph.
Thedegreesumformula(Handshakinglemma):
vVdeg(v)=2|E|
[Link]
[Link]
[Link]"handshakinglemma"stemsfromapopularmathematicalproblem:Inanygroupofpeoplethe
numberofpeoplewhohaveshakenhandswithanoddnumberofotherpeoplefromthegroupiseven.
Thefollowingmethodcalculatesthedegreeofavertex:
defvertex_degree(self,vertex):
"""Thedegreeofavertexisthenumberofedgesconnecting
it,[Link]
double,[Link]
ofadjacentvertices."""
adj_vertices=self.__graph_dict[vertex]
degree=len(adj_vertices)+adj_vertices.count(vertex)
returndegree
Thefollowingmethodcalculatesalistcontainingtheisolatedverticesofagraph:
deffind_isolated_vertices(self):
"""returnsalistofisolatedvertices."""
graph=self.__graph_dict
isolated=[]
forvertexingraph:
print(isolated,vertex)
ifnotgraph[vertex]:
isolated+=[vertex]
returnisolated
ThemethodsdeltaandDeltacanbeusedtocalculatetheminimumandmaximumdegreeofavertexrespectively:
defdelta(self):
"""theminimumdegreeofthevertices"""
min=100000000
forvertexinself.__graph_dict:
vertex_degree=self.vertex_degree(vertex)
ifvertex_degree<min:
min=vertex_degree
returnmin

defDelta(self):
"""themaximumdegreeofthevertices"""
max=0
forvertexinself.__graph_dict:
vertex_degree=self.vertex_degree(vertex)
ifvertex_degree>max:
max=vertex_degree
returnmax

DEGREESEQUENCE
Thedegreesequenceofanundirectedgraphisdefinedasthesequenceofitsvertexdegreesinanonincreasingorder.
Thefollowingmethodreturnsatuplewiththedegreesequenceoftheinstancegraph:
defdegree_sequence(self):
"""calculatesthedegreesequence"""
seq=[]
forvertexinself.__graph_dict:
[Link](self.vertex_degree(vertex))
[Link](reverse=True)
returntuple(seq)
Thedegreesequenceofourexamplegraphisthefollowingsequenceofintegers:(5,2,1,1,1,0).
[Link],twographswiththesamedegreesequencearenot
necessarilyisomorphic.
[Link]
statesthatanonincreasingsequenceofnnumbersdi(fori=1,...,n)isthedegreesequenceofasimplegraphifand
onlyifthesumofthesequenceisevenandthefollowingconditionisfulfilled:

IMPLEMENTATIONOFTHEERDSGALLAITHEOREM
Ourgraphclassseefurtherdownforacompletelistingcontainsamethod"erdoes_gallai"whichdecides,ifa
[Link],wecheck,[Link]
functionreturnsFalse,becausetheErdsGallaitheoremcan'[Link]
methodis_degree_sequencewhethertheinputsequenceisadegreesequence,[Link]
[Link],astheinputissupposedtobeadegreesequence,soyoumaydropthis
[Link],wecheckinthebodyofthesecondifstatement,iftheinequationofthetheoremis
fulfilled:
@staticmethod
deferdoes_gallai(dsequence):
"""ChecksiftheconditionoftheErdoesGallaiinequality
isfullfilled
"""
ifsum(dsequence)%2:
#sumofsequenceisodd
returnFalse
ifGraph.is_degree_sequence(dsequence):
forkinrange(1,len(dsequence)+1):
left=sum(dsequence[:k])
right=k*(k1)+sum([min(x,k)forxindsequence[k:]])
ifleft>right:
returnFalse
else:
#sequenceisincreasing

returnFalse
returnTrue

Versionwithoutthesuperfluousdegreesequencetest:
@staticmethod
deferdoes_gallai(dsequence):
"""ChecksiftheconditionoftheErdoesGallaiinequality
isfullfilled
dsequencehastobeavaliddegreesequence
"""
ifsum(dsequence)%2:
#sumofsequenceisodd
returnFalse
forkinrange(1,len(dsequence)+1):
left=sum(dsequence[:k])
right=k*(k1)+sum([min(x,k)forxindsequence[k:]])
ifleft>right:
returnFalse
returnTrue

GRAPHDENSITY
Thegraphdensityisdefinedastheratioofthenumberofedgesofagivengraph,andthetotalnumberofedges,the
[Link]:Itmeasureshowcloseagivengraphistoacompletegraph.
Themaximaldensityis1,[Link],becausethemaximumnumberofedgesinagraph
dependsontheverticesandcanbecalculatedas:
[Link]=*|V|*(|V|1).
Ontheotherhandtheminimaldensityis0,ifthegraphhasnoedges,[Link].
Forundirectedsimplegraphs,thegraphdensityisdefinedas:

[Link]
fewedges,[Link],[Link]
bound(supremum)forasparsedensityandnogreatestlowerbound(infimum)fordefiningadensegraph.
TheprecisestmathematicalnotationusesthebigOnotation:
SparseGraph:DenseGraph:
AdensegraphisagraphG=(V,E)inwhich|E|=(|V|2).
"density"isamethodofourclasstocalculatethedensityofagraph:
defdensity(self):
"""methodtocalculatethedensityofagraph"""
g=self.__graph_dict
V=len([Link]())
E=len([Link]())
return2.0*E/(V*(V1))
Wecantestthismethodwiththefollowingscript.
fromgraph2importGraph
g={"a":["d","f"],
"b":["c","b"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":["a"]
}

complete_graph={
"a":["b","c"],
"b":["a","c"],
"c":["a","b"]
}
isolated_graph={
"a":[],
"b":[],
"c":[]
}
graph=Graph(g)
print([Link]())
graph=Graph(complete_graph)
print([Link]())
graph=Graph(isolated_graph)
print([Link]())
Acompletegraphhasadensityof1andisolatedgraphhasadensityof0,aswecanseefromtheresultsofthe
previoustestscript:
$pythontest_density.py
0.466666666667
1.0
0.0

CONNECTEDGRAPHS
Agraphissaidtobeconnectedifeverypairofverticesinthe
[Link]
connectedgraph.
Itpossibletodeterminewithasimplealgorithmwhetheragraph
isconnected:
[Link]
point
[Link]
reachedfromx.
[Link],thegraphis
connectedotherwiseitisdisconnected.
Weimplementamethodis_connectedtocheckifagraphisa
[Link]'tputemphasisonefficiencybutonreadability.
defis_connected(self,
vertices_encountered=None,
start_vertex=None):
"""determinesifthegraphisconnected"""
ifvertices_encounteredisNone:
vertices_encountered=set()
gdict=self.__graph_dict
vertices=list([Link]())#"list"necessaryinPython3
ifnotstart_vertex:
#chosseavertexfromgraphasastartingpoint
start_vertex=vertices[0]
vertices_encountered.add(start_vertex)
iflen(vertices_encountered)!=len(vertices):

forvertexingdict[start_vertex]:
ifvertexnotinvertices_encountered:
ifself.is_connected(vertices_encountered,vertex):
returnTrue
else:
returnTrue
returnFalse

Ifyouaddthismethodtoourgraphclass,[Link]
[Link]:
fromgraph2importGraph
g={"a":["d"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":[]
}
g2={"a":["d","f"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":["a"]
}
g3={"a":["d","f"],
"b":["c","b"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":["a"]
}
graph=Graph(g)
print(graph)
print(graph.is_connected())
graph=Graph(g2)
print(graph)
print(graph.is_connected())
graph=Graph(g3)
print(graph)
print(graph.is_connected())

[Link]
component,asdoeseachedge.

DISTANCEANDDIAMETEROFAGRAPH
Thedistance"dist"[Link]
backtracks,detours,orloopsareallowedforthecalculationofadistance.
Inourexamplegraphontheright,thedistancebetweenthevertexaandthevertexfis3,[Link](a,f)=3,becausethe
shortestwayisviatheverticescande(orcandbalternatively).
Theeccentricityofavertexsofagraphgisthemaximaldistancetoeveryothervertexofthegraph:

e(s)=max({dist(s,v)|vV})
(Visthesetofallverticesofg)
Thediameterdofagraphisdefinedasthemaximum
[Link]
diameteristhelengthoftheshortestpathbetweenthemost
[Link],firstfind
[Link]
lengthofanyofthesepathsisthediameterofthegraph.
Wecandirectlyseeinourexamplegraphthatthediameteris3,
becausetheminimallengthbetweenaandfis3andthereisno
otherpairofverticeswithalongerpath.
Thefollowingmethodimplementsanalgorithmtocalculatethe
diameter.
defdiameter(self):
"""calculatesthediameterofthegraph"""

v=[Link]()
pairs=[(v[i],v[j])foriinrange(len(v)1)forjinrange(i+1,
len(v))]
smallest_paths=[]
for(s,e)inpairs:
paths=self.find_all_paths(s,e)
smallest=sorted(paths,key=len)[0]
smallest_paths.append(smallest)
smallest_paths.sort(key=len)
#longestpathisattheendoflist,
#[Link]
diameter=len(smallest_paths[1])
returndiameter
Wecancalculatethediameterofourexamplegraphwiththefollowingscript,assumingagain,thatourcomplete
[Link]:
fromgraph2importGraph
g={"a":["c"],
"b":["c","e","f"],
"c":["a","b","d","e"],
"d":["c"],
"e":["b","c","f"],
"f":["b","e"]
}
graph=Graph(g)
diameter=[Link]()
print(diameter)
Itwillprintoutthevalue3.

THECOMPLETEPYTHONGRAPHCLASS
InthefollowingPythoncode,youfindthecompletePythonClassModulewithallthediscussedmethodes:[Link]

TREE/FOREST

[Link]
byexactlyonesimplepath.
[Link],aforestingraphtheorycanconsistofasingletree!
Agraphwithonevertexandnoedgeisatree(andaforest).
Anexampleofatree:

Whilethepreviousexampledepictsagraphwhichisatreeandforest,thefollowingpictureshowsagraphwhich
consistsoftwotrees,[Link]:

OVERVIEWOFFORESTS:
Withonevertex:

Forestgraphswithtwovertices:

Forestgraphswiththreevertices:

SPANNINGTREE
AspanningtreeTofaconnected,undirectedgraphGisasubgraphG'ofG,whichisatree,andG'containsallthe
verticesandasubsetoftheedgesofG.G'containsalltheedgesofG,[Link],aspanningtree
[Link],everyvertexliesinthetree,butno
cycles(orloops)arecontained.
Example:
Afullyconnectedgraph:

Twospanningtreesfromthepreviousfullyconnectedgraph:

HAMILTONIANGAME

[Link]
cycle(orcircuit)isaHamiltonianpaththatisacycle.
Noteforcomputerscientists:Generally,itisnotnotpossibletodetermine,whethersuchpathsorcyclesexistin
arbitrarygraphs,becausetheHamiltonianpathproblemhasbeenproventobeNPcomplete.
ItisnamedafterWilliamRowanHamiltonwhoinventedthesocalled"icosiangame",orHamilton'spuzzle,which
[Link]
icosiancalculus,analgebraicstructurebasedonrootsofunitywithmanysimilaritiestothequaternions,whichhealso
invented.

COMPLETELISTINGOFTHEGRAPHCLASS
"""APythonClass
AsimplePythongraphclass,demonstratingthe
essential
factsandfunctionalitiesofgraphs.
"""
classGraph(object):
def__init__(self,graph_dict=None):
"""initializesagraphobject
IfnodictionaryorNoneisgiven,anemptydictionarywillbe
used
"""
ifgraph_dict==None:
graph_dict={}
self.__graph_dict=graph_dict
defvertices(self):
"""returnstheverticesofagraph"""
returnlist(self.__graph_dict.keys())
defedges(self):
"""returnstheedgesofagraph"""
returnself.__generate_edges()
defadd_vertex(self,vertex):
"""Ifthevertex"vertex"isnotin
self.__graph_dict,akey"vertex"withanempty
listasavalueisaddedtothedictionary.
Otherwisenothinghastobedone.
"""
ifvertexnotinself.__graph_dict:
self.__graph_dict[vertex]=[]
defadd_edge(self,edge):
"""assumesthatedgeisoftypeset,tupleorlist
betweentwoverticescanbemultipleedges!
"""
edge=set(edge)
vertex1=[Link]()
ifedge:
#notaloop
vertex2=[Link]()
else:
#aloop
vertex2=vertex1
ifvertex1inself.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1]=[vertex2]
def__generate_edges(self):
"""Astaticmethodgeneratingtheedgesofthe
graph"graph".Edgesarerepresentedassets
withone(aloopbacktothevertex)ortwo
vertices
"""
edges=[]
forvertexinself.__graph_dict:
forneighbourinself.__graph_dict[vertex]:
if{neighbour,vertex}notinedges:

[Link]({vertex,neighbour})
returnedges
def__str__(self):
res="vertices:"
forkinself.__graph_dict:
res+=str(k)+""
res+="\nedges:"
foredgeinself.__generate_edges():
res+=str(edge)+""
returnres
deffind_isolated_vertices(self):
"""returnsalistofisolatedvertices."""
graph=self.__graph_dict
isolated=[]
forvertexingraph:
print(isolated,vertex)
ifnotgraph[vertex]:
isolated+=[vertex]
returnisolated
deffind_path(self,start_vertex,end_vertex,path=[]):
"""findapathfromstart_vertextoend_vertex
ingraph"""
graph=self.__graph_dict
path=path+[start_vertex]
ifstart_vertex==end_vertex:
returnpath
ifstart_vertexnotingraph:
returnNone
forvertexingraph[start_vertex]:
ifvertexnotinpath:
extended_path=self.find_path(vertex,
end_vertex,
path)
ifextended_path:
returnextended_path
returnNone

deffind_all_paths(self,start_vertex,end_vertex,path=[]):
"""findallpathsfromstart_vertexto
end_vertexingraph"""
graph=self.__graph_dict
path=path+[start_vertex]
ifstart_vertex==end_vertex:
return[path]
ifstart_vertexnotingraph:
return[]
paths=[]
forvertexingraph[start_vertex]:
ifvertexnotinpath:
extended_paths=self.find_all_paths(vertex,
end_vertex,
path)
forpinextended_paths:
[Link](p)
returnpaths
defis_connected(self,
vertices_encountered=None,
start_vertex=None):
"""determinesifthegraphisconnected"""
ifvertices_encounteredisNone:
vertices_encountered=set()
gdict=self.__graph_dict
vertices=list([Link]())#"list"necessaryinPython3
ifnotstart_vertex:
#chosseavertexfromgraphasastartingpoint

#chosseavertexfromgraphasastartingpoint
start_vertex=vertices[0]
vertices_encountered.add(start_vertex)
iflen(vertices_encountered)!=len(vertices):
forvertexingdifromgraph2importGraph
g={"a":["d"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":[]
}
graph=Graph(g)
print(graph)
[Link]():
print(graph.vertex_degree(node))
print("Listofisolatedvertices:")
print(graph.find_isolated_vertices())
print("""Apathfrom"a"to"e":""")
print(graph.find_path("a","e"))
print("""Allpathesfrom"a"to"e":""")
print(graph.find_all_paths("a","e"))
print("Themaximumdegreeofthegraphis:")
print([Link]())
print("Theminimumdegreeofthegraphis:")
print([Link]())
print("Edges:")
print([Link]())
print("DegreeSequence:")
ds=graph.degree_sequence()
print(ds)
fullfilling=[[2,2,2,2,1,1],
[3,3,3,3,3,3],
[3,3,2,1,1]
]
non_fullfilling=[[4,3,2,2,2,1,1],
[6,6,5,4,4,2,1],
[3,3,3,1]]
forsequenceinfullfilling+non_fullfilling:
print(sequence,Graph.erdoes_gallai(sequence))
print("Addvertex'z':")
graph.add_vertex("z")
print(graph)
print("Addedge('x','y'):")
graph.add_edge(('x','y'))
print(graph)
print("Addedge('a','d'):")
graph.add_edge(('a','d'))
print(graph)
ct[start_vertex]:
ifvertexnotinvertices_encountered:
ifself.is_connected(vertices_encountered,vertex):
returnTrue
else:
returnTrue

returnTrue
returnFalse
defvertex_degree(self,vertex):
"""Thedegreeofavertexisthenumberofedgesconnecting
it,[Link]
double,[Link]
ofadjacentvertices."""
adj_vertices=self.__graph_dict[vertex]
degree=len(adj_vertices)+adj_vertices.count(vertex)
returndegree
defdegree_sequence(self):
"""calculatesthedegreesequence"""
seq=[]
forvertexinself.__graph_dict:
[Link](self.vertex_degree(vertex))
[Link](reverse=True)
returntuple(seq)
@staticmethod
defis_degree_sequence(sequence):
"""MethodreturnsTrue,ifthesequence"sequence"isa
degreesequence,[Link].
OtherwiseFalseisreturned.
"""
#checkifthesequencesequenceisnonincreasing:
returnall(x>=yforx,yinzip(sequence,sequence[1:]))

defdelta(self):
"""theminimumdegreeofthevertices"""
min=100000000
forvertexinself.__graph_dict:
vertex_degree=self.vertex_degree(vertex)
ifvertex_degree<min:
min=vertex_degree
returnmin

defDelta(self):
"""themaximumdegreeofthevertices"""
max=0
forvertexinself.__graph_dict:
vertex_degree=self.vertex_degree(vertex)
ifvertex_degree>max:
max=vertex_degree
returnmax
defdensity(self):
"""methodtocalculatethedensityofagraph"""
g=self.__graph_dict
V=len([Link]())
E=len([Link]())
return2.0*E/(V*(V1))
defdiameter(self):
"""calculatesthediameterofthegraph"""

v=[Link]()
pairs=[(v[i],v[j])foriinrange(len(v))forjinrange(i+1,
len(v)1)]
smallest_paths=[]
for(s,e)inpairs:
paths=self.find_all_paths(s,e)
smallest=sorted(paths,key=len)[0]
smallest_paths.append(smallest)
smallest_paths.sort(key=len)
#longestpathisattheendoflist,

#longestpathisattheendoflist,
#[Link]
diameter=len(smallest_paths[1])
returndiameter
@staticmethod
deferdoes_gallai(dsequence):
"""ChecksiftheconditionoftheErdoesGallaiinequality
isfullfilled
"""
ifsum(dsequence)%2:
#sumofsequenceisodd
returnFalse
ifGraph.is_degree_sequence(dsequence):
forkinrange(1,len(dsequence)+1):
left=sum(dsequence[:k])
right=k*(k1)+sum([min(x,k)forxindsequence[k:]])
ifleft>right:
returnFalse
else:
#sequenceisincreasing
returnFalse
returnTrue
WecantestthisGraphclasswiththefollowingprogram:
fromgraphsimportGraph
g={"a":["d"],
"b":["c"],
"c":["b","c","d","e"],
"d":["a","c"],
"e":["c"],
"f":[]
}
graph=Graph(g)
print(graph)
[Link]():
print(graph.vertex_degree(node))
print("Listofisolatedvertices:")
print(graph.find_isolated_vertices())
print("""Apathfrom"a"to"e":""")
print(graph.find_path("a","e"))
print("""Allpathesfrom"a"to"e":""")
print(graph.find_all_paths("a","e"))
print("Themaximumdegreeofthegraphis:")
print([Link]())
print("Theminimumdegreeofthegraphis:")
print([Link]())
print("Edges:")
print([Link]())
print("DegreeSequence:")
ds=graph.degree_sequence()
print(ds)
fullfilling=[[2,2,2,2,1,1],
[3,3,3,3,3,3],
[3,3,2,1,1]
]
non_fullfilling=[[4,3,2,2,2,1,1],

[6,6,5,4,4,2,1],
[3,3,3,1]]
forsequenceinfullfilling+non_fullfilling:
print(sequence,Graph.erdoes_gallai(sequence))
print("Addvertex'z':")
graph.add_vertex("z")
print(graph)
print("Addedge('x','y'):")
graph.add_edge(('x','y'))
print(graph)
print("Addedge('a','d'):")
graph.add_edge(('a','d'))
print(graph)
Ifwestartthisprogram,wegetthefollowingoutput:
vertices:cefadb
edges:{'c','b'}{'c'}{'c','d'}{'c','e'}{'d','a'}
5
1
0
1
2
1
Listofisolatedvertices:
[]c
[]e
[]f
['f']a
['f']d
['f']b
['f']
Apathfrom"a"to"e":
['a','d','c','e']
Allpathesfrom"a"to"e":
[['a','d','c','e']]
Themaximumdegreeofthegraphis:
5
Theminimumdegreeofthegraphis:
0
Edges:
[{'c','b'},{'c'},{'c','d'},{'c','e'},{'d','a'}]
DegreeSequence:
(5,2,1,1,1,0)
[2,2,2,2,1,1]True
[3,3,3,3,3,3]True
[3,3,2,1,1]True
[4,3,2,2,2,1,1]False
[6,6,5,4,4,2,1]False
[3,3,3,1]False
Addvertex'z':
vertices:cefzadb
edges:{'c','b'}{'c'}{'c','d'}{'c','e'}{'d','a'}
Addedge('x','y'):
vertices:cefzaydb
edges:{'c','b'}{'c'}{'c','d'}{'c','e'}{'d','a'}{'y','x'}
Addedge('a','d'):
vertices:cefzaydb
edges:{'c','b'}{'c'}{'c','d'}{'c','e'}{'d','a'}{'y','x'}

Footnotes:
1Thegraphsstudiedingraphtheory(andinthischapterofourPythontutorial)shouldnotbeconfusedwiththe

graphsoffunctions
2Asingletonisasetthatcontainsexactlyoneelement.
Credits:
NarayanaChikkam,nchikkam(at)gmail(dot)com,pointedoutanindexerrorinthe"erdoes_gallai"[Link]
verymuch,Narayana!

20112016,BerndKlein,[Link]