Pythonで時空間ネットワーク(時間拡大ネットワーク)を実現する

networkx, numpy, decimalを使います.
networkxの有向グラフのノードを複製し,離散時刻とのペアを作って時間拡大ネットワークを定義します.
元の有向グラフは,8〜12行で示すように,5本の枝を持つとします.各枝には移動時間とコストが関連づけられています.
離散時刻の最小時刻は,0, 最大時刻は5,その間は0.25の等間隔に離散時刻を設定します.
等間隔の離散時刻を設定する為に,np.arange()を使います(16行目)
時間拡大ネットワークは,networkxの有向グラフ(DiGraph)として表し,tGと呼んでいます(20行目).
G.adjacency_iter()で,ネットワークGの各ノードの隣接リストの各要素に対する処理をしています.
25行目のdata = eattr['weight']で,元のネットワークの枝に対する属性(time,cost)をdataに代入しています.
data['time'], data['cost']によって,枝の移動時間と移動コストが得られます.


  1 import networkx as nx
  2 import numpy as np
  3 from decimal import *
  4 from math import *
  5 G=nx.DiGraph()
  6 tedges=[]
  7 #tail,head,time,cost
  8 tedges+=[(1,2,{'time':2,'cost':3})]
  9 tedges+=[(1,3,{'time':2,'cost':2})]
 10 tedges+=[(2,3,{'time':1,'cost':5})]
 11 tedges+=[(2,4,{'time':3,'cost':10})]
 12 tedges+=[(3,4,{'time':4.1,'cost':7})]
 13 G.add_weighted_edges_from(tedges)
 14 tstart,tend,tint=0.0,5.0,0.25
 15 epsilon=1e-7
 16 tdisctime=np.arange(tstart,tend+tint,tint)
 17 disctime=[]
 18 for t in tdisctime:
 19         disctime+=[float(Decimal(t).quantize(Decimal('.00'),
               rounding=ROUND_HALF_UP))]
 20 tG=nx.DiGraph()
 21 tedges=[]
 22 for tail,nbrs in G.adjacency_iter():
 23         for head,eattr in nbrs.items():
 24                 for tail_t in disctime:
 25                         data = eattr['weight']
 26                         arr_t=tail_t+data['time']
 27                         if arr_t>floor(arr_t/tint)*tint+1e-7:
 28                                 arr_t=(floor(arr_t/tint)+1)*tint
 29                         else:
 30                                 arr_t=floor(arr_t/tint)*tint
 31                         if arr_t<=tend:
 32                                 tcost=data['cost']
 33                                 tedges+=[((tail,tail_t),(head,arr_t),
                        {'weight':tcost})]
 34 tG.add_edges_from(tedges)
 35 for e in tG.edges_iter():
 36         print e