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)