CODEWITHSUNDEEP
pythonnetworkxgraph-theory
mikazz
mikazz

Reputation: 179

Obtain path from unordered list of edges

How to sort my graph that contains edges with only >begin, end< data. I don't know where my journey starts or where it ends, so I can't just take one where journey begins and append to it missing one's.

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

Upvotes: 0

Views: 129

Answers (1)

yatu
yatu

Reputation: 88226

Since it looks like you have an unordered list of edges, what you're looking for is the 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')]
​

For the same structure as 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')}]

Upvotes: 2

Related Questions