{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"title: Problems on Graphs\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Originally Contributed by**: Arpit Bhatia"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the mathematical discipline of graph theory, a number of problems can be solved by modelling them as optimization problems.\n",
"We will see some examples of such problems in the tutorial. \n",
"These problems are also sometimes referred to as combinatorial optimization problems as \n",
"they consist of finding an optimal object from a finite set of objects."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's first import all the packages we will be using for this tutorial.\n",
"We'll be plotting all the graphs we work with in this tutorial for which we will need some additional packages."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"using JuMP\n",
"using GLPK\n",
"using GraphPlot \n",
"using LightGraphs\n",
"using Colors\n",
"using LinearAlgebra"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Representing Graphs\n",
"For the purpose of this tutorial, we will represent graphs using adjacency matrices. \n",
"An adjacency matrix, sometimes also called the connection matrix, is a square matrix used to represent a finite graph. \n",
"Its rows and columns are labeled by the graph vertices, \n",
"with a 1 or 0 in position ($v_{i}$,$v_{j}$) according to whether $v_{i}$ and $v_{j}$ are adjacent or not."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Minimum Vertex Cover\n",
"Given a graph $G = (V, E)$, a vertex-cover $V' \\subset V$ of $G$ is a collection of vertices such that \n",
"each edge in $E$ is incident to at least one of the vertices in $V'$. \n",
"The size of a vertex-cover $|V'|$ is the number of vertices present in the cover. \n",
"We wish to find the minimum vertex cover of $G$ i.e. a minimum size vertex cover.\n",
"We model this problem as an ILP by defining a decision variable $y_{v}$ for each vertex $v \\in V$ and \n",
"a constraint for each edge $e \\in E$ as follows:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && \\sum_{v \\in V} y_{v} \\\\\n",
"s.t. && y_{u} + y_{v} \\geq 1 && \\forall \\{u,v\\} \\in E \\\\\n",
"&& y_{v} \\in \\{0,1\\} && \\forall v \\in V\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.8981913146304261cx, -0.0725355660816591cy), (-0.4228495348856415cx, -0.03897795757302536cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.23414284198152013cx, 0.021738868557888882cy), (0.31150538160799857cx, 0.35785997076580056cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.29717262115521836cx, -0.13102251217268118cy), (-0.11202592060789507cx, -0.9007680780112517cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.39941593653680485cx, 0.3093323797048721cy), (0.40719442085512214cx, -0.4746794759036423cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.47135524546138335cx, 0.48276654997561536cy), (0.9270481436811627cx, 0.928622879532007cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.010497184694987546cx, -0.9337767998853622cy), (0.33054646069732263cx, -0.6429597258210303cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.2247448713915892mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.2247448713915892mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -0.07972293347075154cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3210408495160676cx, -0.03179059018393293cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.398403389142546cx, 0.41138942950762236cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.08815769224704584cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.40820696824938096cx, -0.5767365257063926cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 1.0cy), 0.04082482904638631w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.25098039215686274,0.8784313725490196,0.8156862745098039,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = [\n",
" 0 1 0 0 0 0;\n",
" 1 0 1 1 0 0;\n",
" 0 1 0 0 1 1;\n",
" 0 1 0 0 1 0;\n",
" 0 0 1 1 0 0;\n",
" 0 0 1 0 0 0;\n",
"]\n",
"\n",
"g = SimpleGraph(G)\n",
" \n",
"gplot(g)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"value.(y) = [0.0, 1.0, 1.0, 1.0, 0.0, 0.0]\n"
]
}
],
"source": [
"vertex_cover = Model(GLPK.Optimizer)\n",
"\n",
"@variable(vertex_cover, y[1:nv(g)], Bin)\n",
"@constraint(vertex_cover, [i = 1:nv(g), j = 1:nv(g); G[i,j] == 1], y[i] + y[j] >= 1)\n",
"@objective(vertex_cover, Min, sum(y))\n",
"\n",
"optimize!(vertex_cover)\n",
"@show value.(y);"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.917393670892945cx, 0.9400595207049227cy), (0.3387725333207542cx, 0.5202027289645201cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.22569729552329565cx, 0.3628542814641542cy), (0.042482858313985794cx, -0.22287546211721843cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.15415320983066788cx, 0.46342699984509594cy), (-0.7128707169077035cx, 0.4903246920561297cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.08768821239085194cx, -0.29846267056684816cy), (-0.9002978379855658cx, -0.12061537962574416cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.060151931467923435cx, -0.41028010454228336cy), (0.327447001643545cx, -0.9100033257802237cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.8453303987770097cx, 0.39607452608553867cy), (-0.9695533125137251cx, -0.0013797037238410387cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.2247448713915892mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.2247448713915892mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.2561662042136992cx, 0.46026224966944285cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.012013949623582265cx, -0.32028343032250706cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.8148837112907348cx, 0.4934894422317828cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -0.0987946198700852cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.37558498348788616cx, -1.0cy), 0.04082482904638631w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"membership = round.(Int, value.(y)) # Change to Int \n",
"membership = membership + ones(Int, nv(g)) # Make the color groups one indexed\n",
"nodecolor = [colorant\"red\", colorant\"blue\"] # Blue to represent vertices in the cover\n",
"nodefillc = nodecolor[membership]\n",
"gplot(g, nodefillc = nodefillc)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Dominating Set\n",
"A dominating set in a graph $G = (V, E)$ is a set $S \\subset V$ such that \n",
"for each vertex $v \\in V$ either $v$ or one of its neighbour should be in $S$. \n",
"Note that for some vertex $u$, $u$ and its neighbour both can be present in $S$.\n",
"We wish to find the smallest dominating set for a graph.\n",
"We model this problem as an ILP by defining a decision variable $x_{v}$ for each vertex $v \\in V$ along with\n",
"a constraint for its neighbourhood."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && \\sum_{v \\in V} x_{v} \\\\\n",
"s.t. && \\sum_{u \\in N(v)}x_{u} \\geq 1 && \\forall v \\in V \\\\\n",
"&& x_{v} \\in \\{0,1\\} && \\forall v \\in V\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9504552544999992cx, -0.6469201348211544cy), (-0.6537733230578624cx, -0.3067453215383041cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9317000730269319cx, -0.735617492710903cy), (-0.4337532991262523cx, -0.9681105321886403cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5763987488337413cx, -0.17988517371611124cy), (-0.3823897215340336cx, 0.30846746832672556cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5413019118594642cx, -0.29143505700524375cy), (-0.04369748827755321cx, -0.6195853222437082cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3618729623729771cx, 0.45354197074092006cy), (-0.3955671209267982cx, 0.7991986591108673cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2803070834085257cx, 0.39149425796263965cy), (0.437229871388653cx, 0.5168727611982328cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3286920297260405cx, 0.8875601310564625cy), (0.2224714060716695cx, 0.9866607727247956cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3279861126807284cx, 0.9314400575611063cy), (0.48015613494480314cx, 0.5984072355292368cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5648216226987739cx, 0.47658590503224835cy), (0.9466610580912667cx, 0.09530165722842239cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9750355646722663cx, -0.029083532405414766cy), (0.82878311525964cx, -0.44575749500187684cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.7545336947204185cx, -0.573914693938478cy), (0.4920149115919096cx, -0.8777057574562876cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.729682590960519cx, -0.5305069522992619cy), (0.09336526639223144cx, -0.6474572920673943cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3675966481666116cx, -0.9408061711072484cy), (-0.2903200939393739cx, -0.993932983709898cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.37941947746464333cx, -0.8938294342131045cy), (0.08253962633662273cx, -0.701992668393079cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3088951258613193cx, -0.950170460987413cy), (-0.03732906887102074cx, -0.710912486801624cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9045340337332909mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9045340337332909mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -0.7037280248995434cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.6042285775578616cx, -0.24993743145991498cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3545598928099133cx, 0.3785197260705293cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.402880190489862cx, 0.874220903781258cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.296659566835491cx, 1.0cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.5114826807900406cx, 0.5298472930903431cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.04204026917032766cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.8038186799319063cx, -0.5168812965776193cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.44272992638042186cx, -0.9347391548171464cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3654533721531842cx, -1.0cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.01922917742084418cx, -0.661082947789037cy), 0.030151134457776365w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.25098039215686274,0.8784313725490196,0.8156862745098039,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = [\n",
" 0 1 0 0 0 0 0 0 0 1 0 ;\n",
" 1 0 1 0 0 0 0 0 0 0 1;\n",
" 0 1 0 1 0 1 0 0 0 0 0;\n",
" 0 0 1 0 1 0 0 0 0 0 0;\n",
" 0 0 0 1 0 1 0 0 0 0 0;\n",
" 0 0 1 0 1 0 1 0 0 0 0;\n",
" 0 0 0 0 0 1 0 1 0 0 0;\n",
" 0 0 0 0 0 0 1 0 1 0 1;\n",
" 0 0 0 0 0 0 0 1 0 1 1;\n",
" 1 0 0 0 0 0 0 0 1 0 1;\n",
" 0 1 0 0 0 0 0 1 1 1 0;\n",
"]\n",
"\n",
"g = SimpleGraph(G)\n",
" \n",
"gplot(g)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"value.(x) = [0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0]\n"
]
}
],
"source": [
"dominating_set = Model(GLPK.Optimizer)\n",
"\n",
"@variable(dominating_set, x[1:nv(g)], Bin)\n",
"@constraint(dominating_set, [i = 1:nv(g)], dot(G[i,:], x) >= 1)\n",
"@objective(dominating_set, Min, sum(x))\n",
"\n",
"optimize!(dominating_set)\n",
"@show value.(x);"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.1071809247960641cx, 0.8810926175947675cy), (-0.1972404942447269cx, 0.49534286614724854cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.014855297752551233cx, 0.9598386597702147cy), (0.47520771431934916cx, 0.9946578404779238cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.25059284287048683cx, 0.35583080814448237cy), (-0.531615558879657cx, -0.15715803995795116cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.1403462394738394cx, 0.43612144262333497cy), (0.4393591961462302cx, 0.5471773967116341cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.6204620207202296cx, -0.2772268400049466cy), (-0.9473685534678846cx, -0.6123892170075641cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5138116788724163cx, -0.2758378533899651cy), (-0.1938645865919211cx, -0.5872130239234588cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9457768943005583cx, -0.7187108289965185cy), (-0.7087073174048314cx, -0.9476390127086458cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5927304994131926cx, -0.9567761963734019cy), (-0.20159940356842038cx, -0.6830084656326755cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.06886661679182543cx, -0.6144116612541659cy), (0.4931219571783036cx, -0.41351672688806373cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.60213181642018cx, -0.32306317917664584cy), (0.8534747810813971cx, 0.10704989156032399cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.90743977556823cx, 0.24580485159600718cy), (0.9840657902706458cx, 0.600097706745705cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8389829252736669cx, 0.22619697539686787cy), (0.5659134247996291cx, 0.5072933189640539cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9389904088100587cx, 0.718040031051738cy), (0.6114055992355008cx, 0.9557320887701438cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9265563985319958cx, 0.6568058124679773cy), (0.5868343857024245cx, 0.578326163194996cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5440593784907264cx, 0.9248889801180745cy), (0.5197274137892534cx, 0.636470875723017cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9045340337332909mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9045340337332909mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.09004359147876151cx, 0.9544965002481385cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.2143778275620295cx, 0.4219389834938776cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.5678305741881142cx, -0.22326621530734636cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -0.6663498417051643cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.6544842117053897cx, -1.0cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.13984569127622315cx, -0.6397846620060774cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.5641010316627013cx, -0.3881437261361522cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.8915055658388757cx, 0.17213043851983034cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.6737721198218818cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.5503960080455594cx, 1.0cy), 0.030151134457776365w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.5133907842344203cx, 0.5613598558410915cy), 0.030151134457776365w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,1.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"membership = convert(Array{Int},value.(x)) # Change to Int \n",
"membership = membership + ones(Int, nv(g)) # Make the color groups one indexed\n",
"nodecolor = [colorant\"red\", colorant\"blue\"] # Blue to represent vertices in the set\n",
"nodefillc = nodecolor[membership]\n",
"gplot(g, nodefillc = nodefillc)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Maximum Matching Problem\n",
"Given a graph $G = (V, E)$, a matching $M \\subset E$ of $G$ is a collection of vertex disjoint edges. \n",
"The size of the matching $M$ is the number of edges present in $M$ i.e. $|M|$. \n",
"We wish to find the Maximum matching of $G$ i.e. a matching of maximum size.\n",
"We can solve this problem by modelling it as an integer linear program (ILP). \n",
"We define a decision variable $m_{e}$ for each edge $e \\in E$ and a constraint for each vertex $u \\in V$ as follows:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\max && \\sum_{e \\in E} m_{e} \\\\\n",
"s.t. && \\sum_{e \\sim u} m_{e} \\leq 1 && \\forall u \\in V \\\\\n",
"&& m_{e} \\in \\{0,1\\} && \\forall e \\in E\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's now use JuMP to solve this problem for a sample graph."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9124440583713282cx, 0.18892987064806072cy), (-0.452849448909366cx, 0.12540489650769876cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.03455206129899002cx, 0.9121012930388699cy), (-0.013225820352004694cx, 0.46007841459140925cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.02438041411591875cx, -0.9120488501460419cy), (0.02025803757936525cx, -0.46491570592557846cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.912379990864015cx, -0.1822465808189434cy), (0.455958776456442cx, -0.1216698999858531cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.29476041865176666cx, 0.16657192326813894cy), (-0.09304962017875602cx, 0.3189107353437421cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.280736753093764cx, 0.08756085857692245cy), (0.2837820131335268cx, -0.08429879218820516cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.016448134038144498cx, 0.28399992223906717cy), (0.022970029544612712cx, -0.2887847706804085cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.09850691569734026cx, -0.3223144958161257cy), (0.2988702786794134cx, -0.1646909448483793cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.0606601717798212mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.0606601717798212mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, 0.20103181617415755cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.04384277249681379cx, 1.0cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.03316080359285012cx, -1.0cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, -0.19387559621191186cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3652935072806942cx, 0.11330295098160192cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.022516531549828467cx, 0.3721797076302791cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.029038427056296667cx, -0.3769645560716204cy), 0.035355339059327376w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.368338767320457cx, -0.11004088459288464cy), 0.035355339059327376w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.25098039215686274,0.8784313725490196,0.8156862745098039,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = [\n",
" 0 0 0 0 1 0 0 0;\n",
" 0 0 0 0 0 1 0 0;\n",
" 0 0 0 0 0 0 1 0;\n",
" 0 0 0 0 0 0 0 1;\n",
" 1 0 0 0 0 1 0 1;\n",
" 0 1 0 0 1 0 1 0;\n",
" 0 0 1 0 0 1 0 1;\n",
" 0 0 0 1 1 0 1 0;\n",
"]\n",
"\n",
"g = SimpleGraph(G)\n",
" \n",
"gplot(g)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"value.(m) = [0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0; 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0]\n"
]
}
],
"source": [
"matching = Model(GLPK.Optimizer)\n",
"\n",
"@variable(matching, m[i = 1:nv(g), j = 1:nv(g)], Bin)\n",
"@constraint(matching, [i = 1:nv(g)], sum(m[i,:]) <= 1)\n",
"@constraint(matching, [i = 1:nv(g), j = 1:nv(g); G[i,j] == 0], m[i,j] == 0)\n",
"@constraint(matching, [i = 1:nv(g), j = 1:nv(g)], m[i,j] == m[j,i])\n",
"@objective(matching, Max, sum(m))\n",
"\n",
"optimize!(matching)\n",
"@show value.(m);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The edges corresponding to the Matching are marked as one in the above matrix."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## k-Coloring Problem\n",
"A k-coloring of a graph $G=(V,E)$ is a function $c: V \\rightarrow \\{1,2...k\\}$ such that \n",
"$c(u) \\neq c(v)$ for every edge $(u,v) \\in E$. In other words, the numbers 1,2...k represent k colors, \n",
"and adjacent vertices must have different colours.\n",
"The goal of a graph coloring problem is to find a minimum number of colours needed to colour a graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We model this problem as an ILP by defining a variable decision variable $z_{i}$ for each colour we have available.\n",
"Given an upper bound $k$ on the number of colors needed, \n",
"we use $|V| \\times k$ decision variables $c_{v,k}$ denoting if vertex $v$ is assigned color $k$.\n",
"Our model will become:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && \\sum_{i=1}^{k} z_{i} \\\\\n",
"s.t. && \\sum_{i=1}^{k} c_{v,i} = 1 && \\forall v \\in V \\\\\n",
"&& c_{u,i} + c_{v,i} \\leq 1 && \\forall (u,v) \\in V, i \\in \\{1,2...k\\} \\\\\n",
"&& c_{v,i} \\in \\{0,1\\} && \\forall v \\in V, i \\in \\{1,2...k\\} \\\\\n",
"&& z_{i} \\in \\{0,1\\} && \\forall i \\in \\{1,2...k\\}\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3719616872967576cx, 0.17249108878689856cy), (-0.07575056320744855cx, -0.5558777970509808cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.35013436531570125cx, 0.30561092716747784cy), (0.19666521563673373cx, 0.9401128578985591cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.4753568936020262cx, 0.2168948516031221cy), (-0.9263868721260207cx, 0.040259058285007567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.03305402928438897cx, -0.6267776256633919cy), (0.8032613420235589cx, -0.6040399064459367cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.11426325050985064cx, -0.6689329113051771cy), (-0.5492727479231261cx, -0.9225852936365126cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8913604562777895cx, -0.5231728721450364cy), (0.9909233998063177cx, 0.3382832491789565cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8181405874145578cx, -0.6479200356998378cy), (0.39359969257793437cx, -0.9537870030793716cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9375361662477824cx, 0.465276362076697cy), (0.310738449801297cx, 0.9515410537364325cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.929316106033124cx, 0.38140855910072735cy), (0.46302862931807937cx, 0.14782343067631118cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.17217997586007508cx, 0.9785615827425165cy), (-0.33881487802943977cx, 0.8345971607162037cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9711022426520007cx, -0.06215601259696302cy), (-0.6464652710048168cx, -0.8888215741925147cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9533960251283276cx, 0.0752898893547037cy), (-0.4615134930901166cx, 0.7492989789261092cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5385727839510998cx, -0.9655434218533815cy), (0.2504616942026673cx, -0.996864289758189cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3339186377307499cx, -0.9210690894021645cy), (0.3878825215288384cx, 0.03348366336607361cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3326434211939066cx, 0.1642388258918604cy), (-0.35520820406114745cx, 0.7613344915307688cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9486832980505138mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9486832980505138mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.40174376572804693cx, 0.24572378506603698cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.045968484776159224cx, -0.6291104933301193cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.8822838560841071cx, -0.6017070387792094cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.4168174158131295cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.2482746160490794cx, 1.0cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, 0.011430124822092713cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.6175675136568175cx, -0.9624077116115705cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.32945642390838503cx, -1.0cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.3923447353512033cx, 0.11241457396390908cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.41490951821844413cx, 0.8131587434587202cy), 0.0316227766016838w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.25098039215686274,0.8784313725490196,0.8156862745098039,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = [\n",
" 0 1 0 0 1 1 0 0 0 0;\n",
" 1 0 1 0 0 0 1 0 0 0;\n",
" 0 1 0 1 0 0 0 1 0 0;\n",
" 0 0 1 0 1 0 0 0 1 0;\n",
" 1 0 0 1 0 0 0 0 0 1;\n",
" 1 0 0 0 0 0 1 0 0 1;\n",
" 0 1 0 0 0 1 0 1 0 0;\n",
" 0 0 1 0 0 0 1 0 1 0;\n",
" 0 0 0 1 0 0 0 1 0 1;\n",
" 0 0 0 0 1 1 0 0 1 0;\n",
"]\n",
"\n",
"g = SimpleGraph(G)\n",
" \n",
"gplot(g)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"value.(z) = [0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0]\n",
"value.(c) = [0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0; 0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0; 0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0; 0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0]\n"
]
}
],
"source": [
"k = nv(g)\n",
"\n",
"k_colouring = Model(GLPK.Optimizer)\n",
"\n",
"@variable(k_colouring, z[1:k], Bin)\n",
"@variable(k_colouring, c[1:nv(g),1:k], Bin)\n",
"@constraint(k_colouring, [i = 1:nv(g)], sum(c[i,:]) == 1)\n",
"@constraint(k_colouring, [i = 1:nv(g), j = 1:nv(g), l = 1:k; G[i,j] == 1], c[i,l] + c[j,l] <= 1)\n",
"@constraint(k_colouring, [i = 1:nv(g), l = 1:k], c[i,l] <= z[l])\n",
"\n",
"@objective(k_colouring, Min, sum(z))\n",
"\n",
"optimize!(k_colouring)\n",
"@show value.(z);\n",
"@show value.(c);"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.2, -1.2, 2.4, 2.4, 0.0mm, 0.0mm, 0.0mm, 0.0mm), nothing, nothing, nothing, List([Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.LinePrimitive}(Compose.LinePrimitive[Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.6259162360020979cx, 0.863253520031184cy), (-0.1298372286546869cx, 0.9872048037441551cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.7262629891417607cx, 0.7746211534207491cy), (0.9776678798004108cx, -0.07911934906892908cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.6321541771443477cx, 0.8173206335335581cy), (0.19537059478909463cx, 0.6156674409407132cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.22011404609996083cx, 0.9218998154217263cy), (-0.36902117639558013cx, -0.026518009817876664cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.27640171481584686cx, 0.9606183085258199cy), (-0.7447842471688036cx, 0.6915339047776689cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.32720030969760316cx, -0.16228121176911223cy), (0.29102870175990875cx, -0.8214331907175408cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.4554846616348667cx, -0.1318976183154654cy), (-0.9257986992659137cx, -0.30480423694362463cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.39813938392817466cx, -0.8204611472972335cy), (0.9469723690349113cx, -0.21359158021678826cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.26730031204662386cx, -0.8930740356221297cy), (-0.2501211858322261cx, -0.986022172468373cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9238089322450017cx, -0.1760496745775792cy), (0.4655197149549725cx, -0.30292498753179614cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.04475433282687116cx, 0.5883882638458566cy), (-0.7344945302254903cx, 0.6462937001565642cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.14583201194517004cx, 0.5066649597208077cy), (0.36709053824607507cx, -0.2481533517077318cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.8280651051490209cx, 0.5744798404880116cy), (-0.9852689952408692cx, -0.2544112880474625cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9439253959789815cx, -0.3878119192592504cy), (-0.3840072307697067cx, -0.9442717416036892cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2703999019470489cx, -0.9457783661542847cy), (0.3317959223983348cx, -0.3782397765315716cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9486832980505138mm)]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.9486832980505138mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}}(Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}[Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.7039308689421715cx, 0.8504583237753391cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.20785186159476043cx, 1.0cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3812833609007805cx, -0.10461819439615039cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.34511175296308605cx, -0.8790962080905027cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, -0.15495651942351907cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.12359390299127093cx, 0.5825297506989322cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.8133341003898901cx, 0.6521522133034887cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -0.3320836608629396cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.3279326267486883cx, -1.0cy), 0.0316227766016838w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.3893286471999742cx, -0.32401814268585627cy), 0.0316227766016838w)], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(0.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.15294117647058825,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.4823529411764706,0.0,0.5490196078431373,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.15294117647058825,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.9450980392156862,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.4823529411764706,0.0,0.5490196078431373,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.4823529411764706,0.0,0.5490196078431373,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.15294117647058825,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.9450980392156862,1.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.15294117647058825,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.9450980392156862,1.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(Measures.BoundingBox{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}},Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}((0.0w, 0.0h), (1.0w, 1.0h)), nothing, nothing, nothing, nothing, List([]), List([]), List([Compose.Property{Compose.FontSizePrimitive}(Compose.FontSizePrimitive[Compose.FontSizePrimitive(4.0mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.0,0.0,0.0,0.0))]), Compose.Property{Compose.FillPrimitive}(Compose.FillPrimitive[Compose.FillPrimitive(RGBA{Float64}(0.0,0.0,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))]), List([]), List([]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\"))"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c = value.(c)\n",
"membership = zeros(nv(g))\n",
"for i in 1:nv(g)\n",
" for j in 1:k\n",
" if c[i,j] == 1\n",
" membership[i] = j\n",
" break\n",
" end\n",
" end\n",
"end\n",
"membership = convert(Array{Int},membership)\n",
"\n",
"nodecolor = distinguishable_colors(nv(g), colorant\"green\")\n",
"nodefillc = nodecolor[membership]\n",
"gplot(g, nodefillc = nodefillc)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.5.1",
"language": "julia",
"name": "julia-1.5"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}