{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# We start with procedures that are used to compute the vertex connectivity kappa_G(s,t) \n",
"# and to display the kappa_G(s,t) internally disjoint s-t paths.\n",
"# We follow the algorithm presented in \n",
"# A.-H. Hossein, Connectivity Algorithms, \n",
"# Chapter 12 in Topics in Structural Graph Theory, Beineke and Wilson eds., \n",
"# Cambridge University Press, 2013\n",
"\n",
"def VertexNetwork(G,s,t): \n",
"# For a graph G and vertices s and t, \n",
"# defines a digraph in which a max flow from s to t is equal to kappa_G(s,t).\n",
"# Vertices of G must be labelled {0,1,...,n-1}, where n is the order of G.\n",
" V=set(G.vertices());\n",
" U=list(V.difference({s,t}));\n",
" n=G.order();\n",
" H=G.subgraph(U);\n",
" F=DiGraph();\n",
" F.add_vertices([s,t]);\n",
" E=H.edges();\n",
" for v in U:\n",
" F.add_vertices([v,v+n]);\n",
" F.add_edge(v,v+n);\n",
" for e in E:\n",
" e1=e[0];\n",
" e2=e[1];\n",
" F.add_edge(e1+n,e2);\n",
" F.add_edge(e2+n,e1);\n",
" for v in U:\n",
" if G.has_edge(s,v):\n",
" F.add_edge(s,v);\n",
" if G.has_edge(v,t):\n",
" F.add_edge(v+n,t);\n",
" if G.has_edge(s,t):\n",
" F.add_edge(s,t);\n",
" return F;\n",
"\n",
"def VertexConnectivity(G,s,t): # Computes kappa_G(s,t) \n",
" n=G.order()\n",
" H=VertexNetwork(G,s,t)\n",
" F=H.flow(s,t,value_only=True)\n",
" return F\n",
"\n",
"def InternallyDisjointPaths(G,s,t,SizeOfFigure): \n",
"# Displays a drawing of G in which a collection of kappa_G(s,t) internally disjoint \n",
"# paths is rainbow coloured.\n",
"# Returns a list of lists containing the edges of each path.\n",
"# SizeOfFigure=[x,y] is used when plotting G.\n",
" n=G.order()\n",
" H=VertexNetwork(G,s,t)\n",
" F=H.flow(s,t,value_only=False)[1]\n",
" for i in range(n):\n",
" F.contract_edge(i,i+n)\n",
" E=F.edges()\n",
" P=[]\n",
" for e in E:\n",
" if e[0]==s:\n",
" P.append([e])\n",
"\n",
" for p in P:\n",
" while True:\n",
" length=len(p)\n",
" head=p[length-1][1]\n",
" if head==t:\n",
" break\n",
" else:\n",
" for e in E:\n",
" if head==e[0]:\n",
" p.append(e)\n",
" \n",
" NumPaths=len(P)\n",
" \n",
" for i in range(NumPaths):\n",
" p=P[i]\n",
" for e in p:\n",
" G.delete_edge((e[0],e[1],None))\n",
" G.delete_edge((e[1],e[0],None))\n",
" G.add_edge((e[0],e[1],i+1))\n",
" \n",
" Colors={}\n",
" Colors.update({None:\"black\"})\n",
" R=rainbow(NumPaths+1)\n",
" for i in range(NumPaths):\n",
" Colors.update({i+1:R[i]})\n",
" \n",
" GP=G.graphplot(edge_labels=False, color_by_label=Colors)\n",
" show(GP.plot(figsize=SizeOfFigure))\n",
" print(\"Found\",NumPaths,\"internally disjoint paths between the vertices labelled\",s,\"and \"+str(t)+\".\")\n",
" return P"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def SubgraphOfPsi(k,l):\n",
"# Returns a graph isomorphic to Psi_{k,p}[0,l-1], \n",
"# assuming p>l+s so that edges don't \"wrap around\".\n",
"# The vertices w_0 to w_{l-1} are labelled 0 to l-1, respectively.\n",
"# The vertices x_0 to x_{l-1} are labelled l to 2l-1, respectively.\n",
"# The vertices y_0 to y_{l-1} are labelled 2l to 3l-1, respectively.\n",
"# The vertices z_0 to z_{l-1} are labelled 3l to 4l-1, respectively.\n",
"\n",
" E=[]\n",
" for i in range(l):\n",
" for j in range(k):\n",
" if i+j