Grafi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d0356b4b-3b66-4348-9a70-f772acb4876c",
   "metadata": {},
   "source": [
    "# Grafi\n",
    "\n",
    "Graf $G$ je abstraktni podatkovni tip, ki ga sestavljata množica **vozlišč** (*nodes, vertices, points*) $V$ in množica **povezav** (*edges, links*) $E$, ki predstavljajo relacije med pari vozlišč. Vozliščema, ki sestavljata povezavo, rečemo **krajišči** (*endpoints*). Vozlišča in povezave lahko hranijo tudi kakšne dodatne lastnosti.\n",
    "\n",
    "<img alt=\"Graf\" src=\"graph.svg\" width=\"300px\"/>\n",
    "\n",
    "Običajne operacije, ki jih želimo izvajati na grafu so:\n",
    "\n",
    "- dodajanje/odstranjevanje vozlišča/povezave\n",
    "- nastavljanje/ugotavljanje lastnosti vozlišča/povezave\n",
    "- ugotavljanje sosednosti dveh vozlišč\n",
    "- iskanje vseh sosednjih vozlišč\n",
    "- ...\n",
    "\n",
    "Kadar z grafom modeliramo nek resničen pojav ali proces, namesto grafa pogosto uporabimo izraz *omrežje (network)*. Grafe lahko uporabimo za modeliranje številnih procesov, kot so razna družbena ali komunikacijska omrežja, omrežja soavtorstev ali celo biološka omrežja, ki modelirajo razne kemijske procese. Mi pa se bomo ukvarjali samo s strukturami brez njihovega ozadja, torej z grafi.\n",
    "\n",
    "## Terminologija\n",
    "\n",
    "Glavni lastnosti grafa sta število vozlišč $n = |V|$ in število povezav $e = |E|$ (za število povezav bomo včasih uporabljali tudi $m$).\n",
    "\n",
    "Poznamo več vrst grafov glede na njihove lastnosti:\n",
    "\n",
    "- **Neusmerjeni** (*undirected*) grafi vsebujejo same neusmerjene povezave, ki predstavljajo simetrične relacije, kjer vrstni red krajišč ni pomemben, npr. med dvema bratoma. **Usmerjeni** (*directed*) grafi (*digraphs*) pa so sestavljeni iz usmerjenih povezav, ki predstavljajo asimetrično relacijo, npr. od otroka k staršu. Te običajno ponazorimo z puščicami.\n",
    "- Glede na lastnost povezav ločimo med **neuteženimi** (*unweighted*) in **uteženimi** (*weighted*) grafi. V neuteženih grafih so vse povezave enakovredne, v uteženih pa vsaki povezavi priredimo neko numerično vrednost, ki ji rečemo utež, in lahko predstavlja npr. dolžino, ceno, ...\n",
    "- **Enostavni** (*simple*) grafi ne vsebujejo **zank** (*loop*), ki povezujejo vozlišče s samim seboj, in **vzporednih povezav** (*multiple/parallel edges*) med istimi pari vozlišč.\n",
    "- Glede na prisotnost ciklov v grafih poznamo **aciklične** (*acyclic*) in **ciklične** (*cyclic*) grafe.\n",
    "- Grafe precej grobo ločujemo tudi po razmerju med številom povezav in številom vozlišč. V **gostih** (*dense*) grafih je število vozlišč velikostnega reda, ki je blizu maksimalnemu številu možnih povezav, $e = O(n^2)$. V **redkih** (*sparse*) grafih pa je število povezav linearno odvisno od števila vozlišč $e = O(n)$.\n",
    "\n",
    "Oglejmo si še nekaj drugih terminov povezanih z grafi:\n",
    "\n",
    "- Tako kot pri drevesih, tudi v grafih poznamo **stopnjo** (*degree*) vozlišča, ki je enaka številu povezav, ki vključujejo to vozlišče. Če govorimo o stopnji grafa (kar bomo označevali z $d$), pa mislimo največjo stopnjo njegovega vozlišča. V usmerjenih grafih ločujemo **vhodno** in **izhodno** stopnjo (*indegree/outdegree*), ki sta število povezav, ki kažejo v vozlišče oz. izven njega.\n",
    "- Dve vozlišči sta **sosednji** (*adjacent*) oz. **soseda**, če ju povezuje katera izmed povezav v grafu. Množici sosednjih vozlišč izbranega vozlišča rečemo tudi soseščina (*neighbourhood*).\n",
    "\n",
    "Poleg že omenjenih splošnih vrst grafov, poznamo tudi več razredov grafov, ki imajo podobne strukturne lastnosti. Poznamo:\n",
    "\n",
    "- **drevesa** (*trees*), ki so v kontekstu novih terminov pravzaprav aciklični povezani neusmerjeni graf\n",
    "- **polne grafe** (*complete graph*), ki vsebujejo vse možne povezave\n",
    "- **regularne grafe** (*regular graph*), v katerih imajo vsa vozlišča enako stopnjo\n",
    "- **dvodelne grafe** (*bipartite graph*), ki so sestavljeni iz dveh skupin vozlišč, povezave pa potekajo samo med obema skupinama\n",
    "- ...\n",
    "\n",
    "Na grafih nas pogosto zanimajo premiki med sosednjimi vozlišči:\n",
    "\n",
    "- **Sprehod** (*walk*) je poljubno zaporedje vozlišč, med katerimi se premikamo po povezavah v grafu. Če obstaja sprehod med dvema vozliščema, bomo rekli, da sta **povezani**. Spomnimo se, da če sta povezani neposredno z eno samo povezavo, jima rečemo tudi sosednji.\n",
    "- **Obhod** (*closed walk*) je sprehod, ki se začne in konča v istem vozlišču.\n",
    "- **Steza** (*trail*) je sprehod brez ponovljenih povezav.\n",
    "- **Pot** (*path*) je sprehod brez ponovljenih vozlišč. Uporablja se nekoliko nekonsistentno, npr. za sprehod. V nekaterih primerih pa je to celo nepomembno - najkrajša pot v pozitivno uteženem grafu bo zagotovo pot in ne sprehod, kjer bi se kaj ponavljalo.\n",
    "- **Cikel** (*cycle*) je obhod brez ponovljenih vmesnih vozlišč (z izjemo začetnega in končnega, ki sta enaka).\n",
    "- V angleščini se pojavlja tudi termin *tour*, ki pa nima poenotene definicije (npr. knight's tour, Euler tour). Običajno pomeni, da zaporedje premikov obišče celoten graf (npr. vsa vozlišča, vse povezave) ob možnih dodatnih omejitvah (npr. vsako povezavo samo enkrat, vrne se na izhodišče)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b8e2b72-0048-4ee8-b87b-2846544bfb06",
   "metadata": {},
   "source": [
    "## Predstavitve\n",
    "\n",
    "Strukturo grafa, ki jo definirajo vozlišča in povezave, moramo nekako predstaviti oz. shraniti, da bomo lahko na njej izvajali kakšne izračune. Glede na funkcionalnost, ki jo potrebujemo, poznamo tri pogoste načine predstavitve grafov. Če je treba, pa si lahko pomagamo kar z več različnimi predstavitvami sočasno."
   ]
  },
  {
   "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": "d21acb93-e59d-4d05-aae2-6f11c78775e1",
   "metadata": {},
   "source": [
    "- **Seznam povezav** (*edge list*) je najbolj enostavna predstavitev. Vse povezave v grafu preprosto shranimo v seznam. Ta predstavitev bo primerna, če želimo obravnavati vse povezave ne glede na vrstni red."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "95de136a-b584-460f-9438-ef99593e45a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "VII read_graph(string fname, int &n, int &m) {\n",
    "    ifstream fin(fname);\n",
    "    fin >> n >> m;\n",
    "    vector<PII> povezave;\n",
    "    for (int i=0;i<m;i++) {\n",
    "        int a,b;\n",
    "        fin >> a >> b;\n",
    "        povezave.push_back({a,b});\n",
    "    }\n",
    "    fin.close();\n",
    "    return povezave;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9d085d6f-9647-40a3-8f9c-60f6a4a20a99",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0,1) (0,4) (1,3) (1,4) (1,5) (1,7) (2,3) (2,5) (4,5) (6,7) \n"
     ]
    }
   ],
   "source": [
    "int n,m;\n",
    "vector<PII> povezave = read_graph(\"graph.txt\",n,m);\n",
    "for (auto [a,b] : povezave) cout << '(' << a << ',' << b << ')' << ' ';\n",
    "cout << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1e54f7c-f661-4d09-ac05-bb5065c929dd",
   "metadata": {},
   "source": [
    "- **Seznam sosedov** (*adjacency list*) hrani za vsako vozlišče seznam njegovih sosedov. Kadar se premikamo po grafih od enega vozlišča k drugemu, nam to pride zelo prav."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "856485ae-e68b-49f6-8278-9ac8859d37b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "VVI adjacency_list(VII &edge_list, int n, bool dir=false) {\n",
    "    vector<VI> adj(n);\n",
    "    for (auto [a,b] : edge_list) {\n",
    "        adj[a].push_back(b);\n",
    "        if (!dir) adj[b].push_back(a);\n",
    "    }\n",
    "    return adj;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "bc221eec-1aa8-4ab7-a939-76896290b668",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: 1 4 \n",
      "1: 0 3 4 5 7 \n",
      "2: 3 5 \n",
      "3: 1 2 \n",
      "4: 0 1 5 \n",
      "5: 1 2 4 \n",
      "6: 7 \n",
      "7: 1 6 \n"
     ]
    }
   ],
   "source": [
    "vector<VI> sosedi = adjacency_list(povezave, n);\n",
    "for (int i=0;i<n;i++) {\n",
    "    cout << i << \": \";\n",
    "    print(sosedi[i]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03f2418b-528b-45b2-84eb-37f1e2ad3aff",
   "metadata": {},
   "source": [
    "- **Matrika sosednosti** (*adjacency matrix*) je namenjena učinkovitemu preverjanju sosednosti dveh vozlišč. Sestavimo namreč matriko $M$, kjer na mestu $M_{x,y}$ hranimo informacijo o prisotnosti ali teži povezave med vozliščema $x$ in $y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5cefd46c-a944-40be-9882-e5862fbd56ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "VVI adjacency_matrix(VII &edge_list, int n) {\n",
    "    vector<VI> mat(n, vector<int>(n));\n",
    "    for (auto [a,b] : edge_list) {\n",
    "        mat[a][b] = 1;\n",
    "        mat[b][a] = 1;\n",
    "    }\n",
    "    return mat;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1aaf320f-9cd8-492f-baa7-60be7d17dfd3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 0 0 1 0 0 0 \n",
      "1 0 0 1 1 1 0 1 \n",
      "0 0 0 1 0 1 0 0 \n",
      "0 1 1 0 0 0 0 0 \n",
      "1 1 0 0 0 1 0 0 \n",
      "0 1 1 0 1 0 0 0 \n",
      "0 0 0 0 0 0 0 1 \n",
      "0 1 0 0 0 0 1 0 \n"
     ]
    }
   ],
   "source": [
    "vector<VI> sosednost = adjacency_matrix(povezave, n);\n",
    "for (int i=0;i<n;i++) {\n",
    "    print(sosednost[i]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac7da855-8f09-4661-83f3-a31517eaf3c1",
   "metadata": {},
   "source": [
    "Predstavitev s seznami povezav ali sosedov bi lahko nadgradili z uporabo množic. Namesto v seznamu hranimo povezave ali sosede v množicah, ki so implementirane z razpršeno tabelo ali kakšno uravnotežene drevesno strukturo.\n",
    "\n",
    "Omenjene predstavitve imajo svoje prednosti in slabosti. Primerjajmo jih med seboj glede na prostorsko zahtevnost in časovne zahtevnosti nekaterih operacij na enostavnih grafih.\n",
    "\n",
    "<table>\n",
    "    <th><td>seznam povezav</td><td>seznam sosedov</td><td>matrika sosednosti</td></th>\n",
    "    <tr><td>Prostorska zahtevnost</td><td>$O(e)$</td><td>$O(n+e)$</td><td>$O(n^2)$</td></tr>\n",
    "    <tr><td>Dodajanje povezave</td><td>$O(1)$</td><td>$O(1)$</td><td>$O(1)$</td></tr>\n",
    "    <tr><td>Brisanje povezave</td><td>$O(e)$</td><td>$O(n)$</td><td>$O(1)$</td></tr>\n",
    "    <tr><td>Dodajanje vozlišča</td><td>$O(1)$</td><td>$O(1)$</td><td>$O(n^2)$</td></tr>\n",
    "    <tr><td>Brisanje vozlišča</td><td>$O(e)$</td><td>$O(e)$</td><td>$O(n^2)$</td></tr>\n",
    "    <tr><td>Sosednost vozlišč</td><td>$O(e)$</td><td>$O(n)$</td><td>$O(1)$</td></tr>\n",
    "    \n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa13b870-f86a-4831-bdb1-645af5800748",
   "metadata": {},
   "source": [
    "## Preiskovanje grafov\n",
    "\n",
    "Preiskovanje grafa (*graph traversal/search*) je sistematičen postopek, ki obišče vsa vozlišča grafa v nekem vrstnem redu. Poznamo dve pogosti vrsti preiskovanj."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fbe6254-a216-4c75-8dfc-4e46bc19ffe9",
   "metadata": {},
   "source": [
    "### Preiskovanje v širino (*breadth-first search, BFS*)\n",
    "\n",
    "Preiskovanje v širino preiskuje vozlišča podobno kot nivojski obhod v drevesih, le da se izogiba povezavam, ki vodijo do že obiskanih vozlišč. Najprej obišče začetno vozlišče, nato njegove sosede, njihove sosede, itd."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d2207e84-99fb-4bb7-a7b1-c9718ec56bbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "void BFS(int x, vector<VI> &adj, vector<int> &vis, vector<int> &seq) {\n",
    "    queue<int> q;\n",
    "    q.push(x); vis[x]=1;\n",
    "    while (!q.empty()) {\n",
    "        x=q.front(); q.pop();\n",
    "        seq.push_back(x);\n",
    "        for (int y : adj[x]) if (vis[y]==0) {\n",
    "            q.push(y); vis[y]=1;\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d890ddf6-4d31-4287-aeb1-4b25608dd430",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 4 3 5 7 2 6 \n"
     ]
    }
   ],
   "source": [
    "vector<int> visB(n), seqB;\n",
    "BFS(0,sosedi,visB,seqB);\n",
    "print(seqB);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9583f211-98d6-487a-8c4f-365c495a16d3",
   "metadata": {},
   "source": [
    "Iskanje v širino ima to lepo lastnost, da obiskuje vozlišča po nivojih od bližjih proti bolj oddaljenim. Z minimalno prilagoditvijo ga lahko uporabimo za računanje *najkrajših poti* iz začetnega vozlišča do vseh ostalih vozlišč v neuteženem grafu, kjer je dolžina poti definirana s številom povezav na njej!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01f23cd1-096d-42af-a376-a57eef6d7a55",
   "metadata": {},
   "source": [
    "### Preiskovanje v globino (*depth-first search, DFS*) \n",
    "\n",
    "Preiskovanje v globino je podobno prememu obhodu v drevesu, ki se izogiba povezam do že obiskanih vozlišč. Najprej obišče začetno vozlišče. Nato izvede preiskovanje v globino na prvem otroku. Ko se to zaključi in če drugi otrok še ni bil obiskan, izvede preiskovanje v globino še iz drugega otroka itd."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "edf5e19d-1ed3-4cf9-aaa1-78a61e2bcb97",
   "metadata": {},
   "outputs": [],
   "source": [
    "void DFS(int x, vector<VI> &adj, vector<int> &vis, vector<int> &seq) {\n",
    "    seq.push_back(x);\n",
    "    vis[x]=1;\n",
    "    for (int y : adj[x]) if (vis[y]==0) {\n",
    "        DFS(y, adj, vis, seq);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "712fa305-3cfd-4d07-95d3-448d4befeed5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 3 2 5 4 7 6 \n"
     ]
    }
   ],
   "source": [
    "vector<int> visD(n), seqD;\n",
    "DFS(0,sosedi,visD,seqD);\n",
    "print(seqD);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06083087-c67c-4084-bbf4-3ba7d0564839",
   "metadata": {},
   "source": [
    "Oba opisana postopka obiščeta samo del grafa, ki je dosegljiv iz začetnega vozlišča. Tej množici vozlišč v neusmerjenem grafu, ki so vsa povezana med seboj, rečemo **povezana komponenta** grafa (*connected component*). Za iskanje povezanih komponent lahko uporabimo kateregakoli od omenjenih postopkov za preiskovanje.\n",
    "\n",
    "Prostorska zahtevnost obeh preiskovanj je $O(n)$. Časovno zahtevnost bi lahko ocenili z $O(n^2)$, vendar smo lahko bolj natančni z $O(e)$, ker bomo vsako povezavo obravnavali največ dvakrat (enkrat iz vsakega krajišča)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fadcf5c7-439d-43b7-9a3c-4f4b7132d7a9",
   "metadata": {},
   "source": [
    "#### Drevo preiskovanja v globino\n",
    "\n",
    "Tudi iskanje v globino ima svoje lepe lastnosti. Prva je jedrnatost. Druga pa je v strukturi povezav, ki jih postopek obišče med preiskovanjem. Prehojene povezave bodo imele obliko drevesa (to sicer velja tudi za iskanje v širino). Poleg tega pa bodo vse ostale povezave v grafu vedno povezovale vozlišča z nekim svojim prednikom (*back-edge*) ali potomcem (*forward-edge*) v drevesu. Nemogoče je, da bi obstajala povezava med dvema poddrevesoma (*cross-edge*). Razmislite, zakaj je temu tako. To lastnost izkoriščajo pomembni algoritmi za iskanje *mostov*, *prereznih vozlišč* in *močno povezanih komponent*. Razmislite tudi, kakšne povezave lahko nastopajo v drevesu preiskovanja v globino na usmerjenem grafu."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "734f2a19-d440-4a09-beb7-51abcb770419",
   "metadata": {},
   "source": [
    "## Detekcija ciklov\n",
    "\n",
    "Podan imamo graf, za katerega ne vemo, ali vsebuje kakšen cikel ali ne. Ugotovili bi radi prisotnost cikla in tudi našli konkreten primer cikla v grafu. Problem se nekoliko razlikuje med neusmerjenimi in usmerjenimi grafi. Če bi vsako neusmerjeno povezavo modelirali z dvema nasproti usmerjenima, bi vsaka povezava predstavljala cikel, česar nočemo.\n",
    "\n",
    "Oglejmo si najprej primer neusmerjenega grafa. Pri razmisleku nam bo prav prišlo drevo preiskovanja v globino. Cikel bo v tem drevesu izgledal tako, da bo obstajala povezava med dvema vozliščema, ki imata relacijo prednik-potomec. To povezavo bomo pri preiskovanu v globino našli takrat, ko bomo obravnavali neko vozlišče $x$ in našli povezavo do nekega že obiskanega prednika $y$. Vozlišča na poti od $x$ proti $y$ bodo formirala cikel, ker med njima obstaja pot po drevesu poleg tega pa še novo odkrita direktna povezava. Prav nam bo prišlo, če bi drevo preiskovanja v globino hranili v obliki tabele staršev za vsako vozlišče. Če je ta vrednost nenastavljena (npr. -1), je vozlišče še neobiskano, koren pa naj ima za starša kar samega sebe. Tako lahko za izgradnjo cikla preprosto sledimo tem starševskim povezavam od $x$ do $y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "536fc13b-4ea9-4029-bf22-8f46971e86a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "int cycle(int x, vector<VI> &adj, vector<int> &par, vector<int> &cyc) {\n",
    "    if (par[x]==-1) par[x]=x;\n",
    "    for (int y : adj[x]) if (y!=par[x]) {\n",
    "        if (par[y]!=-1) {  // cikel\n",
    "            for (int z=x; z!=y; z=par[z]) cyc.push_back(z);\n",
    "            cyc.push_back(y);\n",
    "            return 1;\n",
    "        }\n",
    "        par[y]=x;\n",
    "        if (cycle(y,adj,par,cyc)) return 1;\n",
    "    }\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "306d3d67-a45b-406e-88bd-402f87d7472d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5 2 3 1 \n"
     ]
    }
   ],
   "source": [
    "vector<int> vis(n), par(n,-1), cyc;\n",
    "cout << cycle(0,sosedi,par,cyc) << endl;\n",
    "print(cyc);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70dbc74d-240b-45c0-9260-98a52790ec1e",
   "metadata": {},
   "source": [
    "V usmerjenem grafu je situacija nekoliko drugačna. Povezave na ciklu morajo kazati v isto smer. Če ponovno razmislimo o situaciji na drevesu preiskovanja v globino, bo cikel tudi tu nastal s povezavo od nekega vozlišča $x$ do njegovega prednika $y$. Povezave iz vozlišča $x$ do nekega drugega dela drevesa, ki je že bil obiskan, ne vzpostavijo cikla zaradi usmerjenosti. Poleg obiskanosti vozlišč bomo hranili še informacijo o vozliščih na poti od korena do trenutnega vozlišča. S tem lahko učinkovito ugotovimo, ali je vozlišče prednik $x$-a. Pri sestavljanju cikla bomo zaradi premikanja proti prednikom cikel sestavili v obratnem vrstnem redu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "358d1e88-41da-4565-ab1a-42c90f85b362",
   "metadata": {},
   "outputs": [],
   "source": [
    "int cycleDir(int x, vector<VI> &adj, vector<int> &par, vector<int> &path, vector<int> &cyc) {\n",
    "    if (par[x]==-1) par[x]=x;\n",
    "    path[x]=1;\n",
    "    for (int y : adj[x]) {\n",
    "        if (path[y]) {  // prednik (cikel)\n",
    "            for (int z=x; z!=y; z=par[z]) cyc.push_back(z);\n",
    "            cyc.push_back(y);\n",
    "            reverse(cyc.begin(), cyc.end());\n",
    "            return 1;\n",
    "        }\n",
    "        if (par[y]==-1) {  // neobiskano\n",
    "            par[y]=x;\n",
    "            if (cycleDir(y,adj,par,path,cyc)) return 1;\n",
    "        }\n",
    "    }\n",
    "    path[x]=0;\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2d21742-a868-4879-8bc7-ab9f1305a3fc",
   "metadata": {},
   "source": [
    "Za testiranje si bomo izposodili spodnji usmerjeni graf z dodatno povezavo $5 \\to 4$, da ustvarimo cikel. Paziti moramo tudi na to, od kod začnemo iskanje. Če cikel ni dosegljiv iz začetnega vozlišča, ga ne bomo našli. V tem primeru bi morali začeti iskanje na novo iz nekega neobiskanega vozlišča, dokler niso obiskana vsa in šele takrat lahko zagotovimo, da cikla ni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "de03e383-8724-449d-840a-908f22b870d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "povezave = read_graph(\"directed.txt\",n,m);\n",
    "povezave.push_back({5,4});\n",
    "vector<VI> sosediDir = adjacency_list(povezave, n, true);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "a17bd59c-731e-424e-a997-6947bc30a530",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1 5 4 0 \n"
     ]
    }
   ],
   "source": [
    "vector<int> visDir(n), parDir(n,-1), path(n), cycDir;\n",
    "cout << cycleDir(2,sosediDir,parDir,path,cycDir) << endl;\n",
    "print(cycDir);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "301ef140-3e57-4b6a-8e9f-8acfa1b924e5",
   "metadata": {},
   "source": [
    "## Topološko urejanje\n",
    "\n",
    "Naj usmerjeni graf predstavlja medsebojne odvisnosti izvedbe opravil. Vozlišča ustrezajo opravilom, povezava $x \\rightarrow y$ pa pomeni, da je treba opravilo $x$ izvesti pred opravilom $y$. V kakšnem vrstnem redu naj izvajamo opravila, da bomo lahko izvedli vsa oz. je to sploh mogoče?\n",
    "\n",
    "<img alt=\"Usmerjeni graf\" src=\"directed.svg\" width=\"300px\">\n",
    "\n",
    "Topološki vrstni red vozlišč v usmerjenem grafu je tak vrstni red, da vse povezave v grafu kažejo od zgodnejšega proti kasnejšemu vozlišču v topološkem vrstnem redu. Topološki vrstni red ni enoličen. Za zgornji primer bi bil možen topološki vrstni red npr. `[4,0,2,3,1,6,5]`. Ker v grafu nastopa povezava $0 \\rightarrow 5$, se v topološkem vrstnem redu $0$ pojavi pred $5$. Preverimo lahko, da to velja za vse povezave."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "02d2bcc3-7d00-490e-832c-e65f0b03a0be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: 1 3 5 \n",
      "1: 5 \n",
      "2: 3 \n",
      "3: 1 6 \n",
      "4: 0 3 \n",
      "5: \n",
      "6: \n"
     ]
    }
   ],
   "source": [
    "povezave = read_graph(\"directed.txt\",n,m);\n",
    "sosedi = adjacency_list(povezave, n, true);\n",
    "for (int i=0;i<n;i++) {\n",
    "    cout << i << \": \";\n",
    "    print(sosedi[i]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28fe486f-7bd9-40f9-9430-67c7ed432336",
   "metadata": {},
   "source": [
    "Razmislimo o algoritmu za izgradnjo topološkega vrstnega reda. Vozlišča brez predhodnikov lahko postavimo na začetek topološkega vrstnega reda. Če je takih vozlišč več, njihov medsebojni vrstni red ni pomemben. Za povezave, ki izhajajo iz njih, je torej poskrbljeno. Zato lahko ta vozlišča in njihove povezave odstranimo iz grafa ter ponovimo postopek z morebitnimi novimi vozlišči brez predhodnikov. Postopek se ne zaključi, če topološki vrstni red ne obstaja zaradi prisotnosti cikla v grafu. **Usmerjeni aciklični grafi** (*directed acyclic graph - DAG*) so svoj razred grafov, ki jih je mogoče topološko urediti.\n",
    "\n",
    "Kako naj opisani postopek učinkovito implementiramo? Odstraniti moramo $n$ vozlišč in na vsakem koraku iščemo med preostalimi vozlišči kakšnega z vhodno stopnjo 0. Direktna implementacija takega postopka bo imela kvadratno časovno zahtevnost. To pa lahko izboljšamo v vodenjem seznama vozlišč z vhodno stopnjo 0. Vsakič, ko odstranimo vozlišče in njegove izhodne povezave, dodamo v seznam morebitna novo nastala začetna vozlišča. Tako dobimo algoritem s časovno zahtevnostjo $O(n+e)$. Običajno je število povezav vsaj tolikšno kot število vozlišč, zato lahko brez večje škode poenostavimo na $O(e)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "196068c7-eaad-42e4-a9f9-28ec20c8ae5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "VI toposort(vector<VI> &sosedi, int n) {\n",
    "    vector<int> indeg(n);\n",
    "    for (int x=0;x<n;x++) {\n",
    "        for (int y : sosedi[x]) indeg[y]++;\n",
    "    }\n",
    "    queue<int> q;\n",
    "    for (int x=0;x<n;x++) {\n",
    "        if (indeg[x]==0) q.push(x);\n",
    "    }\n",
    "    vector<int> seq;\n",
    "    while (!q.empty()) {\n",
    "        int x=q.front(); q.pop();\n",
    "        seq.push_back(x);\n",
    "        for (int y : sosedi[x]) {\n",
    "            indeg[y]--;\n",
    "            if (indeg[y]==0) q.push(y);\n",
    "        }\n",
    "    }\n",
    "    return seq;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "b9f4883d-9728-46c9-b63f-10db403e86b1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4 0 3 1 6 5 \n"
     ]
    }
   ],
   "source": [
    "vector<int> topo = toposort(sosedi, n);\n",
    "print(topo);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5f1afd2-43d3-4b1b-8e69-c3ec5d83e9ae",
   "metadata": {},
   "source": [
    "## Kritična pot\n",
    "\n",
    "Potek izvajanja projekta lahko modeliramo z mejniki in aktivnostmi, ki doprinesejo k izpolnjevanju teh mejnikov. Mejnike predstavimo z vozlišči, aktivnosti pa s povezavami v usmerjenem grafu. Ko so končane vse potrebne aktivnosti, je mejnik dosežen. Poleg tega poznamo čas $w(x,y)$ za izvedbo določene aktivnosti med mejnikoma $x$ in $y$. Očitno mora biti graf acikličen. Kakšen je najkrajši čas za izvedbo projekta ob \"neomejeni\" količini resursov, pri čemer lahko vsako aktivnost izvaja ena oseba, vendar imamo na voljo poljubno število oseb? Ta čas predstavlja najdaljša pot v uteženem usmerjenem acikličnem grafu, ki ji rečemo tudi kritična pot.\n",
    "\n",
    "<img alt=\"utežen usmerjen acikličen graf\" src=\"critical.svg\" width=\"400px\">\n",
    "\n",
    "Kako pa jo izračunamo? Vozlišča naprej topološko uredimo v linearnem času. Nato pa lahko računamo najdaljše poti $d(x)$, ki se začnejo v v posameznem vozlišču $x$, v obratnem topološkem vrstnem redu. Če vozlišče nima naslednikov, je $d(x)=0$. Sicer pa velja $d(x) = \\max_{y:\\; x < y \\,\\land\\, (x,y) \\in E\\;} (w(x,y) + d(y))$.\n",
    "\n",
    "Opravka imamo z uteženim grafom, ki ga moramo najprej prebrati. V seznamu sosedov bomo poleg sosednjega vozlišča hranili še težo povezave, ki vodi do njega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "0b0d08fc-4f16-451b-b834-967f6d74fa32",
   "metadata": {},
   "outputs": [],
   "source": [
    "ifstream fin(\"critical.txt\");\n",
    "fin >> n >> m;\n",
    "vector<VI> adj(n);\n",
    "vector<VII> adjw(n);\n",
    "for (int i=0;i<m;i++) {\n",
    "    int a,b,c;\n",
    "    fin >> a >> b >> c;\n",
    "    adj[a].push_back(b);\n",
    "    adjw[a].push_back({b,c});\n",
    "}\n",
    "fin.close();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cccde94e-6349-479e-a2fa-9606df9ffaa4",
   "metadata": {},
   "source": [
    "Algoritem za izračun topološkega vrstnega reda že imamo, samo obrnemo ga."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "2bb723b3-229a-486e-8465-0eba00862058",
   "metadata": {},
   "outputs": [],
   "source": [
    "vector<int> ord = toposort(adj, n);\n",
    "reverse(ord.begin(), ord.end());"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ab315fc-ce0b-445c-9b2c-aefe5aee3a71",
   "metadata": {},
   "source": [
    "V tem obratnem topološkem vrstem redu lahko izračunamo dolžino najdaljše poti iz vsakega vozlišča, saj bo vsaka vrednost odvisna samo od naslednikov, za katere imamo rezultat že izračunan. Zapomnimo si tudi vozlišče z največjim rezultatom, ki je začetek najdaljše poti."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "38fa1e83-d509-475a-9ae4-dc19afcc0267",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dolzina = 10\n"
     ]
    }
   ],
   "source": [
    "vector<int> d(n);\n",
    "int start = ord[0];\n",
    "for (int x : ord) {\n",
    "    for (auto [y,w] : adjw[x]) {\n",
    "        d[x] = max(d[x], w+d[y]);\n",
    "    }\n",
    "    if (d[x]>d[start]) start=x;\n",
    "}\n",
    "cout << \"dolzina = \" << d[start] << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5a60d2a-b11e-4625-8958-320a4cf42484",
   "metadata": {},
   "source": [
    "Izračunane vrednosti so dovolj, da lahko pot tudi rekonstruiramo. Iz trenutnega vozlišča nadaljujemo tam, kjer je izračunana najdaljša pot ravno za dolžino povezave krajša. Druga možnost bi bila, da si pri računanju najdaljših poti za vsako vozlišče poleg razdalje shranjujemo tudi naslednje vozlišče, ki je vodilo do te maksimalne vrednosti."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "bc34e9c7-26cd-41a7-a01b-26ef6576c4e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6 0 5 2\n"
     ]
    }
   ],
   "source": [
    "cout << start;\n",
    "int x=start;\n",
    "while (d[x]!=0) {\n",
    "    for (auto [y,w] : adjw[x]) {\n",
    "        if (d[x]==w+d[y]) {\n",
    "            cout << \" \" << y;\n",
    "            x = y;\n",
    "            break;\n",
    "        }\n",
    "    }\n",
    "}\n",
    "cout << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5653bc0e-31c4-44ee-86c5-15ecb5d96cb4",
   "metadata": {},
   "source": [
    "## Eulerjev obhod\n",
    "\n",
    "Dobro znan problem na neusmerjenih grafih je iskanje Eulerjevega obhod (*Eulerian tour/cycle/circuit*). Pri tem iščemo obhod, ki obišče vse povezave v grafu (vsako povezavo natanko enkrat, vozlišča pa morda tudi večkrat). Podoben problem je iskanje Eulerjevega sprehoda (*Eulerian trail/path/walk*). Pravzaprav iščemo stezo (sprehod brez ponovljenih povezav vendar morda s ponovljenimi vozlišči), ki obišče vse povezave v grafu. Za razliko od obhoda pa se lahko začne in konča na različnih mestih.\n",
    "\n",
    "S tem problemov ste se najbrž že srečali pri risanju oblik z eno potezo (npr. odprtega pisma/ovojnice). Euler pa pri problemu sedmih mostov v Königsbergu (danes Kaliningrad). Zanimalo ga je, kako bi lahko na sprehodu prehodil vsak most natanko enkrat.\n",
    "\n",
    "<img alt=\"sedem mostov v Konigsbergu (wikipedija)\" src=\"https://upload.wikimedia.org/wikipedia/commons/5/5d/Konigsberg_bridges.png\" width=\"200px\">\n",
    "\n",
    "Eulerjev izrek pravi, da v povezanem grafu obstaja Eulerjev obhod natanko takrat, ko so vsa vozlišča sode stopnje. Eulerjev sprehod pa natanko takrat, ko so vsa vozlišča sode stopnje razen morda točno dveh vozlišč, kjer se začne in konča. Dokažimo to trditev za primer obhoda (za sprehod velja podobno).\n",
    "\n",
    "- Recimo, da obstaja Eulerjev obhod. Potem ta obhod na prehodu skozi vsako vozlišče zmanjša stopnjo tega vozlišča za 2. Če sproti odstranjujemo prehojene povezave, imajo na koncu vsa vozlišča stopnjo 0. Torej morajo biti na začetku vsa sode stopnje.\n",
    "\n",
    "- Obratna smer je bolj kompleksna in jo lahko dokažemo kar s konstrukcijo Eulerjevega obhoda na povezanem grafu z vozlišči sodih stopenj. Začnemo v poljubnem vozlišču $x$ in sledimo povezavam, dokler se ne vrnemo v začetno vozlišče $x$. Pri tem se ne moremo zatakniti v nekem drugem vozlišču $y$, ker bi že porabili vse njegove povezave. V vsakem prehodu skozi vozlišče namreč porabimo dve povezavi - če je na voljo vsaj ena za vstop, bo tudi druga za izstop, ker so vsa vozlišča sode stopnje. Morda pa smo se vrnili v začetno vozlišče, pri tem pa še nismo obiskali vseh povezav. Postopek ponovimo na enem od že obiskanih vozlišč, ki ima še kakšne neobiskane povezave. Od tam na enak način zgradimo obhod in ga združimo s prejšnjim. To ponavljamo dokler niso obiskane vse povezave. To je Hierholzerjev algoritem, ki ga lahko implementiramo v linearnem času."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}