src_Python/sw_graph/ApSP_Johnson.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Johnson's Algorithm "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm Priority Queue for Graph Algorithm\n",
      "I'm Priority Queue for Graph Algorithm\n"
     ]
    }
   ],
   "source": [
    "import PriorityQ\n",
    "%run PriorityQ.py\n",
    "import WeightGraph\n",
    "%run WeightGraph.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Dijstra(G,s):\n",
    "    G.initialize_single_source(s)\n",
    "    S = []\n",
    "    \n",
    "    D = []\n",
    "    for v in list(G.graph_dict.keys()): \n",
    "        D.append((G.nm[v].d, G.nm[v].name))\n",
    "    Q = priority_queue(D)                   \n",
    "    #print(Q.h)\n",
    "    \n",
    "    while Q.size() != 0: \n",
    "        \n",
    "        u = Q.heap_extract_min()[1]                      # O(VlgV)\n",
    "        #print(\" >> \", u, \" vertex 꺼냄\")\n",
    "        S.append(u)\n",
    "        \n",
    "        # relaxation을 통해 v.d 를 update 한다.(queue의 값 역시 update 필요)\n",
    "        # for each vertex v ∈ G.adj[u]\n",
    "        for v in list(G.graph_dict[u]):                   #\n",
    "            G.relax(u,v)\n",
    "            #print(Q.find_index(v), (G.nm[v].d, v))\n",
    "            Q.key_update(Q.find_index(v),(G.nm[v].d, v))  #  O(ElgV)\n",
    "        \n",
    "        #print(Q.h)\n",
    "        #print(\" >> Q's size: \", Q.size())   \n",
    "    \n",
    "    #print(\"shortest path가 결정된 vertices set : \",S)\n",
    "    # running time : O(( |V| + |E| )lg|V| )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BellmanFord(G,s):\n",
    "    srt = G.sort_edge()\n",
    "    \n",
    "    G.initialize_single_source('s')\n",
    "    \n",
    "    \"\"\" Finding the single src shortest parth from s to each vertex\"\"\"\n",
    "    # iteration |V| - 1 \n",
    "    for i in range(len(G.graph_dict.keys())):           # O(V) * \n",
    "        # each edge (u,v) ∈ G.E\n",
    "        for [u,v] in srt:                               # O(E)\n",
    "               G.relax(u,v)           \n",
    "        \n",
    "    # test whether ∃ negative weight cycle \n",
    "    for [u,v] in srt:\n",
    "        if G.nm[v].d > G.nm[u].d + G.nm[u].edge[v]:\n",
    "            return False\n",
    "    \n",
    "    # T = O(|V||E|)\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "\n",
    "def Johnson(G):\n",
    "    #preprocessing\n",
    "    # making dummy src\n",
    "    srt = G.sort_edge()\n",
    "    g2 = G.graph_dict.copy()       # dictionary의 주소를 다르게 copy해야한다.(g2 의 변경이 g1이 변경되지 못하게 한다.)\n",
    "    w2 = G.weight_dict.copy()\n",
    "    g2['s'] = set(G.graph_dict.keys())\n",
    "    w2['s'] = {}\n",
    "    for v in g2['s']:\n",
    "        w2['s'][v] = 0\n",
    "    tempG = Graph(g2,w2)\n",
    "    \n",
    "    h = {}\n",
    "    \n",
    "    \n",
    "    # compute BellmanFord algo\n",
    "    if BellmanFord(tempG,'s') == False:\n",
    "        print(\"the input graph contains a negative weight cycle \")\n",
    "    else:\n",
    "        for v in list(G.graph_dict.keys()):\n",
    "            h[v] = tempG.nm[v].d\n",
    "        for [u,v] in srt:\n",
    "            # reweighting process (굳히 tempG.edge 에 대해서 바꿀 필요 없다.)\n",
    "            tempG.nm[u].edge[v] = G.nm[u].edge[v] + h[u] - h[v]\n",
    "            G.nm[u].edge[v] = tempG.nm[u].edge[v]   ## reweighting processing  w 를 w' 값으로 바꿨다.   \n",
    "            #print(\"vertex (\", u ,\", \",v,\") weight를 \", tempG.nm[u].edge[v], \"로 변경 \")\n",
    "        n = len(list(G.graph_dict.keys())) \n",
    "        D = np.ones((n,n))\n",
    "\n",
    "        for u in list(G.graph_dict.keys()):\n",
    "            Dijstra(G,u) # source를 u vertex로 하여 single src shortest path 구함 v.d 에 값 저장됨\n",
    "            #print(\"src \",u,\" 로 부터의 계산값 !! \")\n",
    "            #G.showinfo()\n",
    "            for v in list(G.graph_dict.keys()):\n",
    "                D[G.nm[v].number][G.nm[u].number] = G.nm[v].d + h[v] - h[u] # comeback reweighting value \n",
    "    \n",
    "    return D "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = {'a': set(['b','c','e']),\n",
    "     'b': set(['d','e']),\n",
    "     'c': set(['b']),\n",
    "     'd': set(['a','c']),\n",
    "     'e': set(['d'])}\n",
    "\n",
    "w = {'a': {'b':3, 'c':8, 'e':-4},\n",
    "     'b': {'d':1, 'e':7},\n",
    "     'c': {'b':4},\n",
    "     'd': {'a':2, 'c':-5},\n",
    "     'e': {'d':6}}\n",
    "\n",
    "\n",
    "G = Graph(g,w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  3.,  7.,  2.,  8.],\n",
       "       [ 1.,  0.,  4., -1.,  5.],\n",
       "       [-3., -4.,  0., -5.,  1.],\n",
       "       [ 2.,  1.,  5.,  0.,  6.],\n",
       "       [-4., -1.,  3., -2.,  0.]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = Johnson(G)\n",
    "D"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}