Given Edges, How Can Find Routes That Consists Of Two Edges In A Vectorised Way?
I have an array of towns and their neighbours. I want to get a set all the pairs of towns that have at least one route that consists of exactly two different edges. Is there a vect
Solution 1:
You can use the networkx library:
import numpy as np
import networkx as nx
import matplotlib.pyplotas plt
from itertools import combinations
a = np.array([[3,0], [0,4], [5,0], [2,1], [1,4], [2,3], [5,2]])
G = nx.Graph()
G.add_edges_from(a)
#Createsthis newtork
nx.draw_networkx(G)
# Create pairs of all nodes in network
c = combinations(G.nodes, 2)
# Find all routes between each pair in the network
routes = [list(nx.all_simple_paths(G, i, j, cutoff=2))[0] for i, j in c]
# Select only routes with three nodes/two edges the show first and last node
paths_2_edges = [(i[0], i[-1]) for i in routes if len(i) == 3]
print(paths_2_edges)
Output:
[(3, 4), (3, 5), (3, 1), (0, 2), (0, 1), (4, 5), (4, 2), (5, 1)]
Per comments
Vectorize this statement: np.concatenate([combs(n) for n in target])
:
For t = get_incidences(roads)[1]
s2 = get_combinations_triu(t)
Output s2:
array([[4, 3],
[4, 5],
[3, 5],
[4, 2],
[1, 3],
[1, 5],
[3, 5],
[0, 2],
[0, 1],
[0, 2]])
%timeit get_combinations_triu(t)
96.9 µs ± 3.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Then
s1 = np.array([x for i in t for x in combinations(i,2)])
Output s1:
array([[4, 3],
[4, 5],
[3, 5],
[4, 2],
[1, 3],
[1, 5],
[3, 5],
[0, 2],
[0, 1],
[0, 2]])
And, (s1 == s2).all()
True
Timeit:
%timeit np.array([x foriin t forxinlist(combinations(i,2))])
14.7 µs ± 577 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Post a Comment for "Given Edges, How Can Find Routes That Consists Of Two Edges In A Vectorised Way?"