aula-11-shortest-path.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Terminologia adotada em modelos de redes\n",
    "\n",
    "Uma rede é formada por um conjunto de pontos e de retas conectando certos pares de pontos. \n",
    "\n",
    "Os pontos são chamados **nós** (ou vértices). As retas são chamadas **arcos** (ou ligações ou bordas ou ramificações).\n",
    "\n",
    "Os arcos de uma rede podem ter um fluxo de algum tipo através deles. Se o fluxo através de um arco for permitido apenas em uma direção (por exemplo, uma via de mão única), o arco é dito **arco direcionado**.\n",
    "\n",
    "Se o fluxo através de um arco for permitido em ambas as direções (por exemplo, uma tubulação que pode ser usada para bombear fluido em ambas as direções), o arco é chamado **arco não-direcionado**.\n",
    "\n",
    "Um **caminho** entre dois nós é uma seqüência de arcos distintos conectando esses nós. Um caminho que começa e termina no mesmo nó é chamado **ciclo**.\n",
    "\n",
    "Uma **rede conectada** é uma rede na qual todo par de nós é conectado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Problema do Caminho Mais Curto\n",
    "\n",
    "Considere uma rede conectada e não-direcionada com dois nós especiais chamados origem e destino. Associado a cada uma das ligações (arcos não-direcionados) está uma distância não-negativa. \n",
    "\n",
    "<img src=\"./img/seervarda-park.png\">\n",
    "\n",
    "O objetivo é encontrar o caminho mais curto (o caminho com a distância total mínima) da origem ao destino.\n",
    "\n",
    "- Grafos não direcionados: algoritmo de Dijkstra com complexidade de tempo $O(V^2)$\n",
    "- Grafos direcionados com pesos e sem ciclos: Algoritmo Bellman-Ford Complexidade de tempo $O(VA)$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <iomanip>\n",
    "#include \"setup.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.h\"\n",
    "#include \"ortools/linear_solver/linear_solver.pb.h\"\n",
    "#include \"ortools/graph/shortestpaths.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "const int64 M = 100;\n",
    "\n",
    "const std::vector<char> nodes{'O','A','B','C','D','E','T'};\n",
    "\n",
    "const std::vector<std::vector<int64>> arcs{\n",
    "/*    O, A, B, C, D, E, T*/\n",
    "/*O*/{M, 2, 5, 4, M, M, M}, \n",
    "/*A*/{2, M, 2, M, 7, M, M}, \n",
    "/*B*/{5, 2, M, 1, 4, 3, M}, \n",
    "/*C*/{4, M, 1, M, M, 4, M}, \n",
    "/*D*/{M, 7, 4, M, M, 1, 5}, \n",
    "/*E*/{M, M, 3, 4, 1, M, 7}, \n",
    "/*T*/{M, M, M, M, 5, 7, M}  \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O->A->B->D->T"
     ]
    }
   ],
   "source": [
    "{\n",
    "    int nos = nodes.size();\n",
    "    int origem = 0;\n",
    "    int destino = nos-1;\n",
    "    std::vector<int> paths;\n",
    "    bool found = DijkstraShortestPath(nos, origem, destino,\n",
    "                                     [](int x, int y) { return arcs[x][y]; },\n",
    "                                      M, &paths);\n",
    "    if (found){\n",
    "        int i = paths.size()-1;\n",
    "        std::cout << nodes[paths[i]];\n",
    "        while(--i >= 0)\n",
    "            std::cout << \"->\" << nodes[paths[i]];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Árvore Geradora Mínima\n",
    "\n",
    "Uma \"árvore\" pode ser \"cultivada\" adicionando-se um arco (ou \"ramificação\") por vez a partir da rede original em uma certa direção.\n",
    "\n",
    "O primeiro arco pode ir para qualquer lugar para conectar algum par de nós. A partir daí, cada arco novo deve estar entre um nó que já esteja conectado a outros nós e um novo nó não previamente conectado a qualquer outro nó. \n",
    "\n",
    "Adicionar um nó dessa maneira impede a criação de um ciclo e garante que o número de nós conectados seja uma unidade a mais que o número de arcos. \n",
    "\n",
    "Cada arco novo cria uma **árvore** maior que é uma rede conectada (de algum subconjunto dos $n$ nós) que não contém nenhum ciclo não-direcionado. \n",
    "\n",
    "Assim que o arco $(n - 1)$ tiver sido adicionado, o processo pára, pois a árvore resultante abrange (conecta) todos os $n$ nós. \n",
    "\n",
    "Essa árvore é chamada **árvore de expansão**, isto é, uma rede conectada de todos os n nós que não contêm nenhum ciclo não-direcionado. \n",
    "\n",
    "Cada uma das árvores de expansão tem exatamente $n - 1$ arcos, visto que este é o número mínimo de arcos necessário para ter uma rede conectada e o número máximo possível sem ter ciclos não-direcionados."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "#include \"ortools/graph/graph.h\"\n",
    "#include \"ortools/graph/minimum_spanning_tree.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Algoritmo \"Guloso\" de Prim\n",
    "\n",
    "1. Selecione qualquer nó arbitrariamente e depois o conecte ao nó distinto mais próximo.\n",
    "2. Identifique o nó desconectado que esteja mais próximo a qualquer um dos nós já conectados. \n",
    "3. Repita a etapa anterior até que todos os nós tenham sido conectados.\n",
    "\n",
    "<img src=\"./img/seervarda-park-mst.png\">\n",
    "\n",
    "### Complexidade de Tempo: $O(V^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O->A\n",
      "A->B\n",
      "B->C\n",
      "B->E\n",
      "B->D\n",
      "D->T\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    util::ReverseArcListGraph<> graph;\n",
    "    \n",
    "    for (int tail=0; tail<nodes.size(); tail++) \n",
    "        for (int head=tail+1; head<nodes.size(); head++)\n",
    "            if (arcs[tail][head] < M)\n",
    "                graph.AddArc(tail, head); \n",
    "    \n",
    "    const auto arc_cost = [&graph](int arc) -> int64 {\n",
    "                           return arcs[graph.Tail(arc)][graph.Head(arc)];\n",
    "                        };\n",
    "    \n",
    "    std::vector<int> MST = BuildPrimMinimumSpanningTree(graph, arc_cost);\n",
    "    \n",
    "    for(auto arc : MST){\n",
    "        auto tail = graph.Tail(arc);\n",
    "        auto head = graph.Head(arc);\n",
    "        std::cout << nodes[tail] << \"->\" << nodes[head] << std::endl;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Algoritmo de Kruskal\n",
    "\n",
    "1. crie uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore separada\n",
    "2. crie um conjunto S contendo todas os arcos do grafo\n",
    "3. enquanto S não está vazio e F ainda não está completo\n",
    "    - remova um arco com peso mínimo de S\n",
    "    - se o arco removido conecta duas árvores diferentes, adicione-a à floresta F, combinando duas árvores em uma única árvore\n",
    "\n",
    "No término do algoritmo, a floresta forma uma floresta de expansão mínima do grafo. \n",
    "\n",
    "Se o grafo for conectado, a floresta tem um único componente e forma uma árvore geradora mínima.\n",
    "\n",
    "### Complexidade de Tempo: $O(A log V)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B->C\n",
      "D->E\n",
      "O->A\n",
      "A->B\n",
      "B->E\n",
      "D->T\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    util::ReverseArcListGraph<> graph;\n",
    "    \n",
    "    for (int tail=0; tail<nodes.size(); tail++) \n",
    "        for (int head=tail+1; head<nodes.size(); head++)\n",
    "            if (arcs[tail][head] < M)\n",
    "                graph.AddArc(tail, head); \n",
    "    \n",
    "    const auto arc_cost = [&graph](int arc) -> int64 {\n",
    "                           return arcs[graph.Tail(arc)][graph.Head(arc)];\n",
    "                        };\n",
    "    \n",
    "    std::vector<int> MST = BuildKruskalMinimumSpanningTree(graph, \n",
    "                                                          [&arc_cost](int a, int b) { return arc_cost(a) < arc_cost(b); });\n",
    "    \n",
    "    for(auto arc : MST){\n",
    "        auto tail = graph.Tail(arc);\n",
    "        auto head = graph.Head(arc);\n",
    "        std::cout << nodes[tail] << \"->\" << nodes[head] << std::endl;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}