graph_examples.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "NL9Or11cCrhz"
      },
      "outputs": [],
      "source": [
        "from queue import Queue\n",
        "import sys\n",
        "\n",
        "from graph import *"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yY6BM0JPNsee"
      },
      "source": [
        "# Exemplos básicos"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jDfud8AR5mUm"
      },
      "source": [
        "## DFS e BFS"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "CxFFOjk_BPW7"
      },
      "outputs": [],
      "source": [
        "# busca em profundidade (DFS)\n",
        "def depth_first_search(graph, start):\n",
        "    visited = []\n",
        "    stack = [start]\n",
        "    while stack:\n",
        "        vertex = stack.pop()\n",
        "        if vertex not in visited:\n",
        "            visited.append(vertex)\n",
        "            stack.extend(graph[vertex] - set(visited))\n",
        "    return visited"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "HL6hzUA-Clex"
      },
      "outputs": [],
      "source": [
        "# busca em largura (BFS)\n",
        "def breadth_first_search(graph, start):\n",
        "    visited = [start]\n",
        "    queue = Queue()\n",
        "    queue.put(start)\n",
        "    while not queue.empty():\n",
        "        vertex = queue.get()\n",
        "        for neighbor in graph[vertex]:\n",
        "            if neighbor not in visited:\n",
        "                visited.append(neighbor)\n",
        "                queue.put(neighbor)\n",
        "    return visited"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9E0X630jCGvd",
        "outputId": "1836aa89-bd41-4149-e6ea-9f32086d8d16"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "dfs = ['A', 'B', 'C', 'D', 'E', 'F']\n",
            "bfs = ['A', 'D', 'B', 'E', 'F', 'C']\n"
          ]
        }
      ],
      "source": [
        "#      A\n",
        "#     / \\\n",
        "#    B   D\n",
        "#   /   / \\\n",
        "#  C   E   F\n",
        "\n",
        "graph = {\n",
        "    'A': {'B', 'D'},\n",
        "    'B': {'A', 'C'},\n",
        "    'C': {'B'},\n",
        "    'D': {'A', 'E', 'F'},\n",
        "    'E': {'D'},\n",
        "    'F': {'D'}\n",
        "}\n",
        "\n",
        "print('dfs =', depth_first_search(graph, 'A'))\n",
        "print('bfs =', breadth_first_search(graph, 'A'))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jb269lLP5ja0"
      },
      "source": [
        "## Dijkstra"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "UKeUp_c7ozEE"
      },
      "outputs": [],
      "source": [
        "# dijkstra (menor caminho)\n",
        "def dijkstra(graph, start='A', end='C'):\n",
        "    nodes = list(graph.keys())\n",
        "    unvisited = {node: None for node in nodes}\n",
        "    current_distance = 0\n",
        "    unvisited[start] = current_distance\n",
        "    visited = {}\n",
        "\n",
        "    while end not in visited:\n",
        "        for neighbour, distance in graph[start].items():\n",
        "            if neighbour not in unvisited:\n",
        "                continue\n",
        "\n",
        "            new_distance = current_distance + distance\n",
        "\n",
        "            if unvisited[neighbour] is None or unvisited[neighbour] > new_distance:\n",
        "                unvisited[neighbour] = new_distance\n",
        "\n",
        "        visited[start] = current_distance\n",
        "        del unvisited[start]\n",
        "        \n",
        "        if not unvisited:\n",
        "            break\n",
        "        \n",
        "        candidates = [node for node in unvisited.items() if node[1]]\n",
        "        start, current_distance = sorted(candidates, key = lambda x: x[1])[0]\n",
        "\n",
        "    path = list(visited.keys())\n",
        "    cost = list(visited.values())[-1]\n",
        "    return path, cost"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pCurNU-GzMow",
        "outputId": "3a03e80b-0e9d-4a29-c15b-aef7b753aa77"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['A', 'D', 'E', 'C']\n",
            "custo = 3\n"
          ]
        }
      ],
      "source": [
        "#      a\n",
        "#     / \\\n",
        "#    B - d\n",
        "#   / \\ / \\\n",
        "#  c - e - F\n",
        "#           \\\n",
        "#            G\n",
        "\n",
        "graph = {\n",
        "    'A': {'B': 9, 'D': 1},\n",
        "    'B': {'A': 9, 'C': 9, 'D': 9, 'E': 9},\n",
        "    'C': {'B': 9, 'E': 9},\n",
        "    'D': {'A': 9, 'B': 9, 'E': 1, 'F': 9},\n",
        "    'E': {'B': 9, 'C': 1, 'D': 9, 'F': 9},\n",
        "    'F': {'D': 9, 'E': 9, 'G': 9}\n",
        "}\n",
        "\n",
        "path, cost = dijkstra(graph, start='A', end='C')\n",
        "\n",
        "print(path)\n",
        "print('custo =', cost)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Função utilitária para resumo do grafo"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "id": "r6SbjjYOOI4b"
      },
      "outputs": [],
      "source": [
        "def graph_summary(graph):\n",
        "    # tentando adicionar um vértice e aresta já existentes\n",
        "    graph.add_edge('C', 'B', 10)\n",
        "    graph.add_vertex('B')\n",
        "\n",
        "    # tentando remover um vértice e aresta inexistentes\n",
        "    graph.remove_edge('Z', 'B')\n",
        "\n",
        "    # matriz de adjacências\n",
        "    print('\\nadjacency matrix')\n",
        "    graph.get_adjacency_matrix(pretty=True)\n",
        "\n",
        "    # peso da aresta (A,B)\n",
        "    print('\\nweight (A,B) =', graph.weight('A', 'B'))\n",
        "\n",
        "    # grau do vértice C\n",
        "    print('degree (C) =', graph.degree('C'))\n",
        "\n",
        "    # dfs e bfs\n",
        "    print('\\ndfs =', graph.depth_first_search(start='A'))\n",
        "    print('bfs =', graph.breadth_first_search(start='A'))\n",
        "\n",
        "    # dijkstra\n",
        "    path, cost = graph.dijkstra(start='A', end='C')\n",
        "    print('\\ndijkstra =', path)\n",
        "    print('custo =', cost)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "my461QtjNZ-X"
      },
      "source": [
        "# Criando uma grafo a partir de seus vértices e arestas"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wCSgVgL17lQW",
        "outputId": "52bb7993-5139-44e4-dde5-cdea179d5432"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "aresta ('C', 'B') já existe!\n",
            "vértice B já existe!\n",
            "aresta ('Z', 'B') não existe!\n",
            "\n",
            "adjacency matrix\n",
            "A {'B': 9, 'D': 1}\n",
            "B {'A': 9, 'D': 9, 'C': 9, 'E': 9}\n",
            "C {'B': 9, 'E': 1}\n",
            "D {'A': 1, 'B': 9, 'E': 1, 'F': 9}\n",
            "E {'B': 9, 'C': 1, 'D': 1, 'F': 9}\n",
            "F {'D': 9, 'E': 9, 'G': 9}\n",
            "G {'F': 9}\n",
            "\n",
            "weight (A,B) = 9\n",
            "degree (C) = 2\n",
            "\n",
            "dfs = ['A', 'B', 'E', 'F', 'G', 'D', 'C']\n",
            "bfs = ['A', 'B', 'D', 'C', 'E', 'F', 'G']\n",
            "\n",
            "dijkstra = ['A', 'D', 'E', 'C']\n",
            "custo = 3\n"
          ]
        }
      ],
      "source": [
        "graph = Graph()\n",
        "\n",
        "graph.add_vertex('A')\n",
        "graph.add_vertex('B')\n",
        "graph.add_vertex('C')\n",
        "graph.add_vertex('D')\n",
        "graph.add_vertex('E')\n",
        "graph.add_vertex('F')\n",
        "graph.add_vertex('G')\n",
        "\n",
        "graph.add_edge('A', 'B', 9)\n",
        "graph.add_edge('A', 'D', 1)\n",
        "graph.add_edge('B', 'D', 9)\n",
        "graph.add_edge('B', 'C', 9)\n",
        "graph.add_edge('B', 'E', 9)\n",
        "graph.add_edge('C', 'E', 1)\n",
        "graph.add_edge('D', 'E', 1)\n",
        "graph.add_edge('D', 'F', 9)\n",
        "graph.add_edge('E', 'F', 9)\n",
        "graph.add_edge('F', 'G', 9)\n",
        "\n",
        "graph_summary(graph)\n",
        "\n",
        "# os vértices em letra minúscula representam\n",
        "# o caminho de custo mínimo\n",
        "\n",
        "#      a\n",
        "#     / \\\n",
        "#    B - d\n",
        "#   / \\ / \\\n",
        "#  c - e - F\n",
        "#           \\\n",
        "#            G"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tfv0LJ0eNha6"
      },
      "source": [
        "# Criando um grafo a partir de sua matriz de adjacências"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5-26BKVYFCjq",
        "outputId": "30d014e9-b1cc-4028-85d3-aeb793080be9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "aresta ('C', 'B') já existe!\n",
            "vértice B já existe!\n",
            "aresta ('Z', 'B') não existe!\n",
            "\n",
            "adjacency matrix\n",
            "A {'B': 9, 'D': 1}\n",
            "B {'A': 9, 'C': 9, 'D': 9, 'E': 9}\n",
            "C {'B': 9, 'E': 9}\n",
            "D {'A': 9, 'B': 9, 'E': 1, 'F': 9}\n",
            "E {'B': 9, 'C': 1, 'D': 9, 'F': 9}\n",
            "F {'D': 9, 'E': 9, 'G': 9}\n",
            "G {'F': 9}\n",
            "\n",
            "weight (A,B) = 9\n",
            "degree (C) = 2\n",
            "\n",
            "dfs = ['A', 'B', 'E', 'F', 'G', 'D', 'C']\n",
            "bfs = ['A', 'B', 'D', 'C', 'E', 'F', 'G']\n",
            "\n",
            "dijkstra = ['A', 'D', 'E', 'C']\n",
            "custo = 3\n"
          ]
        }
      ],
      "source": [
        "adjacency_matrix = {\n",
        "    'A': {'B': 9, 'D': 1},\n",
        "    'B': {'A': 9, 'C': 9, 'D': 9, 'E': 9},\n",
        "    'C': {'B': 9, 'E': 9},\n",
        "    'D': {'A': 9, 'B': 9, 'E': 1, 'F': 9},\n",
        "    'E': {'B': 9, 'C': 1, 'D': 9, 'F': 9},\n",
        "    'F': {'D': 9, 'E': 9, 'G': 9},\n",
        "    'G': {'F': 9}\n",
        "}\n",
        "\n",
        "graph = Graph(adjacency_matrix=adjacency_matrix)\n",
        "graph_summary(graph)\n",
        "\n",
        "#      a\n",
        "#     / \\\n",
        "#    B - d\n",
        "#   / \\ / \\\n",
        "#  c - e - F\n",
        "#           \\\n",
        "#            G"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.9.7 ('base')",
      "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.9.7"
    },
    "vscode": {
      "interpreter": {
        "hash": "30f07e33239fa8282e26e15725321d07a8b0c67c5d45bbf6a7e3668dfd7ffdbf"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}