从无序的边列表中获取路径

Question

如何对仅包含边的图形进行排序>；开始、结束<；数据我不知道我的旅程从哪里开始，也不知道它从哪里结束，所以我不能把一个带到旅程开始的地方，然后把一个缺失的附加到它上面

graph_before=[
    {"order" : ("Stockholm", "New York JFK")},
    {"order" : ("Barcelona", "Girona Airport")},
    {"order" : ("Madrid", "Barcelona")},
    {"order" : ("Girona Airport", "Stockholm")},
]


graph_after=[
    {"order" : ("Madrid", "Barcelona")},
    {"order" : ("Barcelona", "Girona Airport")},
    {"order" : ("Girona Airport", "Stockholm")},
    {"order" : ("Stockholm", "New York JFK")},
]
# Trip Madrid > New York JFK

Answer 1

因为看起来你有一个无序的边列表，你要寻找的是连接所有边的path，也就是longest possible path in the graph。为此，您可以使用NetworkX构建一个有向图，并使用^{}查找最长路径：

import networkx as nx

edges = [tuple(*d.values()) for d in graph_before]
# [('Stockholm', 'New York JFK'), ('Barcelona', 'Girona Airport')...
G = nx.DiGraph()
G.add_edges_from(edges)
longest_path = nx.dag_longest_path(G)
graph_after = list(zip(longest_path[:-1], longest_path[1:]))

---

print(graph_after)
[('Madrid', 'Barcelona'),
 ('Barcelona', 'Girona Airport'),
 ('Girona Airport', 'Stockholm'),
 ('Stockholm', 'New York JFK')]
​

对于与graph_before相同的结构：

graph_after = [{'order': edge} for edge in graph_after]

print(graph_after)
[{'order': ('Madrid', 'Barcelona')},
 {'order': ('Barcelona', 'Girona Airport')},
 {'order': ('Girona Airport', 'Stockholm')},
 {'order': ('Stockholm', 'New York JFK')}]