CODEWITHSUNDEEP
pythonpython-3.xlistgraphnetworkx
Luca Lazzati
Luca Lazzati

Reputation: 65

Shortest path of a list of Source and Destination networkx

I have a graph with relative nodes and edges like this:

enter image description here

what I would like is to find a way to do the shortest_path of networkx only of the nodes included in my list, that is:

source = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destination = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

I would like not to do this by hand, that is:

nx.shortest_path(G, source="10.0.11.100", target="10.0.12.100")
nx.shortest_path(G, source="10.0.11.100", target="10.0.13.100")
nx.shortest_path(G, source="10.0.11.100", target="10.0.14.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.11.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.13.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.14.100")
...

The result I would like looks like this:

[('10.0.12.100','10.0.14.100',['10.0.1.11', '10.0.1.23']), ('10.0.14.100', '10.0.12.100', ['10.0.1.22', '10.0.1.9']), ('10.0.11.100', '10.0.14.100', ['10.0.1.6', '10.0.1.18', '10.0.1.26']), ('10.0.14.100', '10.0.11.100' ,['10.0.1.25', '10.0.1.17', '10.0.1.5'])...]

That is [(Source, Destination, [Path from Source to Destination])]

Is there any way to do this? Thank you very much

This is my code:

import networkx
G = nx.DiGraph()
z = [('10.0.12.100', '10.0.1.1'),('10.0.1.1', '10.0.11.100'),('10.0.11.100', '10.0.1.2'),('10.0.1.2', '10.0.12.100'),('10.0.13.100', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.11.100'),('10.0.11.100', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.13.100'),('10.0.11.100', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.1.26'),('10.0.1.26', '10.0.14.100'),('10.0.14.100', '10.0.1.22'),('10.0.1.22', '10.0.1.9'),('10.0.1.9', '10.0.12.100'),('10.0.12.100', '10.0.1.1'),('10.0.1.1', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.13.100'),('10.0.13.100', '10.0.1.26'),('10.0.1.26', '10.0.14.100'),('10.0.13.100', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.1.2'),('10.0.1.2', '10.0.12.100'),('10.0.14.100', '10.0.1.25'),('10.0.1.25', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.11.100'),('10.0.12.100', '10.0.1.11'),('10.0.1.11', '10.0.1.23'),('10.0.1.23', '10.0.14.100'),('10.0.14.100', '10.0.1.25'),('10.0.1.25', '10.0.13.100')]
G.add_edges_from(z)
random_pos = nx.random_layout(G, seed=42)
pos=nx.spring_layout(G, pos=random_pos) 
nx.draw(
    G,
    pos=pos,
    node_color='#FF0000',
    with_labels=True,
    arrows=False
)

source = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destination = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

list_shortest_path = []
for i in G.nodes(data=True):
  DD = list_shortest_path.append(nx.shortest_path(G, source=i[0], target=i[1]))

Upvotes: 1

Views: 737

Answers (3)

AdielM
AdielM

Reputation: 31

You can use itertools.product and list comprehension.

from itertools import product

list_shortest_path = [(src, dst, nx.shortest_path(G, source=src, target=dst) 
for src, dst in product(sources, destinations) if src != dst]

Upvotes: 1

willcrack
willcrack

Reputation: 1852

Simply put you can do a double for loop:

sources = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destinations = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

res = []
for s in sources:
    for d in destinations:
        res.append((s, d, nx.shortest_path(G, source=s, target=d)))

But this may have some problems for some kind of graphs:

  • In case of a DiGraph(your case), this should be the solution to go for, since it considers the shortest path from both ends (source to destination is a different path than destination to source).

  • If you were to use a Graph(without directed edges) the most efficient solution would look similar to @Vanojx1's answer.

Upvotes: 2

Vanojx1
Vanojx1

Reputation: 5574

Isn't that the combinations of source nodes?

from itertools import combinations

for n1, n2 in combinations(source, 2):
    list_shortest_path.append((n1, n2, nx.shortest_path(G, source=n1, target=n2))

Upvotes: 1

Related Questions