0405_dfs_adjacency_list.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "0405_dfs_adjacency_list.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNXOEvxp8a5QxBtRw4dZhoy",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/0405_dfs_adjacency_list.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dVfjrph-nOPh"
      },
      "outputs": [],
      "source": [
        "def dfs(G, s):\n",
        "  n = len(G)\n",
        "  path = [-1]*n\n",
        "  visited = [False]*n\n",
        "\n",
        "  def _dfs(u):\n",
        "    visited[u] = True\n",
        "    for v in G[u]:\n",
        "      if not visited[v]:\n",
        "        path[v] = u\n",
        "        _dfs(v)\n",
        "\n",
        "  _dfs(s)\n",
        "  return path"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%file 0405a.al\n",
        "1 4\n",
        "0 3 5 6\n",
        "4 5 6\n",
        "1 7\n",
        "0 2 6 7\n",
        "1 2\n",
        "1 2 4\n",
        "3 4"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LwZpKJ8Vnm5Q",
        "outputId": "69c26839-4705-48d9-8986-0b61b5e35495"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Writing 0405a.al\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "G1 = []\n",
        "with open(\"0405a.al\") as f:\n",
        "  for line in f:\n",
        "    if line == \"-\\n\":\n",
        "      G1.append([])\n",
        "    else:\n",
        "      G1.append([int(x) for x in line.split()])\n",
        "\n",
        "print(G1)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gPd2cKiPntSR",
        "outputId": "481bac62-5708-4df3-c3dc-05bac9f03f24"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1, 4], [0, 3, 5, 6], [4, 5, 6], [1, 7], [0, 2, 6, 7], [1, 2], [1, 2, 4], [3, 4]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "path = dfs(G1, 5)\n",
        "path"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ag3tn335nwlg",
        "outputId": "54d0a31d-8648-475f-c4d8-e4cc2a64b432"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 5, 4, 7, 0, -1, 2, 4]"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def drawG_al(G, directed=False, path=[]):\n",
        "  graph = gv.Digraph(\"felicidad\") if directed else gv.Graph(\"alegria\")\n",
        "  n = len(G)\n",
        "  added = set()\n",
        "  for v, u in enumerate(path):\n",
        "    if u != -1:\n",
        "      graph.edge(str(u), str(v), dir=\"forward\", penwidth=\"2\", color=\"orange\")\n",
        "      added.add(f\"{u},{v}\")\n",
        "      added.add(f\"{v},{u}\")\n",
        "  for u in range(n):\n",
        "    for v in G[u]:\n",
        "      if not directed and not f\"{u},{v}\" in added:  \n",
        "        added.add(f\"{u},{v}\")\n",
        "        added.add(f\"{v},{u}\")\n",
        "        graph.edge(str(u), str(v))\n",
        "      elif directed:\n",
        "        graph.edge(str(u), str(v))\n",
        "  return graph"
      ],
      "metadata": {
        "id": "oHKfwqQVn1Is"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import graphviz as gv"
      ],
      "metadata": {
        "id": "3s27546qn-FV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "drawG_al(G1, path=path)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 463
        },
        "id": "kTWFHKnwn6OO",
        "outputId": "c0de0915-80da-462c-c938-5d1030584f27"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7f46e6e0a950>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: alegria Pages: 1 -->\n<svg width=\"263pt\" height=\"332pt\"\n viewBox=\"0.00 0.00 263.00 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n<title>alegria</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-328 259,-328 259,4 -4,4\"/>\n<!-- 1 -->\n<g id=\"node1\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"109\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"109\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 0 -->\n<g id=\"node2\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"125\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"125\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1&#45;&#45;0 -->\n<g id=\"edge1\" class=\"edge\">\n<title>1&#45;&#45;0</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M113.0375,-287.8314C114.7941,-279.9266 116.8917,-270.4872 118.8363,-261.7365\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"122.2665,-262.4346 121.0192,-251.9134 115.4332,-260.916 122.2665,-262.4346\"/>\n</g>\n<!-- 3 -->\n<g id=\"node7\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 1&#45;&#45;3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>1&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M93.0758,-291.4105C82.9831,-281.2953 70.4674,-266.9921 63,-252 26.3489,-178.4167 24.9925,-76.985 26.1529,-36.1298\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"228\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"228\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 1&#45;&#45;6 -->\n<g id=\"edge9\" class=\"edge\">\n<title>1&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M125.4589,-291.5811C136.4877,-281.3212 150.8015,-266.7844 161,-252 201.1886,-193.7398 213.5136,-177.062 229,-108 234.4705,-83.6043 232.7122,-54.547 230.6243,-36.1846\"/>\n</g>\n<!-- 4 -->\n<g id=\"node4\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"141\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"141\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 0&#45;&#45;4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>0&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M129.0375,-215.8314C130.7941,-207.9266 132.8917,-198.4872 134.8363,-189.7365\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"138.2665,-190.4346 137.0192,-179.9134 131.4332,-188.916 138.2665,-190.4346\"/>\n</g>\n<!-- 5 -->\n<g id=\"node3\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"137\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"137\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&#45;1 -->\n<g id=\"edge2\" class=\"edge\">\n<title>5&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M114.1946,-28.0405C97.1859,-36.9014 75.2021,-51.5959 65,-72 30.2101,-141.5798 70.3477,-235.3151 94.0517,-280.0901\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"91.1145,-282.0151 98.968,-289.1265 97.2634,-278.6697 91.1145,-282.0151\"/>\n</g>\n<!-- 2 -->\n<g id=\"node5\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"173\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"173\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 4&#45;&#45;2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M148.7463,-144.5708C152.4804,-136.1691 157.0404,-125.9091 161.1945,-116.5623\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"164.4619,-117.8283 165.325,-107.2687 158.0652,-114.9853 164.4619,-117.8283\"/>\n</g>\n<!-- 7 -->\n<g id=\"node6\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"101\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"101\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 4&#45;&#45;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>4&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M131.5206,-144.937C126.6885,-136.2393 120.7111,-125.4799 115.3304,-115.7948\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"118.3274,-113.9823 110.4114,-106.9405 112.2083,-117.3819 118.3274,-113.9823\"/>\n</g>\n<!-- 4&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>4&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M162.1018,-150.6379C177.4937,-141.241 197.5821,-126.463 209,-108 222.691,-85.8613 226.6502,-55.4279 227.7199,-36.2378\"/>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge10\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M164.2854,-72.5708C158.6253,-61.2506 151.2784,-46.5568 145.6343,-35.2687\"/>\n</g>\n<!-- 2&#45;&#45;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M185.4804,-73.6621C192.5124,-64.4564 201.4347,-52.7764 209.2883,-42.4953\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"212.28,-44.3446 215.569,-34.2733 206.7172,-40.0953 212.28,-44.3446\"/>\n</g>\n<!-- 7&#45;&#45;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>7&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M85.6672,-75.0816C75.249,-64.945 61.2922,-51.3654 49.6053,-39.9944\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"51.9212,-37.3644 42.3132,-32.8993 47.0397,-42.3815 51.9212,-37.3644\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "qFKCCDVon83t"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}