{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "THE FIREFIGTER PROBLEM\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def clp(G, B, gasilci, cas):\n",
    "    ''' vhodni podatki:\n",
    "         G           izbran graf\n",
    "         B           vozlišča, ki na začetku zgorijo\n",
    "         gasilci     število gasilcev, ki v vsakem koraku gasijo požar\n",
    "         cas         maksimaleno število časovnih enot\n",
    "     izhodni podatki:\n",
    "         seznam oblike [število časovnih enot, pogorela/burnt vozlišča po časih, zaščitena/defended vozlišča po časih] '''\n",
    " \n",
    "    casi = range(1, cas+1) # uprabljamo pri zankah\n",
    "    \n",
    "    # CLP:\n",
    "    p = MixedIntegerLinearProgram(maximization=False) # CLP\n",
    "    d = p.new_variable(binary=True) # spremenljivka, defended\n",
    "    b = p.new_variable(binary=True) # spremenljivka, burnt\n",
    "\n",
    "    p.set_objective(sum(b[i, cas] for i in G)) # minimiziramo število pogorelih vozlišč na koncu \n",
    "\n",
    "    for t in casi:\n",
    "        for i in G:\n",
    "            for j in G[i]: # j je številka v seznamu vozlišča i, sosed od i\n",
    "                p.add_constraint(b[i,t] + d[i,t] - b[j,t-1] >= 0)\n",
    "            p.add_constraint(b[i,t] + d[i,t] <= 1)\n",
    "            p.add_constraint(b[i,t] - b[i,t-1] >= 0)\n",
    "            p.add_constraint(d[i,t] - d[i,t-1] >= 0)\n",
    "        p.add_constraint(sum((d[i,t] - d[i,t-1]) for i in G) <= gasilci)\n",
    "\n",
    "    for i in G:\n",
    "        p.add_constraint(b[i,0] == (1 if i in B else 0))\n",
    "        p.add_constraint(d[i,0] == 0)\n",
    "        \n",
    "    return [p.solve(), p.get_values(b), p.get_values(d)]\n",
    "\n",
    "\n",
    "def skrcitev(dic, t):\n",
    "    ''' pomožna funkcija skrcitev vrne seznam, ki vsebuje vozlišča, ki jih je potrebno pobarvati (imajo vrednost ključa 1) v določenem času '''\n",
    "\n",
    "    new = []\n",
    "    for key in dic:\n",
    "        if key[1] == t and dic[key] == 1:\n",
    "            new.append(key[0])\n",
    "    return new\n",
    "\n",
    "\n",
    "def ali_je_problem_koncan(G, B, gasilci, cas, t):\n",
    "    ''' funkcija nam pove ali je problem v času t zaključen/končen '''\n",
    "    \n",
    "    b = skrcitev(clp(G, B, gasilci, cas)[1], t) # burnt vozlišča v t\n",
    "    d = skrcitev(clp(G, B, gasilci, cas)[2], t) # defended vozlišča v t\n",
    "    skupaj = b + d\n",
    "\n",
    "    # sosedi od pogorelih vozlišč so lahko pogoreli ali zaščiteni. Ne smejo biti prazna vozlišča\n",
    "    for pogorelo_vozlisce in b:\n",
    "        for sosed_od_pogorelo_vozlisce in G[pogorelo_vozlisce]:\n",
    "            if sosed_od_pogorelo_vozlisce not in skupaj:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "   \n",
    "def cas_potreben(G, B, gasilci, cas):\n",
    "    ''' iz p.solve() pridobi čas po katerem se nič več ne spremeni -> dobimo potreben čas '''\n",
    "    \n",
    "    burnt = clp(G, B, gasilci, cas)[1]\n",
    "    defended = clp(G,B,gasilci,cas)[2]\n",
    "\n",
    "    urej_burnt = sorted(burnt.items(), key=lambda tup: tup[0][1]) #uredi glede na čas po vozliščih naraščajoče\n",
    "    urej_defended = sorted(defended.items(), key=lambda tup: tup[0][1]) \n",
    "\n",
    "    vredn_burnt= []\n",
    "    for i, v in urej_burnt:\n",
    "        vredn_burnt.append(v)\n",
    "    # pridobim ven vrednosti spremnljivk b v časih in vozliščih naraščajoče\n",
    "\n",
    "    vredn_defended= []\n",
    "    for i, v in urej_defended:\n",
    "        vredn_defended.append(v)\n",
    "    # pridobim ven vrednosti spremnljivk d v časih in vozliščih naraščajoče\n",
    "\n",
    "    # from itertools import islice\n",
    "    from itertools import accumulate\n",
    "    dolzina = [len(G)] * (cas +1) # Vrednosti zgrupiram v paketke, v vsakem je toliko vrednosti, kolikor je vozlišč\n",
    "    seznami_vrednosti_po_casih_burnt = [vredn_burnt[x - y: x] for x, y in zip(\n",
    "                        accumulate(dolzina), dolzina)]\n",
    "\n",
    "    seznami_vrednosti_po_casih_defended = [vredn_defended[x - y: x] for x, y in zip(\n",
    "                        accumulate(dolzina), dolzina)]\n",
    "\n",
    "    i = 0\n",
    "    while seznami_vrednosti_po_casih_burnt[i] != seznami_vrednosti_po_casih_burnt[i+1]:\n",
    "        i = i + 1\n",
    "    i    \n",
    "\n",
    "    j = 0\n",
    "    while seznami_vrednosti_po_casih_defended[j] != seznami_vrednosti_po_casih_defended[j+1]:\n",
    "        j = j + 1\n",
    "    j \n",
    "\n",
    "    return max(i, j) #večji od časev ko se neha spreminjati\n",
    "\n",
    "\n",
    "\n",
    "def barvanje_v_casu_t(G, B, gasilci, cas, t):\n",
    "    ''' pomožna funkcija barvanje_v_casu_t izriše graf in pobarva vozlišča v določenem času (t). Začetna vozlišča oz. izvor pošara pobarva v zeleno, \n",
    "         pogorela v  rdečo, zaščitena pa v modro. '''\n",
    "\n",
    "    b = skrcitev(clp(G, B, gasilci, cas)[1], t) # burnt vozlišča v času t BREZ ZAČETNIH VOZLIŠČ B\n",
    "    for el in B:\n",
    "        b.remove(el)\n",
    "    d = skrcitev(clp(G, B, gasilci, cas)[2], t) # defended vozlišča v času t\n",
    "    \n",
    "    return G.show(partition = [b, B, d])\n",
    "\n",
    "\n",
    "def barvanje_po_korakih(G, B, gasilci, cas, t):\n",
    "    ''' funkcija, ki za vsako časovno enoto nariše situacijo na grafu\n",
    "         barve:\n",
    "             - zelena: oglišča kjer se požar začne (B)\n",
    "             - rdeča: pogorela\n",
    "             - modra: zaščitena '''\n",
    "    \n",
    "    if ali_je_problem_koncan(G, B, gasilci, cas, t) == False:\n",
    "        return 'V izbranem času problem še ni zaključen.'\n",
    "    \n",
    "    else:    \n",
    "        time = cas_potreben(G, B, gasilci, cas)\n",
    "        print(\"Število potrebnih časovnih korakov: \" + str(time))\n",
    "        for t in range(0, time + 1):\n",
    "            print(\"Situacija v času \" + str(t) + \":\")\n",
    "            barvanje_v_casu_t(G, B, gasilci, cas, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# PRIMER 1:\n",
    "G1 = graphs.Grid2dGraph(3, 4)\n",
    "B1 = [(1, 1), (2, 2)]\n",
    "gasilci1 = 2\n",
    "cas1 = 10\n",
    "#cas_potreben(G1,B1,gasilci1,cas1)\n",
    "#barvanje_po_korakih(G1, B1, gasilci1, cas1, 3)\n",
    "#ali_je_problem_koncan(G1, B1, gasilci1, cas1, 2)\n",
    "#ali_je_problem_koncan(G1,B1,gasilci1,1,1) #lahko preverjamo, če je cas1 uredu, recimo tukaj cas1 = 1 ni uredu, ker na koncu (t=1) še problem ni končan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# PRIMER 2:\n",
    "G2 = graphs.PetersenGraph()\n",
    "B2 = [1,5]\n",
    "gasilci2 = 3\n",
    "cas2 = 10\n",
    "#barvanje_po_korakih(G2, B2, gasilci2, cas2, 2)\n",
    "#ali_je_problem_koncan(G2, B2, gasilci2, cas2, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# PRIMER 3:\n",
    "G3 = graphs.PappusGraph()\n",
    "B3 = [0,1,2,3]\n",
    "gasilci3 = 3\n",
    "cas3 = 2\n",
    "#barvanje_po_korakih(G3, B3, gasilci3, cas3, 3)\n",
    "#ali_je_problem_koncan(G3, B3, gasilci3, cas3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Generate all graphs with 5 vertices and up to 4 edges. #edges je število povezav\n",
    "#L = list(graphs(5, lambda G: G.size() <= 4))\n",
    "#len(L)\n",
    "#graphs_list.show_graphs(L) # long time\n",
    "\n",
    "# Lahko uporabiva ta generate za grafe, samo pri večjem številu vozlišč bo delalo zelo dolgo časa. -> Lahko potem za tisto testiranje ali_je_problem_koncan ??"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "import random\n",
    "def nakljucno_izberi_vzolisca(graf, n):\n",
    "    ''' funkcija naključno izbere n vozlišč iz grafa graf '''\n",
    "    return random.sample(list(graf), n)\n",
    "\n",
    "def seznam_naborov_st_vozlisc_cas(seznam_imen_grafov, st_gasilcev, stevilo_vozlisc_v_B):\n",
    "    ''' funkcija, ki sprejme seznam v katerem so imena grafov, število gasilcev ter število vozlišč, ki jih želimo v začetni množici B.\n",
    "            Vrne pa seznam naborov oblike (število vozlišč, potreben čas reševanje problema)'''\n",
    "    # določimo čas:\n",
    "    cas = 10\n",
    "    # sprehodimo se po seznam_imen_grafov in sestavljamo nabor:\n",
    "    seznam_naborov = []\n",
    "    for graf in seznam_imen_grafov:\n",
    "        B1 = nakljucno_izberi_vzolisca(graf, stevilo_vozlisc_v_B)\n",
    "        B2 = nakljucno_izberi_vzolisca(graf, stevilo_vozlisc_v_B)\n",
    "        potreben_cas1 = cas_potreben(graf, B1, st_gasilcev, cas)\n",
    "        potreben_cas2 = cas_potreben(graf, B2, st_gasilcev, cas)\n",
    "        seznam_naborov.append((len(graf), potreben_cas1))\n",
    "        seznam_naborov.append((len(graf), potreben_cas2))\n",
    "    \n",
    "    return seznam_naborov\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'cas_potreben' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Input \u001b[0;32mIn [6]\u001b[0m, in \u001b[0;36m<cell line: 27>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     22\u001b[0m         seznam_grafov\u001b[38;5;241m.\u001b[39mappend(graphs\u001b[38;5;241m.\u001b[39mRandomBlockGraph(i, j))\n\u001b[1;32m     24\u001b[0m \u001b[38;5;66;03m# zmanjka prostora v programu ...\u001b[39;00m\n\u001b[1;32m     25\u001b[0m \n\u001b[1;32m     26\u001b[0m \u001b[38;5;66;03m# s tem dobimo zelo velik seznam grafov, na katerem lahko izvedemo funkcijo seznam_naborov_st_vozlisc_cas za poljubno število vozlišč in vozlišč v B:\u001b[39;00m\n\u001b[0;32m---> 27\u001b[0m seznam_naborov_1_2 \u001b[38;5;241m=\u001b[39m \u001b[43mseznam_naborov_st_vozlisc_cas\u001b[49m\u001b[43m(\u001b[49m\u001b[43mseznam_grafov\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mInteger\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mInteger\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m)\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     28\u001b[0m seznam_naborov_1_3 \u001b[38;5;241m=\u001b[39m seznam_naborov_st_vozlisc_cas(seznam_grafov, Integer(\u001b[38;5;241m1\u001b[39m), Integer(\u001b[38;5;241m3\u001b[39m))\n\u001b[1;32m     29\u001b[0m seznam_naborov_1_4 \u001b[38;5;241m=\u001b[39m seznam_naborov_st_vozlisc_cas(seznam_grafov, Integer(\u001b[38;5;241m1\u001b[39m), Integer(\u001b[38;5;241m4\u001b[39m))\n",
      "Input \u001b[0;32mIn [5]\u001b[0m, in \u001b[0;36mseznam_naborov_st_vozlisc_cas\u001b[0;34m(seznam_imen_grafov, st_gasilcev, stevilo_vozlisc_v_B)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m graf \u001b[38;5;129;01min\u001b[39;00m seznam_imen_grafov:\n\u001b[1;32m     14\u001b[0m     B \u001b[38;5;241m=\u001b[39m nakljucno_izberi_vzolisca(graf, stevilo_vozlisc_v_B)\n\u001b[0;32m---> 15\u001b[0m     potreben_cas \u001b[38;5;241m=\u001b[39m \u001b[43mcas_potreben\u001b[49m(graf, B, st_gasilcev, cas)\n\u001b[1;32m     16\u001b[0m     seznam_naborov\u001b[38;5;241m.\u001b[39mappend((\u001b[38;5;28mlen\u001b[39m(graf), potreben_cas))\n\u001b[1;32m     18\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m seznam_naborov\n",
      "\u001b[0;31mNameError\u001b[0m: name 'cas_potreben' is not defined"
     ]
    }
   ],
   "source": [
    "# sestavljanje seznama grafov:\n",
    "\n",
    "c = graphs.CycleGraph(5)\n",
    "p = graphs.PathGraph(3)\n",
    "\n",
    "seznam_grafov = [graphs.HeawoodGraph(), p.cartesian_product(c), graphs.PappusGraph()]\n",
    "\n",
    "for i in range(3, 100): # manj kot 3 je nesmiselno\n",
    "    seznam_grafov.append(graphs.CircularLadderGraph(i)) # ima 2 * i vozlišč\n",
    "\n",
    "for i in range(2, 15):\n",
    "    for j in range(3,15):\n",
    "        seznam_grafov.append(graphs.Grid2dGraph(i,j)) # matrika i x j, tj. ima i * j vozlišč\n",
    "\n",
    "for i in range(4, 15):\n",
    "    for j in range(4,15):\n",
    "        seznam_grafov.append(graphs.CycleGraph(i).cartesian_product(graphs.CycleGraph(j))) # ima i * j vozlišč\n",
    "\n",
    "for i in range(3, 15):\n",
    "    for j in range(3, 15):\n",
    "        seznam_grafov.append(graphs.RandomBlockGraph(i, j))\n",
    "        \n",
    "# zmanjka prostora v programu ...\n",
    "\n",
    "# s tem dobimo zelo velik seznam grafov, na katerem lahko izvedemo funkcijo seznam_naborov_st_vozlisc_cas za poljubno število vozlišč in vozlišč v B:\n",
    "seznam_naborov_1_2 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 1, 2)\n",
    "seznam_naborov_1_3 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 1, 3)\n",
    "seznam_naborov_1_4 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 1, 4)\n",
    "\n",
    "seznam_naborov_2_2 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 2, 2)\n",
    "seznam_naborov_2_3 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 2, 3)\n",
    "seznam_naborov_2_4 = seznam_naborov_st_vozlisc_cas(seznam_grafov, 2, 4)\n",
    "\n",
    "\n",
    "# V naslednjem koraku zaženemo kodo in dobimo zelo velik seznam, ki ga v ločeni .py datoteki pretvorimo v .csv obliko s katero bomo\n",
    "#         lahko izrisali grafe (število potrebnih časovnih enot v odvisnosti od števila vozlišč grafa)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.7",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-9.7",
   "resource_dir": "/ext/jupyter/kernels/sage-9.7"
  },
  "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.10.5"
  },
  "vscode": {
   "interpreter": {
    "hash": "387d60c8761f370b7f7ba5659dccf1e3b6ab3e6fcdc49b65086dfce393770dcf"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}