DataAlgo2020_007(LongestPath)ext.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-007(最長経路問題)",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyPW2l33dMTTS3vxeLI/0W6r",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kameda-yoshinari/DataAlgo2020/blob/master/DataAlgo2020_007(%E6%9C%80%E9%95%B7%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yRmydXneMgT8",
        "colab_type": "text"
      },
      "source": [
        "# 4.1. 最長経路問題\n",
        "\n",
        "ここでは最長経路問題とそれを解くアルゴリズムについて学ぶ．\n",
        "\n",
        "**いつもの約束**  \n",
        "１つのコードセルだけの実行は Ctrl + Enter．  \n",
        "エディタで「インデント幅（スペース）は4で表示」「行番号を表示」「インデントガイドを表示」．  \n",
        "内部では日本語はUTF-8で表現されている．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CdQdV_MJIlce",
        "colab_type": "text"
      },
      "source": [
        "# 準備\n",
        "\n",
        "インスタンスに接続し起動する．  \n",
        "下記の手順でGoogle Driveをマウントする．  \n",
        "マウント先に移動し，作業フォルダとする．  \n",
        "これによって，インスタンスがリセットされてもGoogle Drive内にファイルが保存されるようにする．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DMtqXRXJIPMR",
        "colab_type": "code",
        "outputId": "a0a95ac3-9938-4f76-9e2f-6230f6c5c0c5",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 141
        }
      },
      "source": [
        "!echo \"Google Driveをマウントします\"\n",
        "from google.colab import drive \n",
        "drive.mount('/content/drive')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Google Driveをマウントします\n",
            "Go to this URL in a browser: https://accounts.google.com/o/oauth2/auth?client_id=947318989803-6bn6qk8qdgf4n4g3pfee6491hc0brc4i.apps.googleusercontent.com&redirect_uri=urn%3aietf%3awg%3aoauth%3a2.0%3aoob&response_type=code&scope=email%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdocs.test%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive.photos.readonly%20https%3a%2f%2fwww.googleapis.com%2fauth%2fpeopleapi.readonly\n",
            "\n",
            "Enter your authorization code:\n",
            "··········\n",
            "Mounted at /content/drive\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SABzmuELIaj2",
        "colab_type": "code",
        "outputId": "407f187b-a568-4276-f2e9-f769a575e843",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 138
        }
      },
      "source": [
        "!echo \"今回の作業用フォルダを作成しそこに移動します\"\n",
        "%cd /content/drive/My\\ Drive/\n",
        "%mkdir -p 202004_DataAlgo/DA2020_007\n",
        "%cd       202004_DataAlgo/DA2020_007\n",
        "!ls\n",
        "!echo \"日本時間表示\"\n",
        "!rm /etc/localtime\n",
        "!ln -s /usr/share/zoneinfo/Japan /etc/localtime\n",
        "!date"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "今回の作業用フォルダを作成しそこに移動します\n",
            "/content/drive/My Drive\n",
            "/content/drive/My Drive/202004_DataAlgo/DA2020_007\n",
            "graph5dash1.h  graph5dash.h  graph6dash.h  longestpath_J\n",
            "graph5dash2.h  graph5.h      graph6.h\t   longestpath_J.c\n",
            "日本時間表示\n",
            "Sun Jun  7 18:20:23 JST 2020\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NINxYWNgOSaw",
        "colab_type": "text"
      },
      "source": [
        "ここでは，グラフ5を利用する．  \n",
        "頂点数は8．有向グラフ．閉路なし．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tErWQzIr6Ttp",
        "colab_type": "text"
      },
      "source": [
        "![da2020-graph5](https://user-images.githubusercontent.com/45651568/84226060-bfe2cd00-ab1b-11ea-8493-9b077d00e569.jpg)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rz4_9z4rOQu4",
        "colab_type": "code",
        "outputId": "c810e866-8f51-4e39-e194-0c37c3f1a34d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "%%writefile graph5.h\n",
        "// 8 nodes, directed, no cycle.\n",
        "#define N 8\n",
        "int edge[N][N] = {\n",
        "//   0 1 2 3 4 5 6 7\n",
        "\t{0,4,0,0,2,0,0,0}, // 0\n",
        "\t{0,0,0,0,0,0,1,0}, // 1\n",
        "\t{0,0,0,3,0,0,3,0}, // 2\n",
        "\t{0,0,0,0,0,0,0,5}, // 3\n",
        "\t{0,0,0,0,0,2,0,0}, // 4\n",
        "\t{0,0,0,0,0,0,0,0}, // 5\n",
        "\t{0,0,0,0,0,4,0,1}, // 6\n",
        "\t{0,0,0,0,0,0,0,0}  // 7\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Overwriting graph5.h\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4s3BWazcz1FB",
        "colab_type": "text"
      },
      "source": [
        "# 最長経路問題概要\n",
        "\n",
        "**内容**\n",
        "\n",
        "グラフとして重み付き有向グラフを考える．辺に重みとして数値が付与されている．\n",
        "本節では，辺の重みは正値とする．\n",
        "隣接する頂点aと頂点bの間の辺の重みをedge(a,b)で表現する．edge(a,b)は正値である．  \n",
        "\n",
        "最長経路問題とは，与えられた重み付き有向グラフにおいて，その重みの合計が最も大きい道を求める問題である．なお，頂点Aから頂点Bへの「道」には，同じ頂点は高々一度しか現れないことに注意する．以降，ある道（経路）が与えられた時，その辺の重みの合計のことを経路（道）の重みと呼ぶ．\n",
        "\n",
        "頂点集合V中のある頂点kについて注目する．\n",
        "頂点kを到着頂点とする道の中で最も重みのある道の重みをW(k)で表すとする．  \n",
        "求めたいのは，頂点集合 V の中で最大の W(k_max) であり，それを実現する道の構成である．  \n",
        "\n",
        "今，ここで，頂点dより上流の全ての頂点sではW(s)がわかっているものとする．  \n",
        "すると，W(d)は次式によって求められる．  \n",
        "> W(d) = max ( W(s) + edge(s,d) )   \n",
        "> ただしsは頂点dに向かって隣接しているすべての頂点  \n",
        "\n",
        "では「頂点dより上流の全ての頂点sではW(s)がわかっているものとする」ことをどうやって保証すればいいのであろうか．それを保証するのがトポロジカルソーティングである．  \n",
        "\n",
        "アルゴリズムは３部構成になる．  \n",
        "\n",
        "1. トポロジカルソーティングを実施する\n",
        "2. 上流から順に頂点kについて W(k) を求めていく\n",
        "3. 全頂点について求めた W( ) において最大の値 W(k_max) を求める\n",
        "\n",
        "**実装**\n",
        "\n",
        "トポロジカルソーティングについては前のプログラムをそのまま流用する．\n",
        "\n",
        "参考までに，グラフ5では最長経路の重みは 9 となる．  \n",
        "Longest Path Value = 9  \n",
        "5 <- 6 <- 1 <- 0 <- Go"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_o0avWIHZqC",
        "colab_type": "text"
      },
      "source": [
        "# 最長経路問題を解くプログラム\n",
        "\n",
        "**目標**\n",
        "\n",
        "無閉路の有向グラフにおいて最長経路の重みとその経路を求める．\n",
        "\n",
        "**説明**\n",
        "\n",
        "アルゴリズムは３部構成になる．\n",
        "\n",
        "1. トポロジカルソーティングを実施する\n",
        "2. 上流から順に頂点kについて W(k) を求めていく\n",
        "3. 全頂点について求めた W( ) において最大の値 W(k_max) を求める\n",
        "\n",
        "**コード**\n",
        "\n",
        "アルゴリズムを３部構成に分けたので，それぞれをユーザ定義関数で実現する．\n",
        "\n",
        "**備考**\n",
        "\n",
        "アルゴリズムの3.は2.の中に統合できるが，アルゴリズム説明とプログラム記述を揃えるために別関数で用意している．  \n",
        "このプログラムでは，最長経路の重みを求めるだけでなく，最長経路の構成を表示するために工夫をしている．\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Eo2CM8EqZi97",
        "colab_type": "code",
        "outputId": "5398d622-0ad7-4637-b422-fc7fbb088c60",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "%%writefile longestpath_J.c\n",
        "// Topological Sorting\n",
        "//    2020/05/24 kameda\n",
        "#include <stdio.h>\n",
        "#include \"graph5dash2.h\"\n",
        "\n",
        "typedef struct {int W; int src;} ppath;\n",
        "\n",
        "int tsort[N];  // トポロジカルソーティング結果を記録するための配列\n",
        "int num_tsort = 0; // 記録済の頂点数\n",
        "ppath path[N]; // 経路を参照できるようにするためのリンクトリスト風配列\n",
        "\n",
        "int listed[N];  // 0 未, 1 済\n",
        "\n",
        "// 深さ優先探索本体 / 再帰呼出\n",
        "void dfs(int CurrentRoom){\n",
        "    int RoomToCheck;\n",
        "\n",
        "\t// 処理済みであることを記録\n",
        "\tlisted[CurrentRoom] = 1;\n",
        "\n",
        "    // 次にどの頂点を列挙していくか検討\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "        if (edge[CurrentRoom][RoomToCheck] != 0 && listed[RoomToCheck] == 0) \n",
        "\t\t\tdfs(RoomToCheck);\n",
        "\t}\n",
        "\n",
        "\t// トポロジカルソーティング\n",
        "\tprintf(\"●●列挙： %d\\n\", CurrentRoom);\n",
        "\ttsort[num_tsort] = CurrentRoom;\n",
        "\tnum_tsort++;\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "// それぞれの頂点での最長経路（最長経路を解くための探索）\n",
        "void findlongest (void) {\n",
        "\tint p; // トポロジカルソート結果配列 tsort 上での注目箇所\n",
        "\tint d; // 検討する頂点の番号\n",
        "\n",
        "\t// Cleaning up\n",
        "\t// 最長経路を計算するための配列を初期化\n",
        "\t{\n",
        "\t\tint i;\n",
        "\t\tfor (i = 0; i < N; i++) {\n",
        "\t\t\tpath[i].W = 0; // the largest cost of the paths that terminates at vertex i\n",
        "\t\t\tpath[i].src = -1; // the src vertex that gives us the path of the largest cost\n",
        "\t\t}\n",
        "\t}\n",
        "\t\n",
        "\t// Take up a vertex from the end of tsort[] (i.e. starting from source vertices)\n",
        "\t// トポロジカルソートの順に上流側から頂点を処理\n",
        "\tfor (p = N-1; p >= 0; p--) {\n",
        "\t\tint s;\n",
        "\t\td = tsort[p];\n",
        "\t\tfor (s = 0; s < N; s++) {\n",
        "\t\t\tif (edge[s][d] > 0 && path[s].W + edge[s][d] > path[d].W) {\n",
        "\t\t\t\tpath[d].W = path[s].W + edge[s][d];\n",
        "\t\t\t\tpath[d].src = s;\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t}\n",
        "\n",
        "\t// 結果の表示\n",
        "\tprintf(\"Node  : \");\n",
        "\tfor (d = 0; d < N; d++) \n",
        "\t\tprintf(\"%3d \", d);\n",
        "\tprintf(\"\\n\");\n",
        "\tprintf(\"Weight: \");\n",
        "\tfor (d = 0; d < N; d++) \n",
        "\t\tprintf(\"%3d \", path[d].W);\n",
        "\tprintf(\"\\n\");\n",
        "\tprintf(\"Src   : \");\n",
        "\tfor (d = 0; d < N; d++) \n",
        "\t\tprintf(\"%3d \", path[d].src);\n",
        "\tprintf(\"\\n\");\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "// 最長経路を求めて表示\n",
        "void findfinalsolution (void) {\n",
        "  \tint LVertex; // 解：最長経路の到着頂点（終点）\n",
        "\tint i;\n",
        "\n",
        "\t// Tentative vertex candidate (of longest path)\n",
        "\t// 頂点0を仮解とする\n",
        "\tLVertex = 0;\n",
        "\n",
        "\t// find the actual (destination) vertex\n",
        "\t// 最長経路の頂点 LNode を探す\n",
        "\tfor (i = 1; i < N; i++) {\n",
        "\t\tif (path[i].W > path[LVertex].W)\n",
        "\t\t\tLVertex = i;\n",
        "\t}\n",
        "\n",
        "\t// Show the longest path\n",
        "\tprintf(\"Longest Path Value = %d\\n\", path[LVertex].W);\n",
        "\tfor (i = LVertex; i >= 0; i = path[i].src)\n",
        "\t\tprintf(\"%d <- \", i);\n",
        "\tprintf(\"Go\\n\");\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "\tint StartingNode;\n",
        "\tint i;\n",
        "\n",
        "\tprintf(\"1. トポロジカルソーティングを開始します．\\n\");\n",
        "\tfor (StartingNode = 0; StartingNode < N; StartingNode++) {\n",
        "\t\tif (listed[StartingNode] == 0) {\n",
        "\t\t\tdfs(StartingNode);\n",
        "\t\t}\n",
        "\t}\n",
        "\tprintf(\"T.Sort 結果 : \");\n",
        "\tfor (i = 0; i < N; i++)\n",
        "\t\tprintf(\"%d \", tsort[i]);\n",
        "\tprintf(\"\\n\");\n",
        "\n",
        "\tprintf(\"2. 最長経路を解くための探索を開始します． \\n\");\n",
        "\tfindlongest();\n",
        "\n",
        "\tprintf(\"3. 最長経路を求めて表示します． \\n\");\n",
        "\tfindfinalsolution();\n",
        "\n",
        "  return 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Overwriting longestpath_J.c\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zhechXUNbvva",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "コンパイルしてエラーが無いことを確認．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5gxNiHT-bvEd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o  longestpath_J longestpath_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CxBI4UbEcB9L",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O3zzVD4tcA3h",
        "colab_type": "code",
        "outputId": "717f8837-c530-48cc-af65-3c522303da83",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 260
        }
      },
      "source": [
        "!./longestpath_J"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1. トポロジカルソーティングを開始します．\n",
            "●●列挙： 5\n",
            "●●列挙： 7\n",
            "●●列挙： 6\n",
            "●●列挙： 1\n",
            "●●列挙： 4\n",
            "●●列挙： 0\n",
            "●●列挙： 3\n",
            "●●列挙： 2\n",
            "T.Sort 結果 : 5 7 6 1 4 0 3 2 \n",
            "2. 最長経路を解くための探索を開始します． \n",
            "Node  :   0   1   2   3   4   5   6   7 \n",
            "Weight:   6  10   0   3   8  15  11  12 \n",
            "Src   :   6   0  -1   2   0   6   1   6 \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DY_MbwoPf_9h",
        "colab_type": "text"
      },
      "source": [
        "# 節末課題\n",
        "\n",
        "1. 最長経路の表示の仕組み  \n",
        "最長経路の頂点の並びを表示する仕組みについて，longestpath_J プログラムに即して説明せよ．\n",
        "このとき，構造体ppathのメンバ src に格納されている値について言及すること．\n",
        "\n",
        "2. 計算量  \n",
        "最長経路問題を解く longestpath_J プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "3. 閉路の扱い  \n",
        "最長経路問題において，与えるグラフには閉路が存在していないと仮定した．そのことに必然性があるかどうか議論せよ．\n",
        "\n",
        "4. 閉路の実際上の扱い  \n",
        "本節の longestpath_J プログラムでは，実際には閉路が含まれるグラフを与えても実行すると結果が出てしまうことがある．\n",
        "これは，閉路があると最長経路が解として得られないはず，ということと矛盾する．\n",
        "本プログラムで実行結果がでるのは，グラフの解釈を都合のよいように勝手に変えているからと考えることができる．  \n",
        "それでは，本プログラムでは，閉路が存在するとき，それをどう解釈しているのか，説明を試みよ．\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/06/10.\n",
        "\n"
      ]
    }
  ]
}