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

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 connecting them all, which is the longest possible path in the graph. For that you could build a directed graph using NetworkX, and look for the longest path with nx.dag_longest_path:

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')}]

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

Obtain path from unordered list of edges

python

graph-theory

networkx