test2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from itertools import islice\n",
    "label = 'egdes_new5.txt'\n",
    "G = (nx.read_edgelist(label, create_using=nx.DiGraph(), nodetype=int, \n",
    "                      data=(('mode',int), ('cap',float),('flow',float),('len',float),('disu',float))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "egdes_new5.txt\n",
      "[0, 4, 7, 70, 3, 122, 69, 174, 121, 226, 173, 278, 225, 330, 277, 382, 329, 434, 444, 463, 468, 473, 481, 480]\n",
      "[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0, 1]\n",
      "22.46875\n",
      "[0, 4, 16, 28, 80, 90, 132, 142, 184, 194, 236, 246, 288, 298, 340, 350, 392, 402, 444, 463, 468, 473, 481, 480]\n",
      "[2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 1]\n",
      "22.46875\n",
      "[0, 4, 7, 70, 73, 122, 69, 174, 121, 226, 173, 278, 225, 330, 277, 382, 329, 434, 444, 463, 468, 473, 481, 480]\n",
      "[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0, 1]\n",
      "22.46875\n",
      "[0, 4, 7, 70, 3, 73, 122, 69, 174, 121, 226, 173, 278, 225, 330, 277, 382, 329, 434, 444, 463, 468, 473, 481, 480]\n",
      "[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0, 1]\n",
      "22.46875\n",
      "[0, 4, 7, 70, 3, 122, 125, 174, 121, 226, 173, 278, 225, 330, 277, 382, 329, 434, 444, 463, 468, 473, 481, 480]\n",
      "[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0, 1]\n",
      "22.46875\n"
     ]
    }
   ],
   "source": [
    "# try 2 505\n",
    "source = 0\n",
    "target = 480\n",
    "\n",
    "def k_shortest_paths(G, source, target, k, weight=None):\n",
    "    return list(islice(nx.shortest_simple_paths(G, source, target, weight='disu'), k))\n",
    "\n",
    "Paths = k_shortest_paths(G, source, target, 5)\n",
    "validpaths = []\n",
    "count = 0\n",
    "validpaths = Paths\n",
    "print(label)\n",
    "for path in Paths:\n",
    "    print(path)\n",
    "    sum = 0\n",
    "    mode = []\n",
    "    for i in range(len(path)-1):\n",
    "        weight=G.edges[path[i],path[i+1]]['disu']\n",
    "        mode.append(G.edges[path[i],path[i+1]]['mode'])\n",
    "        sum=sum+weight\n",
    "    print(mode)\n",
    "    print(sum)\n",
    "\n",
    "\n",
    "#     valid = 1\n",
    "#     for i in range(len(path)-1):\n",
    "#         if G.edges[path[i], path[i+1]]['mode'] !=0:\n",
    "#             continue\n",
    "#         elif G.edges[path[i], path[i+1]]['mode'] ==0:\n",
    "#             i+=1\n",
    "#             if i == (len(path)-1):\n",
    "#                 break\n",
    "#             elif G.edges[path[i], path[i+1]]['mode'] ==0:\n",
    "#                 valid = 0 \n",
    "#                 count+=1\n",
    "#                 if count == 5 :\n",
    "#                     break\n",
    "#                 print(path)\n",
    "# #                     print(path[i-1], path[i])\n",
    "# #                     print(path[i], path[i+1])\n",
    "#                 break\n",
    "#     if valid == 1:\n",
    "#         print(1)\n",
    "#         print(path)\n",
    "#         count+=1\n",
    "#         if count == 5 :\n",
    "#             break\n",
    "#         print(path)\n",
    "#         sum = 0\n",
    "#         mode = []\n",
    "#         for i in range(len(path)-1):\n",
    "#             weight=G.edges[path[i],path[i+1]]['disu']\n",
    "#             mode.append(G.edges[path[i],path[i+1]]['mode'])\n",
    "#             sum=sum+weight\n",
    "# #         print(mode)\n",
    "# #         print(sum)\n",
    "#         validpaths.append(path)\n",
    "        #存储路径的列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import re\n",
    "fh=open(\"expandnode2_forweight.txt\", \"r\")\n",
    "srs=fh.readlines()\n",
    "for sr in srs:\n",
    "    sr_1=re.split('\\s', sr)\n",
    "    #print(sr_1)\n",
    "    a=int(sr_1[0])\n",
    "    b=float(sr_1[1])\n",
    "    c=float(sr_1[2])\n",
    "    G.add_node(a, Loc=b, Tra=c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def Update_weight():\n",
    "    for i in range(len(path)-1):\n",
    "        if G.edges[path[i], path[i+1]]['mode'] ==1:\n",
    "            veh=12\n",
    "            t0=G.edges[path[i],path[i+1]]['len'] / veh\n",
    "            weight= 10*t0+20*2/60+15*0.2*t0+0.1*math.pow(t0,2)\n",
    "            G.add_edge(path[i], path[i+1], disu=weight)\n",
    "            \n",
    "        if G.edges[path[i], path[i+1]]['mode'] ==2:\n",
    "            veh=48\n",
    "            t0=G.edges[path[i],path[i+1]]['len'] / veh\n",
    "            k = (G.edges[path[i],path[i+1]]['flow']/G.edges[path[i], path[i+1]]['cap'] \n",
    "                 +4*10/G.edges[path[i], path[i+1]]['cap'])\n",
    "            weight = 10*t0+(10+20)*t0*0.15*math.pow(k, 4)+20*11/60\n",
    "            G.add_edge(path[i], path[i+1], disu=weight)\n",
    "            \n",
    "        if G.edges[path[i], path[i+1]]['mode'] ==3:\n",
    "            j=1\n",
    "            for link in list(G.edges.data()):\n",
    "                #print(link)\n",
    "                #print(link[0])\n",
    "                p=link[0]\n",
    "                q=link[1]\n",
    "                if (link[2]['mode']==2 and G.node[p]['Loc'] == G.node[path[i]]['Loc'] \n",
    "                    and G.node[q]['Loc']==G.node[path[i+1]]['Loc'] and \n",
    "                    G.node[q]['Tra'] == G.node[path[i+1]]['Tra']):\n",
    "                    j += 1\n",
    "                    print(j)\n",
    "                    veh=25\n",
    "                    t0=G.edges[path[i],path[i+1]]['len'] / veh\n",
    "                    k = G.edges[p, q]['flow'] / G.edges[p, q]['cap']+4*10/G.edges[p, q]['cap']\n",
    "                    weight = (10*t0+10*t0*0.15*math.pow(k, 4)+20*0.5/10+20*2/60+\n",
    "                              20*G.edges[path[i],path[i+1]]['flow']/250+2)\n",
    "                    G.add_edge(path[i], path[i+1], disu=weight)\n",
    "                                                                                 \n",
    "        if G.edges[path[i], path[i+1]]['mode'] ==4:\n",
    "            t0 = 3 / 60                                                                    \n",
    "            weight = 10 * t0 + 20*0.5/10+20*5/60+20*G.edges[path[i],path[i+1]]['flow']/30000+3\n",
    "            G.add_edge(path[i], path[i+1], disu=weight)\n",
    "                                                        \n",
    "        if G.edges[path[i], path[i+1]]['mode'] ==0:\n",
    "            if G.nodes[path[i]]['Tra'] != G.nodes[path[i+1]]['Tra']:\n",
    "                weight = 20*5/60\n",
    "                G.add_edge(path[i], path[i+1], disu=weight)\n",
    "            else:\n",
    "                weight = 0\n",
    "                G.add_edge(path[i], path[i+1], disu=weight)\n",
    "    return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "默认流量为0，根据流量更新一次权值\n",
    "\n",
    "初始流量是2000,然后根据更新后的权值，更新流量；\n",
    "根据流量更新权值\n",
    "$$ v_s^w(j+1) = v_s^w(j)+\\frac{1}{j}[y_s^w(j)-v_s^w(j)] $$\n",
    "这里的$v(1)$是0，$y(j)$是根据流量分配公式计算所得的流量，$y(1)$是2000流量分配到每条路上的流量（每次权值不一样）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#流量分配\n",
    "import math\n",
    "def flow_allocation(Flow,weights):\n",
    "    c =  [ 0 for _ in range(len(weights))]\n",
    "    sum = 0\n",
    "    for i in range(len(weights)):\n",
    "        c[i] = math.exp(-0.2*weights[i])\n",
    "        sum += c[i]\n",
    "    flow = [ 0 for _ in range(len(weights))]\n",
    "    for i in range(len(weights)):\n",
    "        flow[i] = Flow * c[i] / sum\n",
    "    return flow\n",
    "\n",
    "#流量更新\n",
    "def Update_flow(flow_old, times):\n",
    "    #y(j)不作为参数传入\n",
    "    #flow_old是就路径流量的列表\n",
    "    flow_new = [_ for _ in range(len(flow_old))]\n",
    "    for i in range(len(flow_old)):\n",
    "        flow_new[i] = flow_old[i] + 1/times * (flow_y[i] - flow_old[i])\n",
    "    return flow_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[424.040437411342, 424.040437411342, 424.040437411342, 303.83825035463207, 424.040437411342]\n"
     ]
    }
   ],
   "source": [
    "for path in validpaths:\n",
    "    Update_weight()\n",
    "#第一次默认流量为0，已经更新权值\n",
    "#分配2000流量给每条路：\n",
    "#更新权值后，重新计算每条路的权值和\n",
    "\n",
    "#每条路的权值和放到一个列表中\n",
    "def upathsum():\n",
    "    pathswes = []\n",
    "    for path in validpaths:\n",
    "        sum = 0\n",
    "        for i in range(len(path)-1):\n",
    "            weight=G.edges[path[i],path[i+1]]['disu']\n",
    "            sum=sum+weight\n",
    "        pathswes.append(sum)\n",
    "    return pathswes\n",
    "pathswes = upathsum()\n",
    "\n",
    "# print(pathswes)\n",
    "flow_y = flow_allocation(2000, pathswes)\n",
    "t = 1\n",
    "flow_ini = [0 for i in range(len(flow_y))]\n",
    "flow_new = Update_flow(flow_ini, t)\n",
    "print (flow_new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}