Vpeta drevesa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d0356b4b-3b66-4348-9a70-f772acb4876c",
   "metadata": {},
   "source": [
    "# Disjunktne množice\n",
    "\n",
    "Čeprav poglavje obljublja delo z vpetimi drevesi, se bomo najprej posvetili neki drugi podatkovni strukturi, ki nam bo kasneje prišla prav. Prav pa nam pride v številnih aplikacijah, kjer imamo opravka z združevanjem množic ali kakšnih drugih ekvivalenčnih razredov objektov.\n",
    "\n",
    "Podatkovna struktura disjunktnih množic (*disjoint-set*) hrani množico disjunktnih množic (ali razbitje množice na podmnožice) in omogoča naslednje operacije:\n",
    "\n",
    "- `add(x)`: Doda novo množico $\\{x\\}$ z enim samim elementom.\n",
    "- `find(x)`: Najde množico, ki ji pripada element x.\n",
    "- `union(x,y)`: Združi množici elementov x in y.\n",
    "\n",
    "Poleg disjunktnih množic se za to podatkovno strukturo uporablja tudi izraz **union-find**. Pogosto se problemi začnejo s množicami posameznih elementov, ki jih nato zdržujemo z uporabo funkcij `union` in `find`, zato se bomo omejili na ta primer. Dopolnitev razvitih rešitev s funkcijo `add` za dodajanje novega elementa je enostavna. \n",
    "\n",
    "<img src=\"disjoint-set.svg\" width=\"400px\">\n",
    "\n",
    "Posamezne množice bomo predstavili z drevesi. Koren drevesa pa bo predstavnik posamezne množice. Funkcija `find(x)` bo torej morala poiskati in vrniti koren drevesa, funkcija `union(x,y)` pa združiti dve drevesi v eno. Koren drevesa z elementom x lahko pripnemo kot otroka korenu drevesa z elementom y. Združevanje je torej učinkovito, vendar lahko s takimi združevanji nastanejo zelo izrojena drevesa, zato je časovna zahtevnost operacije `find` linearna.\n",
    "\n",
    "Ker imamo opravka z dvema funkcijama, pri analizi učinkovitosti običajno opazujemo zaporedje $n-1$ združevanj (kar postopoma združi vseh $n$ posameznih elementov v eno samo množico), med tem pa izvedemo še $m \\geq n$ klicev funkcije find."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dd0daee2-cd1a-4486-bb56-c6efa6699700",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <fstream>\n",
    "#include <vector>\n",
    "#include <queue>\n",
    "#include <algorithm>\n",
    "using namespace std;\n",
    "\n",
    "typedef pair<int,int> PII;\n",
    "typedef vector<int> VI;\n",
    "typedef vector<pair<int,int>> VII;\n",
    "typedef vector<vector<int>> VVI;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e0838df4-7f90-48fd-9b27-4484477751f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "template<typename T>\n",
    "void print(const vector<T> &sez) {\n",
    "    for (T x : sez) cout << x << \" \";\n",
    "    cout << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1952375-a776-4d49-87c1-e6551c5e6e28",
   "metadata": {},
   "source": [
    "### Združevanje po velikosti\n",
    "\n",
    "Prva izboljšava temelji na pametnejšem združevanju. Pri združitvi dveh dreves je smiselno manjšega pripeti k večjemu. Velikost drevesa lahko merimo po število vozlišč (*union by size*) ali po oceni višine (*union by rank*). Osredotočili se bomo na prvo možnost, ker dobimo z drugo enake rezultate.\n",
    "\n",
    "Ob vsaki združitvi se višina drevesa lahko poveča za največ 1 (če združujemo enako globoki drevesi). Pri združevanju postane vozlišče manjšega drevesa del vsaj dvakrat večjega združenega drevesa. Zato lahko vsako vozlišče nastopa v največ $O(\\log n)$ združevanjih (sicer bi moralo imeti združeno drevo več kot $n$ vozlišč, kar ni mogoče). Časovna zahtevnost operacije join je $O(1)$, find pa $O(\\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fccbe26-f021-4b8c-92f9-ede1057997e4",
   "metadata": {},
   "source": [
    "### Stiskanje poti\n",
    "\n",
    "Druga možna izboljšava temelji na iskanju korena drevesa (find). Če smo že prehodili dolgo pot, da smo našli koren, bi lahko vsa vozlišča na poti tudi povezali direktno nanj, da nam kasneje ne bo treba tega početi ponovno.\n",
    "\n",
    "Če imamo opravka samo z operacijami find (brez združevanj), je amortizirana časovna zahtevnost operacije find $O(1)$ (v zaporedju $m \\geq n$ find-ov). V zaporedju operacij find bomo vsako vozlišče pri iskanju korena prehodili enkrat (morda jih bomo prehodili cel kup že v prvi operaciji in kasneje nobenega, ali pa v vsaki operaciji nekaj, skupaj pa ravno vse).\n",
    "\n",
    "Če upoštevamo še združevanja, je amortizirana analiza nekoliko kompleksnejša. Povejmo samo, da je časovna zahtevnost postopnega združevanja vseh elementov v eno množico ($n-1$ operacij join) z $m \\geq n$ vmesnimi operacijami find enaka $O(m \\log n)$. Amortizirana zahtevnost operacije find je torej $O(\\log n)$. S strategijo združevanja po velikosti smo dosegli enako zahtevnost, ki pa ni bila amortizirana."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13ead3c3-a83e-4ed2-842e-1139d60fbd1c",
   "metadata": {},
   "source": [
    "### Skupna rešitev\n",
    "\n",
    "Obe izboljšavi lahko tudi združimo, saj ne vplivata ena na drugo. Združevanje po velikosti skrajša poti, ki jih stiskanje poti kasneje še dodatno skrajša. Stiskanje poti ne spremeni velikosti drevesa, temveč ga zgolj preuredi, zato ne vpliva na združevanje po velikosti.\n",
    "\n",
    "Rezultat je podatkovna struktura s skoraj konstantnimi amortiziranimi časovnimi zahtevnostmi posameznih operacij. Časovna zahtevnost je $O(m \\log^* n)$, še tesnejša meja pa je $O(m \\alpha(n))$. Obe funkciji (iterirani logaritem in inverzna Ackermannova funkcija) rasteta izjemno počasi in sta praktično konstantni za vse razumne vrednost, npr. $n = 2^{65536} \\approx 10^{20000}, \\log_2^*(n) = 5, \\alpha(n) = 4$. Amortizirana časovna zahtevnost posamezne operacije v procesu združevanja posameznih elementov v eno končno množico je torej praktično konstantna!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fa32e385-3bc3-4294-a784-70e164581953",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DisjointSet {  // Union-Find\n",
    "public:\n",
    "    vector<int> parent, size;\n",
    "    DisjointSet(int n) {\n",
    "        parent = vector<int>(n);\n",
    "        size = vector<int>(n);\n",
    "        for (int i=0;i<n;i++) {  // individual sets\n",
    "            parent[i] = i;\n",
    "            size[i] = 1;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    int root(int x) {  // find\n",
    "        if (parent[x]==x) return x;  // reached the root        \n",
    "        int r = root(parent[x]);\n",
    "        parent[x] = r;  // path compression\n",
    "        return r;\n",
    "    }\n",
    "\n",
    "    void join(int x, int y) {  // union by size\n",
    "        x=root(x); y=root(y);  // replace by roots\n",
    "        if (x==y) return;\n",
    "        if (size[x]>size[y]) swap(x,y);  // make x smaller\n",
    "        parent[x] = y;  // attach to larger root\n",
    "        size[y] += size[x];\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5e14dcce-7a9e-4ad0-8f0d-746eaf0da320",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "DisjointSet ds(10);\n",
    "ds.join(3,4); ds.join(5,7); ds.join(0,3); ds.join(8,9); ds.join(7,9);\n",
    "cout << (ds.root(3) == ds.root(7)) << endl;\n",
    "cout << (ds.root(5) == ds.root(8)) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1294c700-b045-415f-8840-ae0636ef3fd1",
   "metadata": {},
   "source": [
    "# Minimalno vpeto drevo\n",
    "\n",
    "**Vpeto drevo** (*spanning tree*) grafa G je drevo T, ki vključuje vsa vozlišča grafa G in podmnožico njegovih povezav. **Minimalno vpeto drevo** (*minimum spanning tree, MST*) je tisto vpeto drevo, ki ima najmanjšo vsoto uteži povezav. Če imamo opravka z več komponentami, govorimo o minimalnem povezanem gozdu. Tam za vsako povezano komponento ločeno poiščemo minimalno vpeto drevo.\n",
    "\n",
    "<img src=\"mst.svg\" width=\"300px\">\n",
    "\n",
    "Vpeto drevo lahko enostavno poiščemo s preiskovanjem v širino ali globino iz poljubnega vozlišča. Kako pa poiščemo minimalno vpeto drevo?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "69b92f20-ece6-4720-ba95-d2dcf8f88023",
   "metadata": {},
   "outputs": [],
   "source": [
    "ifstream fin(\"mst.txt\");\n",
    "int n,m;\n",
    "fin >> n >> m;\n",
    "vector<VI> edges;\n",
    "vector<VII> adj(n);\n",
    "for (int i=0;i<m;i++) {\n",
    "    int a,b,w;\n",
    "    fin >> a >> b >> w;\n",
    "    edges.push_back({a,b,w});\n",
    "    adj[a].push_back({b,w});\n",
    "    adj[b].push_back({a,w});\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abae2b4c-6eda-4588-820a-18397bf278a7",
   "metadata": {},
   "source": [
    "### Prerezna lastnost\n",
    "\n",
    "Razbitju vozlišč grafa na dve disjunktni množici pravimo **prerez grafa** (*cut*). Povezavam s krajišči v različnih delih razbitja pa **prerezne povezave** (*cut-edge, cut-set*).\n",
    "\n",
    "Prerezna lastnost (*cut property*) pravi, da je najmanjša prerezna povezava vedno del nekega minimalnega vpetega drevesa (ne glede na izbrani prerez). Naj bo $e$ najmanjša prerezna povezava v razbitju vozlišč na množici $A$ in $B=V-A$. Recimo, da ta povezava ni del nobenega minimalnega vpetega drevesa. Potem mora v minimalnem vpetem drevesu obstajati neka druga povezava $e'$ med $A$ in $B$. Vemo, da je $w(e) \\leq w(e')$. Povezavo $e'$ lahko zamenjamo z $e$ in pri tem ohranimo ali zmanjšamo vsoto povezav v vpetem drevesu."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92005221-09a9-4f2c-ad60-c1131df36845",
   "metadata": {},
   "source": [
    "## Prim\n",
    "\n",
    "Primov algoritem je požrešen algoritem, ki gradi minimalno vpeto drevo s širjenjem od izhodiščenega vozlišča navzven proti sosedom. Za izhodišče lahko uporabimo poljubno vozlišče, saj morajo biti vsa del minimalnega vpetega drevesa. Oglejmo si prerez grafa na množico A, ki vključuje vsa vozlišča do sedaj zgrajenega drevesa in množico B, ki vsebuje preostala. Iz prerezne lastnosti sledi, da je najmanjša povezava med A in B del nekega minimalnega vpetega drevesa. Zato jo lahko dodamo v drevo in ponovimo enak razmislek."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "035d81c7-64bc-4c0d-8ee2-9445503fb891",
   "metadata": {},
   "source": [
    "Analizirajmo časovno zahtevnost takega postopka. V drevo moramo dodati $n$ vozlišč, vsakič pa moramo obravnavati $m$ povezav, da najdemo najmanjšo med že dodanimi vozlišči in preostankom. Časovna zahtevnost bi bila $O(nm)$.\n",
    "\n",
    "Lahko pa jo izboljšamo. Za vsako še nedodano vozlišče bomo vzdrževali njegovo razdaljo do že zgrajenega drevesa. Na začetku so vse te razdalje enake $\\infty$, razen za začetno vozlišče, ki ima razdaljo 0. Na vsakem koraku poiščemo vozlišče z najmanjšo razdaljo, ga dodamo v drevo in posodobimo razdalje do drevesa vseh njegovih sosedov. Vse skupaj bomo obravnavali $O(m)$ povezav. Na vsakem koraku dodajanja novega vozlišča v drevo pa bomo iskali vozlišče z najmanjšo razdaljo do drevesa. Časovna zahtevnost je $O(n^2 + m) = O(n^2)$.\n",
    "\n",
    "Namesto večkratnega iskanja vozlišča z najmanjšo razdaljo lahko hranimo vozlišča v prioritetni vrsti podobno kot v Dijkstrovem algoritmu. Posodobljene razdalje dodajamo v vrsto, če dobimo iz vrste kakšno staro vrednost, pa jo ignoriramo. Časovna zahtevnost take implementacije je $O(m \\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "eb5d12da-3e6f-4708-af10-047d302f24f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "int Prim(int n, vector<VII> &adj, vector<PII> &mst) {\n",
    "    vector<int> dist(n,-1);  // distance from the tree\n",
    "    vector<int> done(n), parent(n);\n",
    "    int cost=0;\n",
    "    priority_queue<PII, vector<PII>, greater<PII>> pq;\n",
    "    dist[0]=0; pq.push({0,0});\n",
    "    while (!pq.empty()) {\n",
    "        auto [d,x]=pq.top(); pq.pop();\n",
    "        if (done[x]) continue;  // ignore old items in queue\n",
    "        cost+=d;\n",
    "        done[x]=1;\n",
    "        for (auto [y,w] : adj[x]) if (!done[y]) {  // update unfinished neighbors\n",
    "            if (dist[y]==-1 || w<dist[y]) {  // new or smaller distance\n",
    "                dist[y]=w; pq.push({w,y});\n",
    "                parent[y]=x;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    for (int x=1;x<n;x++) {  // skip root\n",
    "        mst.push_back({x,parent[x]});\n",
    "    }\n",
    "    return cost;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ffcc8c46-290c-47f1-b824-4fd94acab0c2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n",
      "1 0\n",
      "2 1\n",
      "3 2\n",
      "4 3\n",
      "5 2\n",
      "6 5\n",
      "7 6\n",
      "8 2\n"
     ]
    }
   ],
   "source": [
    "vector<PII> mst;\n",
    "cout << Prim(n, adj, mst) << endl;\n",
    "for (PII edge : mst) cout << edge.first << \" \" << edge.second << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9df08d48-7a3a-44e8-b9f3-94ba97bb6e27",
   "metadata": {},
   "source": [
    "## Kruskal\n",
    "\n",
    "Kruskalov algoritem je prav tako požrešne narave. Začne z množico vozlišč in dodaja povezave od manjših proti večjim povezavam glede na uteži. Pravzaprav postopoma pretvarja gozd z več manjšimi drevesi v eno veliko drevo. Vsako povezavo $(x,y)$ doda, če njena vključitev ne ustvari cikla. Povedano drugače, vozlišči $x$ in $y$ ne smeta pripadati istemu drevesu oz. povezani komponenti.\n",
    "\n",
    "Vodi ta postopek res do optimalne rešitve? Tudi tu si lahko pomagamo s prerezno lastnostjo. Recimo, da smo že sestavili nek gozd in želimo dodati povezavo $(x,y)$. Naj bo drevo z vozliščem $x$ množica $A$, vsa ostala vozlišča pa množica $B$. Povezava $(x,y)$ je globalno najcenejša nedodana povezava in zato tudi najcenejša povezava med množicama $A$ in $B$. Torej jo lahko gotovo dodamo v vpeto drevo in pri tem ne bomo zgrešili optimalne rešitve.\n",
    "\n",
    "Za začetek moramo povezave urediti po velikosti, kar zahteva $O(m \\log m)$ časa. Nato pa obravnavamo po vrsti vseh $m$ povezav in za vsako preverjamo, ali sta krajišči del iste povezane komponente. Povezano komponento lahko vsakič znova določimo z uporabo preiskovanja v širino ali globino, ki ima časovno zahtevnost $O(m)$. Časovna zahtevnost celega postopka bi bila $O(m \\log m + m m) = O(m^2)$.\n",
    "\n",
    "Lahko pa uporabimo podatkovno strukturo disjunktnih množic, ki predstavljajo povezane komponente. Posamezna vozlišča združujemo v povezane komponente, da dobimo na koncu eno samo komponento, ki je minimalno vpeto drevo. Operacije v strukturi disjunktnih množic so praktično konstantne in zanemerljive v primerjavi z začetnim urejanjem povezav. Časovna zahtevnost je $O(m \\log m + m \\alpha(n)) = O(m \\log m) = O(m \\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "15a3c499-965b-407c-b15c-c41392cbab75",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool cmpW(VI e1, VI e2) { return e1[2] < e2[2]; }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "3c6befec-284f-44dc-be10-a9ba0b55bbd3",
   "metadata": {},
   "outputs": [],
   "source": [
    "int Kruskal(int n, vector<VI> &edges, vector<PII> &mst) {\n",
    "    sort(edges.begin(), edges.end(), cmpW);  // sort by weights\n",
    "    DisjointSet ds(n);\n",
    "    int cost=0;\n",
    "    for (VI e : edges) {\n",
    "        int a=e[0], b=e[1], w=e[2];\n",
    "        if (ds.root(a)==ds.root(b)) continue;  // same component?\n",
    "        ds.join(a,b);\n",
    "        cost+=w;\n",
    "        mst.push_back({a,b});\n",
    "    }\n",
    "    return cost;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "9dd17393-bf4f-4c59-986c-b6f2d4dd1d15",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n",
      "7 6\n",
      "8 2\n",
      "6 5\n",
      "0 1\n",
      "2 5\n",
      "2 3\n",
      "0 7\n",
      "3 4\n"
     ]
    }
   ],
   "source": [
    "vector<PII> mst;\n",
    "cout << Kruskal(n, edges, mst) << endl;\n",
    "for (PII edge : mst) cout << edge.first << \" \" << edge.second << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49346c6d-3125-4859-9f10-b7b6f33d9f21",
   "metadata": {},
   "source": [
    "## Steinerjevo drevo v grafu\n",
    "\n",
    "V problemu minimalnega vpetega drevesa smo morali poiskati podmnožico povezav z najmanjšo vsoto, ki med seboj povezujejo vsa vozlišča grafa v obliki drevesa. Problem lahko posplošimo tako, da zahtevamo, da je med seboj povezana samo neka izbrana podmnožica vozlišč (ki jim rečemo terminali, njihovo število pa bomo označili s $t$), vključuje pa lahko tudi druga vozlišča\n",
    "\n",
    "- $t = n$: Če so vsa vozlišča terminali, imamo opravka s problemom minimalnega vpetega drevesa.\n",
    "- $t = 2$: Če moramo povezati samo dve vozlišči, imamo opravka s problemom najkrajše poti.\n",
    "- V splošnem se temu problemu reče Steinerjevo drevo v grafu. Vozliščem, ki so del rešitve (drevesa), čeprav niso terminali, pa Steinerjeve točke.\n",
    "\n",
    "Problem Steinerjevega drevesa spada med težke probleme, za katere ne poznamo algoritmov s polinomsko zahtevnostjo v odvisnosti od števila terminalov $t$. Soroden geometrijski problem Steinerjevega drevesa v ravnini, kjer želimo povezati $t$ točk z ravnimi črtami, pri čemer lahko dodajamo vmesne točke/križišča, je prav tako težek.\n",
    "\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/e/e4/Steiner_4_points.svg\" >"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}