{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#\n",
    "#  A - B - I\n",
    "#            /\n",
    "#           /\n",
    "#          /\n",
    "#         /\n",
    "#        /\n",
    "#       /\n",
    "#      /\n",
    "#     /\n",
    "#    /\n",
    "#  C - D - E\n",
    "#         |\n",
    "#  F - G - H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "grafo = {\n",
    "    \"A\": [\"B\"],\n",
    "    \"B\": [\"B\", \"I\"],\n",
    "    \"C\": [\"D\", \"I\"],\n",
    "    \"D\": [\"C\", \"E\",\"G\"],\n",
    "    \"E\": [\"D\"],\n",
    "    \"F\": [\"G\"],\n",
    "    \"G\": [\"F\", \"H\", \"D\"],\n",
    "    \"H\": [\"G\"],\n",
    "    \"I\": [\"B\", \"C\"],\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_tot_comp(grafo):\n",
    "    visitado = []; comp = [];\n",
    "    for i in list(grafo.keys()):\n",
    "        if i not in visitado:\n",
    "            visitado.append(i)\n",
    "            visita_vizinho(grafo, i, visitado)\n",
    "            comp.append(visitado.copy())\n",
    "    return comp\n",
    "        \n",
    "def visita_vizinho(grafo, atual, visitado):\n",
    "    for i in grafo[atual]:\n",
    "        if i not in visitado:\n",
    "            visitado.append(i)\n",
    "            visita_vizinho(grafo, i, visitado)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(calc_tot_comp(grafo))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Vamos agora testar o algoritmo de ciclo hamiltoniano\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CiHam(grafo, size, pt, path=[]):\n",
    "    print('Hamilton chamado com origem={}, path={}'.format(pt, path))\n",
    "    if pt not in set(path):\n",
    "        path.append(pt)\n",
    "        if len(path)==size:\n",
    "            return path\n",
    "        for pt_next in grafo.get(pt, []):\n",
    "            res_path = [i for i in path]\n",
    "            candidate = CiHam(grafo, size, pt_next, res_path)\n",
    "            if candidate is not None:\n",
    "                return candidate\n",
    "        print('Nos {} caminho termina '.format(path))\n",
    "    else:\n",
    "        print('Nos {} esta no ciclo {}'.format(pt, path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hamilton chamado com origem=A, path=[]\n",
      "Hamilton chamado com origem=B, path=['A']\n",
      "Hamilton chamado com origem=B, path=['A', 'B']\n",
      "Nos B esta no ciclo ['A', 'B']\n",
      "Hamilton chamado com origem=I, path=['A', 'B']\n",
      "Hamilton chamado com origem=B, path=['A', 'B', 'I']\n",
      "Nos B esta no ciclo ['A', 'B', 'I']\n",
      "Hamilton chamado com origem=C, path=['A', 'B', 'I']\n",
      "Hamilton chamado com origem=D, path=['A', 'B', 'I', 'C']\n",
      "Hamilton chamado com origem=C, path=['A', 'B', 'I', 'C', 'D']\n",
      "Nos C esta no ciclo ['A', 'B', 'I', 'C', 'D']\n",
      "Hamilton chamado com origem=E, path=['A', 'B', 'I', 'C', 'D']\n",
      "Hamilton chamado com origem=D, path=['A', 'B', 'I', 'C', 'D', 'E']\n",
      "Nos D esta no ciclo ['A', 'B', 'I', 'C', 'D', 'E']\n",
      "Nos ['A', 'B', 'I', 'C', 'D', 'E'] caminho termina \n",
      "Hamilton chamado com origem=G, path=['A', 'B', 'I', 'C', 'D']\n",
      "Hamilton chamado com origem=F, path=['A', 'B', 'I', 'C', 'D', 'G']\n",
      "Hamilton chamado com origem=G, path=['A', 'B', 'I', 'C', 'D', 'G', 'F']\n",
      "Nos G esta no ciclo ['A', 'B', 'I', 'C', 'D', 'G', 'F']\n",
      "Nos ['A', 'B', 'I', 'C', 'D', 'G', 'F'] caminho termina \n",
      "Hamilton chamado com origem=H, path=['A', 'B', 'I', 'C', 'D', 'G']\n",
      "Hamilton chamado com origem=G, path=['A', 'B', 'I', 'C', 'D', 'G', 'H']\n",
      "Nos G esta no ciclo ['A', 'B', 'I', 'C', 'D', 'G', 'H']\n",
      "Nos ['A', 'B', 'I', 'C', 'D', 'G', 'H'] caminho termina \n",
      "Hamilton chamado com origem=D, path=['A', 'B', 'I', 'C', 'D', 'G']\n",
      "Nos D esta no ciclo ['A', 'B', 'I', 'C', 'D', 'G']\n",
      "Nos ['A', 'B', 'I', 'C', 'D', 'G'] caminho termina \n",
      "Nos ['A', 'B', 'I', 'C', 'D'] caminho termina \n",
      "Hamilton chamado com origem=I, path=['A', 'B', 'I', 'C']\n",
      "Nos I esta no ciclo ['A', 'B', 'I', 'C']\n",
      "Nos ['A', 'B', 'I', 'C'] caminho termina \n",
      "Nos ['A', 'B', 'I'] caminho termina \n",
      "Nos ['A', 'B'] caminho termina \n",
      "Nos ['A'] caminho termina \n"
     ]
    }
   ],
   "source": [
    "CiHam(grafo, 9, \"A\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}