{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"using Pkg;\n",
"Pkg.add([\"LightGraphs\", \"GraphPlot\", \"Laplacians\",\"Colors\"]);\n",
"using LinearAlgebra;\n",
"using LightGraphs, GraphPlot, Laplacians,Colors;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphs and Networks"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Take for example, a sample directed graph:\n",
"\n",
""
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{6, 9} directed simple Int64 graph"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# creating the above directed graph\n",
"let \n",
" edges = [(1, 2), (1, 3), (2,4), (3, 2), (3, 5), (4, 5), (4, 6), (5, 2), (5, 6)]\n",
" global graph = DiGraph(Edge.(edges))\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Incidence matrix\n",
"- shows the relationship between nodes (columns) via edges (rows)\n",
"- edges are connected by exactly two nodes (duh), with direction indicated by the sign of each row in the edge column\n",
" + a value of $1$ at $A_{12}$ indicates that edge 1 is directed towards node $1$, or node $2$ is the destination node for edge $1$\n",
"- edge rows sum to 0 and constant column vectors $c(1,\\dots,1)$ are in the nullspace\n",
"- cannot represent self-loops (nodes connected to themselves)\n",
"\n",
"_Using Strang's definition in the LALFD book, a graph consists of nodes defined as columns $n$ and edges $m$ as rows between the nodes. An **Incidence Matrix** A is $m\\,\\times\\,n$. For the above sample directed graph, we can generate its incidence matrix._"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9×6 Array{Int64,2}:\n",
" -1 1 0 0 0 0\n",
" -1 0 1 0 0 0\n",
" 0 -1 0 1 0 0\n",
" 0 1 -1 0 0 0\n",
" 0 0 -1 0 1 0\n",
" 0 0 0 -1 1 0\n",
" 0 0 0 -1 0 1\n",
" 0 1 0 0 -1 0\n",
" 0 0 0 0 -1 1"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# create an incidence matrix from a directed graph\n",
"function create_incidence(graph::DiGraph)\n",
" M = zeros(Int, ne(graph), nv(graph))\n",
" \n",
" # each edge maps to a row in the incidence matrix\n",
" for (i, e) in edges(graph) |> enumerate\n",
" M[i, e.src] = -1\n",
" M[i, e.dst] = 1\n",
" end\n",
" return M\n",
"end\n",
"\n",
"A = create_incidence(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Creating a graph from an incidence matrix\n",
"- reversal of above, shows the relationship between an graph and an incidence matrix"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"code_folding": []
},
"outputs": [
{
"data": {
"text/plain": [
"create_graph (generic function with 1 method)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function create_graph(incidence::Array{Int,2})\n",
" n = size(incidence)[2]\n",
" graph = DiGraph(n)\n",
"\n",
" # find nodes where edge goes out and edge goes in\n",
" v_out = findall(x->x == -1, incidence) # edge goes out of vertex\n",
" v_in = findall(x->x == 1, incidence) # edge goes in of vertex\n",
" \n",
" # match the Cartesian index between the two lists, add edge\n",
" for i in v_in\n",
" for o in v_out\n",
" if o[1] == i[1]\n",
" add_edge!(graph, o[2], i[2])\n",
" end\n",
" end\n",
" end\n",
" return graph\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Visualising an incidence matrix\n",
"- this is really just visualising a graph, but is this ok?"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.9433861482927702cx, -0.08492077756084468cy), (-0.38994718504056314cx, -0.9150792224391552cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9433861482927702cx, 0.08492077756084468cy), (-0.38994718504056314cx, 0.9150792224391552cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2312712607173676cx, -1.0cy), (0.23127126071736748cx, -1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.33333333333333337cx, 0.8979379273840342cy), (-0.33333333333333326cx, -0.8979379273840342cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2312712607173676cx, 1.0cy), (0.23127126071736748cx, 1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.33333333333333326cx, -0.8979379273840342cy), (0.33333333333333337cx, 0.8979379273840342cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.389947185040563cx, -0.9150792224391553cy), (0.9433861482927701cx, -0.08492077756084482cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3010584721149381cx, 0.9031754163448146cy), (-0.3010584721149385cx, -0.9031754163448147cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.389947185040563cx, 0.9150792224391553cy), (0.9433861482927701cx, 0.08492077756084482cy)])], 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.47052974924705687cx, -0.8558639343295267cy), (-0.38994718504056314cx, -0.9150792224391552cy), (-0.41361415706233806cx, -0.8179202062063807cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.41361415706233806cx, 0.8179202062063807cy), (-0.38994718504056314cx, 0.9150792224391552cy), (-0.47052974924705687cx, 0.8558639343295267cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.13730199863877662cx, -1.034202014332567cy), (0.23127126071736748cx, -1.0cy), (0.13730199863877662cx, -0.9657979856674331cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3675353476659001cx, -0.8039686653054434cy), (-0.33333333333333326cx, -0.8979379273840342cy), (-0.2991313190007664cx, -0.8039686653054434cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.13730199863877662cx, 0.9657979856674331cy), (0.23127126071736748cx, 1.0cy), (0.13730199863877662cx, 1.034202014332567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.36753534766590024cx, 0.8039686653054434cy), (0.33333333333333337cx, 0.8979379273840342cy), (0.2991313190007665cx, 0.8039686653054434cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9197191762709952cx, -0.18207979379361924cy), (0.9433861482927701cx, -0.08492077756084482cy), (0.8628035840862764cx, -0.14413606567047335cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.30378966205056546cx, -0.8032127202950605cy), (-0.3010584721149385cx, -0.9031754163448147cy), (-0.2388959025365845cx, -0.8248439734663875cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8628035840862764cx, 0.14413606567047335cy), (0.9433861482927701cx, 0.08492077756084482cy), (0.9197191762709952cx, 0.18207979379361924cy)])], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.5cx, -0.75cy), \"b1\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.5cx, 0.75cy), \"b2\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.1666666666666666cx, -1.0cy), \"b3\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.33333333333333337cx, -0.5cy), \"b4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.1666666666666666cx, 1.0cy), \"b5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.33333333333333326cx, 0.5cy), \"b6\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.8333333333333333cx, -0.25cy), \"b7\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.1666666666666667cx, -0.5cy), \"b8\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.8333333333333333cx, 0.25cy), \"b9\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.33333333333333337cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.33333333333333337cx, 1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.33333333333333326cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.33333333333333326cx, 1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, 0.0cy), \"x1\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.33333333333333337cx, -1.0cy), \"x2\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.33333333333333337cx, 1.0cy), \"x3\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.33333333333333326cx, -1.0cy), \"x4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.33333333333333326cx, 1.0cy), \"x5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, 0.0cy), \"x6\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gplot(\n",
" create_graph(A), \n",
" # manually setting node locations to match the above\n",
" [1.0, 2, 2, 3, 3, 4],\n",
" [0.0, -1, 1, -1, 1, 0],\n",
" nodelabel = [\"x$i\" for i in 1:nv(graph)],\n",
" edgelabel = [\"b$i\" for i in 1:ne(graph)],\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Laplacian matrix / Kirchhoff matrix\n",
"- $A^\\top A$, where $A$ is an incidence matrix\n",
"- diagonal entries make up the degree matrix\n",
"- off-diagonal entries are $-B$, the adjacency matrix\n",
"\n",
"_The **Laplacian Matrix** $L\\,=\\,A^TA$ is a square matrix, symmetric and positive semidefinite:_"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6×6 Array{Int64,2}:\n",
" 2 -1 -1 0 0 0\n",
" -1 4 -1 -1 -1 0\n",
" -1 -1 3 0 -1 0\n",
" 0 -1 0 3 -1 -1\n",
" 0 -1 -1 -1 4 -1\n",
" 0 0 0 -1 -1 2"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"L = A'A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Degree matrix\n",
"- counts the edges into nodes $1,\\dots,n$. $D_{ii}$ is the edges for node $i$\n",
"- each degree is in the range $1, n-1$; meaning each node is connected to at least one other node and at most all other nodes\n",
"- the trace of the diagonal matrix is twice the number of edges. $\\frac{tr(D)}{2} = m$ where $m$ = rows of $A$\n",
"\n",
"The Degree matrix counts the edges into nodes, which can be extracted using Julia's Diagonal() constructor:"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6×6 Diagonal{Int64,Array{Int64,1}}:\n",
" 2 ⋅ ⋅ ⋅ ⋅ ⋅\n",
" ⋅ 4 ⋅ ⋅ ⋅ ⋅\n",
" ⋅ ⋅ 3 ⋅ ⋅ ⋅\n",
" ⋅ ⋅ ⋅ 3 ⋅ ⋅\n",
" ⋅ ⋅ ⋅ ⋅ 4 ⋅\n",
" ⋅ ⋅ ⋅ ⋅ ⋅ 2"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"D = Diagonal(L)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Adjacency matrix\n",
"- describes connectedness between nodes\n",
"- _looks to symmetric and positive definite?_ - is this always the case?"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6×6 Array{Int64,2}:\n",
" 0 1 1 0 0 0\n",
" 1 0 1 1 1 0\n",
" 1 1 0 0 1 0\n",
" 0 1 0 0 1 1\n",
" 0 1 1 1 0 1\n",
" 0 0 0 1 1 0"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"B = -(L - D)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Kirchhoff's Current Law\n",
"- independent solutions to $A^\\top y = 0$ = $n - m + 1$, meaning edges - nodes + 1 independent loops to a graph\n",
"- balance of currents: flows into a node equals flows out of a node, maintaining equilibrium\n",
"- a loop is a cycle of edges that start and ends on the same node"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{Array{Int64,1},1}:\n",
" [0, 0, 0, 0, 0, 0]\n",
" [0, 0, 0, 0, 0, 0]\n",
" [0, 0, 0, 0, 0, 0]\n",
" [0, 0, 0, 0, 0, 0]"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# for incidence matrix A, there are n - m + 1 = 4 solutions\n",
"# b1, -b2, -b4\n",
"y₁ = [1, -1, 0, -1, 0, 0, 0, 0, 0]\n",
"# -b4, b5, b8\n",
"y₂ = [0, 0, 0, -1, 1, 0, 0, 1, 0]\n",
"# b3,b6,b8\n",
"y₃ = [0, 0, 1, 0, 0, 1, 0, 1, 0]\n",
"# b6, -b7, b9\n",
"y₄ = [0, 0, 0, 0, 0, 1, -1, 0, 1]\n",
"\n",
"[A'y for y in [y₁, y₂, y₃, y₄]]"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"gplot_nestedloops (generic function with 1 method)"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function gplot_nestedloops(nestedloops)\n",
" gplot(\n",
" create_graph(A), \n",
" # manually setting node locations to match the above\n",
" [1.0, 2, 2, 3, 3, 4],\n",
" [0.0, -1, 1, -1, 1, 0],\n",
" nodelabel = [\"x$i\" for i in 1:nv(graph)],\n",
" edgelabel = [\"b$i\" for i in 1:ne(graph)],\n",
" edgelabeldistx=-0.7,\n",
" edgestrokec = [i in nestedloops ? colorant\"green\" : colorant\"lightgrey\" for i in 1:ne(graph)]\n",
" )\n",
"end"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.9433861482927702cx, -0.08492077756084468cy), (-0.38994718504056314cx, -0.9150792224391552cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9433861482927702cx, 0.08492077756084468cy), (-0.38994718504056314cx, 0.9150792224391552cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2312712607173676cx, -1.0cy), (0.23127126071736748cx, -1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.33333333333333337cx, 0.8979379273840342cy), (-0.33333333333333326cx, -0.8979379273840342cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2312712607173676cx, 1.0cy), (0.23127126071736748cx, 1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.33333333333333326cx, -0.8979379273840342cy), (0.33333333333333337cx, 0.8979379273840342cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.389947185040563cx, -0.9150792224391553cy), (0.9433861482927701cx, -0.08492077756084482cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.3010584721149381cx, 0.9031754163448146cy), (-0.3010584721149385cx, -0.9031754163448147cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.389947185040563cx, 0.9150792224391553cy), (0.9433861482927701cx, 0.08492077756084482cy)])], 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)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.47052974924705687cx, -0.8558639343295267cy), (-0.38994718504056314cx, -0.9150792224391552cy), (-0.41361415706233806cx, -0.8179202062063807cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.41361415706233806cx, 0.8179202062063807cy), (-0.38994718504056314cx, 0.9150792224391552cy), (-0.47052974924705687cx, 0.8558639343295267cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.13730199863877662cx, -1.034202014332567cy), (0.23127126071736748cx, -1.0cy), (0.13730199863877662cx, -0.9657979856674331cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3675353476659001cx, -0.8039686653054434cy), (-0.33333333333333326cx, -0.8979379273840342cy), (-0.2991313190007664cx, -0.8039686653054434cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.13730199863877662cx, 0.9657979856674331cy), (0.23127126071736748cx, 1.0cy), (0.13730199863877662cx, 1.034202014332567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.36753534766590024cx, 0.8039686653054434cy), (0.33333333333333337cx, 0.8979379273840342cy), (0.2991313190007665cx, 0.8039686653054434cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9197191762709952cx, -0.18207979379361924cy), (0.9433861482927701cx, -0.08492077756084482cy), (0.8628035840862764cx, -0.14413606567047335cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.30378966205056546cx, -0.8032127202950605cy), (-0.3010584721149385cx, -0.9031754163448147cy), (-0.2388959025365845cx, -0.8248439734663875cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8628035840862764cx, 0.14413606567047335cy), (0.9433861482927701cx, 0.08492077756084482cy), (0.9197191762709952cx, 0.18207979379361924cy)])], Symbol(\"\"))]), 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)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.5714434508311761cx, -0.75cy), \"b1\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.5714434508311761cx, 0.75cy), \"b2\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.09522321583549057cx, -1.0cy), \"b3\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4047767841645094cx, -0.5cy), \"b4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.09522321583549057cx, 1.0cy), \"b5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.2618898825021572cx, 0.5cy), \"b6\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.7618898825021572cx, -0.25cy), \"b7\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.23811011749784275cx, -0.5cy), \"b8\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.7618898825021572cx, 0.25cy), \"b9\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.33333333333333337cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.33333333333333337cx, 1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.33333333333333326cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.33333333333333326cx, 1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, 0.0cy), \"x1\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.33333333333333337cx, -1.0cy), \"x2\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.33333333333333337cx, 1.0cy), \"x3\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.33333333333333326cx, -1.0cy), \"x4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.33333333333333326cx, 1.0cy), \"x5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, 0.0cy), \"x6\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(\"\"))"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# a really nonfunctional way of implementing the inner nested loop. \n",
"loops = [[1,2,4],[4,5,8],[3,6,8],[6,7,9]];\n",
"\n",
"# step through these loops in the presentation. gplot breaks once you put it in a for loop.\n",
"for loop in loops\n",
" IJulia.clear_output()\n",
" gplot_nestedloops(loop) |> display\n",
" sleep(1)\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graph Laplacian Matrix\n",
"- $K = A^\\top CA$ is a weighted graph Laplacian in which the weights are in $C$\n",
"- In standard Laplacian matrix $C = I$"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.03676678814744493cx, -0.9174032067758662cy), (-0.36905725043628196cx, -0.3583082792072858cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.1842903223471573cx, -0.9475769459490523cy), (0.9124300846715147cx, -0.5116816961502052cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.49138158345457456cx, -0.19492435406567588cy), (-0.9376292858529343cx, 0.38308846003360075cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8987695479079991cx, -0.4462562486305231cy), (-0.3277804172155083cx, -0.28871387945188653cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.9361500916570695cx, -0.3796354302118559cy), (0.46406207549538614cx, 0.2090758947669945cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.8987273987983623cx, 0.4512056703838093cy), (0.2989395659508176cx, 0.30136902822166356cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9127301318875061cx, 0.5167966348952081cy), (-0.20316963539954513cx, 0.9470789570558688cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.31583984053947645cx, 0.23127108937554974cy), (-0.3446385426945301cx, -0.2182834687043057cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.34027316526405293cx, 0.37130650777129803cy), (-0.05596076539864869cx, 0.917392598883098cy)])], 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.28617852954478645cx, -0.41426466957862396cy), (-0.36905725043628196cx, -0.3583082792072858cy), (-0.3415365412580224cx, -0.45444677600396793cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8493713390206036cx, -0.5892935161065347cy), (0.9124300846715147cx, -0.5116816961502052cy), (0.8142363667424302cx, -0.5306024191613214cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.8531315639627176cx, 0.32960823008492157cy), (-0.9376292858529343cx, 0.38308846003360075cy), (-0.9072767047169189cx, 0.2878061383869196cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2302196027471457cx, -0.26676194376799467cy), (-0.3277804172155083cx, -0.28871387945188653cy), (-0.23893406515961607cx, -0.33460860383672675cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5495316606347356cx, 0.1571629867757493cy), (0.46406207549538614cx, 0.2090758947669945cy), (0.4961666022074995cx, 0.1143695097415317cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.20145135913992612cx, 0.2790968587539881cy), (0.2989395659508176cx, 0.30136902822166356cy), (0.20994299227903984cx, 0.3469717679933465cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2657852444613361cx, 0.8691091840549104cy), (-0.20316963539954513cx, 0.9470789570558688cy), (-0.30125397878892846cx, 0.927599183395132cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.2862010521680004cx, -0.13713508793819462cy), (-0.3446385426945301cx, -0.2182834687043057cy), (-0.24771165410428236cx, -0.19368309740195117cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.02690805234505221cx, 0.8614215434547672cy), (-0.05596076539864869cx, 0.917392598883098cy), (-0.028457068988656846cx, 0.8212492336216979cy)])], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.29757805022596373cx, -0.4567836144873641cy), \"1.0\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.774180101754668cx, -0.5944439815744431cy), \"2.0\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.8572527173268772cx, 0.2789788224675196cy), \"0.75\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.07175815198063173cx, -0.3215982750121784cy), \"0.5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.5501591253643416cx, 0.10170966946598264cy), \"0.85\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.050159125364341584cx, 0.33249322797856623cy), \"0.9\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.3369248254652884cx, 0.8659688979877692cy), \"2.4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.22170511019251787cx, -0.13460883782376507cy), \"3.0\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.013128216322825459cx, 0.822174776663599cy), \"1.0\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.09672040701867202cx, -1.0cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.429010869307509cx, -0.2757114859831521cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, -0.4592586420992575cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, 0.46387559195107686cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.40021216715245544cx, 0.288699106654396cy), 0.04082482904638631w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.1158997672870512cx, 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.09672040701867202cx, -1.0cy), \"x1\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.429010869307509cx, -0.2757114859831521cy), \"x2\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, -0.4592586420992575cy), \"x3\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, 0.46387559195107686cy), \"x4\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.40021216715245544cx, 0.288699106654396cy), \"x5\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.1158997672870512cx, 1.0cy), \"x6\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#vector for weights\n",
"W = [1.0,2.0,0.75,0.5,0.85,0.9,2.4,3,1.0]\n",
"\n",
"#label edges with weights\n",
"gplot(\n",
" graph,\n",
" nodelabel=[\"x$i\" for i in 1:nv(graph)],\n",
" edgelabel=W\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6×6 Array{Float64,2}:\n",
" 3.0 -1.0 -2.0 0.0 0.0 0.0\n",
" -1.0 5.25 -0.5 -0.75 -3.0 0.0\n",
" -2.0 -0.5 3.35 0.0 -0.85 0.0\n",
" 0.0 -0.75 0.0 4.05 -0.9 -2.4\n",
" 0.0 -3.0 -0.85 -0.9 5.75 -1.0\n",
" 0.0 0.0 0.0 -2.4 -1.0 3.4"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#diagonal matrix of weights\n",
"C = diagm(W)\n",
"\n",
"#weighted Laplacians\n",
"K = A'*C*A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Road-network\n",
"An example of using graph theory to solve a difficult problem: navigating a road network.\n",
"\n",
"In a simple example, weights may represent the distance of each edge (i.e. the distance between two nodes); in a sophisticated scenario, weights may be a combination of inputs to determine the expected duration to traverse an edge (such as distance, speed limit, turning cost, vehicle dimensions and weight, expected congestion cost, etc.)\n",
"\n",
"Below is an example of such a graph, calculating expected travel times from 4 nodes to all nodes within an area of Townsville, taking the shortest time from any node as the resultant value of an edge and scaling on a quantize colour scale with 4 breaks."
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# road network visual\n",
"display(\"text/html\",\"\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Max-Flow / Min-Cut Theorem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Max-Flow Min-Cut Theorem represents a network flow optimisation problem where the maximal value of a flow from a Source node $S$ to a Sink node $T$ (i.e. Destination) is equal to the total value of a minimal cut, where edges are only counted if they disconnect the path from a source to a sink.\n",
"\n",
"**Applications**:\n",
"- Distribution of Incoming Web Traffic to Server Applications using [Load Balancing techniques](http://david-kempe.com/publications/load-balancing-final.pdf)\n",
"- Unifying data flows from cloud-based servers using event-driven architectures.\n",
"- Distance of destinations and flow rate of traffic between destinations\n",
"- Representing the electrical flow in a distribution grid\n",
"\n",
"**Terminology and base assumptions**\n",
"1. For a Max-Flow Min-Cut Theorem, we have Graphs $G$, Vertices $v$ and Edges $e$ denoted as: $G(v,e)$\n",
"1. We are only using Directed Graphs to represent the flow of a graph\n",
"1. Distinguished vertices as Source $S$ and Sink $T$.\n",
"1. For any vertices other than $S$ or $T$, everything that flows in has to come out of the vertex.\n",
"\n",
"**Obeying the Conservation Laws with these Constraints**\n",
"1. We can't accumulate more than the incoming flow in the vertices (what goes in must come out)\n",
"1. Obey the Conservation Laws: anything that's not found in the Source ($S$) or Sink ($T$) has to leave the node.\n",
"1. Can have flows that are cyclical, but can't have self-looping vertices\n",
"1. Can increase the flow between vertices by removing specific edges"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Definitions\n",
"\n",
"A flow $f$ is a function defined by the edges on a graph where each edge $f(u,v) \\in E$ has a non-negative Capacity $C(u,v)$ is $\\mathbb{Z}^+$ and is not greater than the Capacity $C(u,v)$ for that edge.\n",
"\n",
"This can be represented in the following form:\n",
"\n",
"$$\n",
"0 \\leq\\,f(u,v)\\,\\leq\\,C(u,v)\\quad\\:\\forall\\:\\text{ edges in }G(u,v)\n",
"$$\n",
"\n",
"For all vertices other than Source node $S$ and Sink node $T$, everything that flows in has to flow out of the vertex, for example:\n",
"\n",
"$$\n",
"\\sum_{a\\,\\in\\,N_{in}(v)} f(a,v) = \\sum_{b\\,\\in\\,N_{out}(v)} f(v,b)\n",
"$$\n",
"\n",
"where: \n",
"- $N_{in}$: set of nodes leading into $v$, and \n",
"- $N_{out}$: set of nodes leading from $v$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Calculating Values of a Flow\n",
"In the 'Max-Flow Min-Cut Theorem', calculating the value of the flow is defined as the total amount of flow from the source $S$ (= total amount of flow to the sink $T$).\n",
"\n",
"$$\n",
"\\begin{vmatrix}{f}\\end{vmatrix}= \\sum_{v\\,\\in\\,N_{out}(S)} f(S,v) - \\sum_{v\\,\\in\\,N_{in}(S)} f(v,S)\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.46780795434228745cx, 0.11164886749653875cy), (-0.42692888776297566cx, 0.8883511325034612cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.36188081165132635cx, 0.0cy), (0.8881966011250105cx, 0.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3092492327039579cx, 1.0cy), (0.36188081165132624cx, 1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.32961909427933683cx, 0.9356578811595333cy), (0.9085664627003893cx, 0.0643421188404667cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9479279657954108cx, -0.9010631350112805cy), (-0.525756244730905cx, -0.09893686498871956cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5257562447309049cx, 0.9010631350112805cy), (0.9479279657954107cx, 0.09893686498871956cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), 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}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.39771306121564626cx, 0.7927141340187933cy), (-0.42692888776297566cx, 0.8883511325034612cy), (-0.4660225438388209cx, 0.7963093699463288cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.7942273390464196cx, -0.03420201433256687cy), (0.8881966011250105cx, 0.0cy), (0.7942273390464196cx, 0.03420201433256687cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.2679115495727354cx, 0.9657979856674331cy), (0.36188081165132624cx, 1.0cy), (0.2679115495727354cx, 1.034202014332567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8120347632292798cx, 0.09045018267559989cy), (0.9085664627003893cx, 0.0643421188404667cy), (0.8514008306818435cx, 0.1463914364239799cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5392561076148643cx, -0.19802144351693604cy), (-0.525756244730905cx, -0.09893686498871956cy), (-0.5997880790649807cx, -0.16616251117476954cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.873896131461335cx, 0.16616251117476954cy), (0.9479279657954107cx, 0.09893686498871956cy), (0.9344281029114514cx, 0.19802144351693604cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4342105263157895cx, 0.75cy), \"(8, 5)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.631578947368421cx, 0.0cy), \"(6, 6)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.24999999999999994cx, 1.0cy), \"(3, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.6447368421052632cx, 0.25cy), \"(2, 2)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.605263157894737cx, -0.25cy), \"(14, 11)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.868421052631579cx, 0.25cy), \"(5, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.4736842105263158cx, 0.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.42105263157894735cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.4736842105263157cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.0cy), 0.044721359549995794w)], 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4736842105263158cx, 0.0cy), \"A\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.42105263157894735cx, 1.0cy), \"B\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, -1.0cy), \"source\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.4736842105263157cx, 1.0cy), \"C\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, 0.0cy), \"sink\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(\"\"))"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"G = SimpleDiGraph(5, 6; seed=18)\n",
"edge_capacity = [8, 6, 3, 2, 14, 5]\n",
"edge_flow = [5, 6, 3, 2, 11, 3]\n",
"node_label = [\"A\", \"B\", \"source\", \"C\", \"sink\"]\n",
"\n",
"flow_order = [\n",
" [(8,0), (6,0), (3,0), (2,0), (14,11), (5,0)],\n",
" [(8,5), (6,6), (3,0), (2,0), (14,11), (5,0)],\n",
" [(8,5), (6,6), (3,3), (2,2), (14,11), (5,0)],\n",
" [(8,5), (6,6), (3,3), (2,2), (14,11), (5,3)]\n",
"]\n",
"\n",
"colours = [\n",
" [colorant\"lightgray\",colorant\"lightgray\",colorant\"lightgray\",colorant\"lightgray\",colorant\"orange\",colorant\"lightgray\"],\n",
" [colorant\"orange\",colorant\"orange\",colorant\"lightgray\",colorant\"lightgray\",colorant\"orange\",colorant\"lightgray\"],\n",
" [colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"lightgray\"],\n",
" [colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"orange\"],\n",
"]\n",
"\n",
"for i in 1:4\n",
" IJulia.clear_output()\n",
" gplot(\n",
" G,\n",
" [6.0,6.5,1.0,15.0,20.0],\n",
" [2.0,3.0,1.0,3.0,2.0], \n",
" nodelabel=node_label, \n",
" edgelabel=flow_order[i],\n",
" edgestrokec=colours[i]\n",
" ) |> display\n",
" sleep(2)\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graph Cut\n",
"A graph cut is a partition of the vertices into two disjoint subsets: a set containing the source and a set containing the sink."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.46780795434228745cx, 0.11164886749653875cy), (-0.42692888776297566cx, 0.8883511325034612cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.36188081165132635cx, 0.0cy), (0.8881966011250105cx, 0.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3092492327039579cx, 1.0cy), (0.36188081165132624cx, 1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.32961909427933683cx, 0.9356578811595333cy), (0.9085664627003893cx, 0.0643421188404667cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9479279657954108cx, -0.9010631350112805cy), (-0.525756244730905cx, -0.09893686498871956cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5257562447309049cx, 0.9010631350112805cy), (0.9479279657954107cx, 0.09893686498871956cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), 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}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.39771306121564626cx, 0.7927141340187933cy), (-0.42692888776297566cx, 0.8883511325034612cy), (-0.4660225438388209cx, 0.7963093699463288cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.7942273390464196cx, -0.03420201433256687cy), (0.8881966011250105cx, 0.0cy), (0.7942273390464196cx, 0.03420201433256687cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.2679115495727354cx, 0.9657979856674331cy), (0.36188081165132624cx, 1.0cy), (0.2679115495727354cx, 1.034202014332567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8120347632292798cx, 0.09045018267559989cy), (0.9085664627003893cx, 0.0643421188404667cy), (0.8514008306818435cx, 0.1463914364239799cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5392561076148643cx, -0.19802144351693604cy), (-0.525756244730905cx, -0.09893686498871956cy), (-0.5997880790649807cx, -0.16616251117476954cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.873896131461335cx, 0.16616251117476954cy), (0.9479279657954107cx, 0.09893686498871956cy), (0.9344281029114514cx, 0.19802144351693604cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4342105263157895cx, 0.75cy), \"(8, 5)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.631578947368421cx, 0.0cy), \"(6, 6)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.24999999999999994cx, 1.0cy), \"(3, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.6447368421052632cx, 0.25cy), \"(2, 2)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.605263157894737cx, -0.25cy), \"(14, 11)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.868421052631579cx, 0.25cy), \"(5, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.4736842105263158cx, 0.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.42105263157894735cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.4736842105263157cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.0cy), 0.044721359549995794w)], 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.5019607843137255,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(1.0,0.0,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4736842105263158cx, 0.0cy), \"A\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.42105263157894735cx, 1.0cy), \"B\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, -1.0cy), \"source\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.4736842105263157cx, 1.0cy), \"C\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, 0.0cy), \"sink\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = SimpleDiGraph(5, 6; seed=18)\n",
"node_label = [\"A\", \"B\", \"source\", \"C\", \"sink\"]\n",
"\n",
"flow_order = [(8,5), (6,6), (3,3), (2,2), (14,11), (5,3)]\n",
"\n",
"edge_colours = [colorant\"orange\",colorant\"orange\",colorant\"lightgray\",colorant\"lightgray\",colorant\"lightgray\",colorant\"lightgray\"]\n",
"node_colours = [colorant\"red\", colorant\"green\", colorant\"red\", colorant\"green\", colorant\"green\"]\n",
"\n",
"gplot(\n",
" G,\n",
" [6.0,6.5,1.0,15.0,20.0],\n",
" [2.0,3.0,1.0,3.0,2.0],\n",
" nodefillc = node_colours,\n",
" nodelabel=node_label, \n",
" edgelabel=flow_order,\n",
" edgestrokec=edge_colours\n",
" ) "
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.46780795434228745cx, 0.11164886749653875cy), (-0.42692888776297566cx, 0.8883511325034612cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.36188081165132635cx, 0.0cy), (0.8881966011250105cx, 0.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.3092492327039579cx, 1.0cy), (0.36188081165132624cx, 1.0cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.32961909427933683cx, 0.9356578811595333cy), (0.9085664627003893cx, 0.0643421188404667cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.9479279657954108cx, -0.9010631350112805cy), (-0.525756244730905cx, -0.09893686498871956cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.5257562447309049cx, 0.9010631350112805cy), (0.9479279657954107cx, 0.09893686498871956cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), 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)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.39771306121564626cx, 0.7927141340187933cy), (-0.42692888776297566cx, 0.8883511325034612cy), (-0.4660225438388209cx, 0.7963093699463288cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.7942273390464196cx, -0.03420201433256687cy), (0.8881966011250105cx, 0.0cy), (0.7942273390464196cx, 0.03420201433256687cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.2679115495727354cx, 0.9657979856674331cy), (0.36188081165132624cx, 1.0cy), (0.2679115495727354cx, 1.034202014332567cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.8120347632292798cx, 0.09045018267559989cy), (0.9085664627003893cx, 0.0643421188404667cy), (0.8514008306818435cx, 0.1463914364239799cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(-0.5392561076148643cx, -0.19802144351693604cy), (-0.525756244730905cx, -0.09893686498871956cy), (-0.5997880790649807cx, -0.16616251117476954cy)]), Compose.LinePrimitive{Tuple{Measures.Measure,Measures.Measure}}(Tuple{Measures.Measure,Measures.Measure}[(0.873896131461335cx, 0.16616251117476954cy), (0.9479279657954107cx, 0.09893686498871956cy), (0.9344281029114514cx, 0.19802144351693604cy)])], Symbol(\"\"))]), List([Compose.Property{Compose.LineWidthPrimitive}(Compose.LineWidthPrimitive[Compose.LineWidthPrimitive(1.3416407864998738mm)]), Compose.Property{Compose.StrokePrimitive}(Compose.StrokePrimitive[Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(1.0,0.6470588235294118,0.0,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0)), Compose.StrokePrimitive(RGBA{Float64}(0.8274509803921568,0.8274509803921568,0.8274509803921568,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4342105263157895cx, 0.75cy), \"(8, 5)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.631578947368421cx, 0.0cy), \"(6, 6)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.24999999999999994cx, 1.0cy), \"(3, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.6447368421052632cx, 0.25cy), \"(2, 2)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.605263157894737cx, -0.25cy), \"(14, 11)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.868421052631579cx, 0.25cy), \"(5, 3)\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.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.4736842105263158cx, 0.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-0.42105263157894735cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((-1.0cx, -1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((0.4736842105263157cx, 1.0cy), 0.044721359549995794w), Compose.CirclePrimitive{Tuple{Measures.Measure,Measures.Measure},Measures.Measure}((1.0cx, 0.0cy), 0.044721359549995794w)], 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}(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.5019607843137255,0.0,1.0)), Compose.FillPrimitive(RGBA{Float64}(0.0,0.5019607843137255,0.0,1.0))])]), 0, false, false, false, false, nothing, nothing, 0.0, Symbol(\"\")), Compose.Context(BBox{l,t,r,b,w,h = 0.0w,0.0h, 1.0w,1.0h, 1.0w,1.0h}, nothing, nothing, nothing, nothing, List([]), List([Compose.Form{Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}}(Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}[Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.4736842105263158cx, 0.0cy), \"A\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-0.42105263157894735cx, 1.0cy), \"B\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((-1.0cx, -1.0cy), \"source\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((0.4736842105263157cx, 1.0cy), \"C\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm)), Compose.TextPrimitive{Tuple{Measures.Length{:cx,Float64},Measures.Length{:cy,Float64}},Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((1.0cx, 0.0cy), \"sink\", Compose.HCenter(), Compose.VCenter(), Compose.Rotation{Tuple{Measures.Length{:w,Float64},Measures.Length{:h,Float64}}}(0.0, (0.5w, 0.5h)), (0.0mm, 0.0mm))], Symbol(\"\"))]), 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": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = SimpleDiGraph(5, 6; seed=18)\n",
"node_label = [\"A\", \"B\", \"source\", \"C\", \"sink\"]\n",
"\n",
"flow_order = [(8,5), (6,6), (3,3), (2,2), (14,11), (5,3)]\n",
"\n",
"edge_colours = [colorant\"lightgray\",colorant\"orange\",colorant\"orange\",colorant\"orange\",colorant\"lightgray\",colorant\"lightgray\"]\n",
"node_colours = [colorant\"red\", colorant\"red\", colorant\"red\", colorant\"green\", colorant\"green\"]\n",
"\n",
"gplot(\n",
" G,\n",
" [6.0,6.5,1.0,15.0,20.0],\n",
" [2.0,3.0,1.0,3.0,2.0],\n",
" nodefillc = node_colours,\n",
" nodelabel=node_label, \n",
" edgelabel=flow_order,\n",
" edgestrokec=edge_colours\n",
" ) "
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.2.0",
"language": "julia",
"name": "julia-1.2"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.2.0"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}