查找圖表所有可能的路徑與時間約束

Question

我的數據如下所示：

 source target 
time     
0.5 96253 94861 
1.0 96652 95091 
1.5 94861 95091 
2.5 95091 95409 
3.5 95409 97221 
4.5 97221 96781 
5.5 96781 97707 
6.5 97707 98191 
7.5 98191 99096 
8.5 99096 100016 
8.5 99096 100013 
9.5 100013 98663 
9.5 100016 98658 
10.5 98658 99573 
10.5 98663 99589 
11.5 99589 100506 
11.5 99573 100490 

• 內source和target列每個整數引用一個點。
• 每一行都是兩個點之間的鏈接。
• time索引是指可以找到鏈接的時間點。

一個聰明的算法是找到包含在數據集內的所有可能的軌跡。

例如在前面的例子中，4個軌跡存在：

[96253, 94861, 95091, 95409, 97221, 97221, 96781, 97707, 98191, 99096, 100016, 98658, 99573, 100490] 
[96652, 95091, 95409, 97221, 97221, 96781, 97707, 98191, 99096, 100016, 98658, 99573, 100490] 
[96253, 94861, 95091, 95409, 97221, 97221, 96781, 97707, 98191, 99096, 100013, 98663, 99589, 100506] 
[96652, 95091, 95409, 97221, 97221, 96781, 97707, 98191, 99096, 100013, 98663, 99589, 100506] 

---

此問題就可以恢復爲圖形理論問題。請參見下圖，它與開始時顯示的數據相對應。

的想法是要找到在該圖所有可能的路徑與約束尊重時間的邏輯：一個軌跡的點（節點）的有序列表，它只能從t去t+1（不能過去）。

---

該算法將在Python中實現。因此，任何Python技巧都是允許的:-)

Answer 1

應用圖論算法似乎是解決這個問題的明智之道。我使用了networkx python庫。

print(spot_ids) 

輸出：

 source target 
time     
0.5 96253 94861 
1.0 96652 95091 
1.5 94861 95091 
2.5 95091 95409 
3.5 95409 97221 
4.5 97221 96781 
5.5 96781 97707 
6.5 97707 98191 
7.5 98191 99096 
8.5 99096 100016 
8.5 99096 100013 
9.5 100013 98663 
9.5 100016 98658 
10.5 98658 99573 
10.5 98663 99589 
11.5 99589 100506 
11.5 99573 100490 

算法：

import itertools 
import networkx as nx 

# Build graph 
graph = nx.Graph() 
for t, spot in spot_ids.iterrows(): 
    graph.add_edge(int(spot['source']), int(spot['target']), attr_dict=dict(t=t)) 

# Find graph extremities by checking if number of neighbors is equal to 1 
tracks_extremities = [node for node in graph.nodes() if len(graph.neighbors(node)) == 1] 
tracks_extremities 

paths = [] 
# Find all possible paths between extremities 
for source, target in itertools.combinations(tracks_extremities, 2): 

    # Find all path between two nodes 
    for path in nx.all_simple_paths(graph, source=source, target=target): 

     # Now we need to check wether this path respect the time logic contraint 
     # edges can only go in one direction of the time 

     # Build times vector according to path 
     t = [] 
     for i, node_srce in enumerate(path[:-1]): 
      node_trgt = path[i+1] 
      t.append(graph.edge[node_srce][node_trgt]['t']) 

     # Will be equal to 1 if going to one time direction 
     if len(np.unique(np.sign(np.diff(t)))) == 1: 
      paths.append(path) 

for path in paths: 
    print(path) 

輸出：

[100490, 99573, 98658, 100016, 99096, 98191, 97707, 96781, 97221, 95409, 95091, 96652] 
[100490, 99573, 98658, 100016, 99096, 98191, 97707, 96781, 97221, 95409, 95091, 94861, 96253] 
[96652, 95091, 95409, 97221, 96781, 97707, 98191, 99096, 100013, 98663, 99589, 100506] 
[100506, 99589, 98663, 100013, 99096, 98191, 97707, 96781, 97221, 95409, 95091, 94861, 96253]