I've been trying to implement a fast Steiner path approximation connecting points on a road network. I found fast_pcst, a python package which calculates prize-collecting steiner paths extremely quickly, given an list of edges, node prizes, and edge costs.
Can I use this package to solve normal steiners just by giving every node a prize of 99999 so it connects them all? I tested it and it seems to capture every input node in the path. Here is my code:
import momepy
import pcst_fast
# store coordinates of nodes in a dictionary for plotting
coords = {}
for i, j, in enumerate(list(G.nodes)):
coords[i] = j
# convert nodes to a list of ids for input in pcst function
G = nx.relabel.convert_node_labels_to_integers(G, label_attribute='old_label')
lengths = nx.get_edge_attributes(G, "length")
nx.set_edge_attributes(G, values=lengths, name="weight")
nx.draw(G, pos=coords, node_size=5, alpha=0.4)
plt.title("Full road graph")
plt.show()
# define parameters for input, choose num of random nodes
num_steiners = 200
edge_list = [[int(u), int(v)] for u, v in G.edges()]
node_id = [i for i in range(len(G.nodes))]
prizes = [0]*len(G.nodes)
selection = random.sample(list(range(len(prizes))), num_steiners)
for s in selection:
prizes[s] = 9999 # some high value to catch no matter what
costs = list(lengths.values())
root = -1
num_clusters = 1
# Run pcst
vertices, eg = pcst_fast.pcst_fast(edge_list, prizes, costs, root, num_clusters, "gw", 1)
node_list = list(vertices)
nodes_to_plot = [n for n in G.nodes() if n in selection]
# Create a subgraph with only the nodes you want to plot
H = G.subgraph(nodes_to_plot)
# Plot the subgraph using networkx.draw()
nx.draw(H, pos=coords, with_labels=True, node_size=10)
plt.title("Nodes to connect")
plt.show()
print("Are all steiner nodes a subset of the outputed vertices?")
print(set(selection).issubset(set(node_list)))
I = G.subgraph(node_list).copy()
I = H.copy()
I.remove_edges_from(list(I.edges()))
for p in [edge_list[k] for k in eg]:
I.add_edge(p[0], p[1], key=0)
# Plot the subgraph using networkx.draw()
nx.draw(I, pos=coords, node_size=1)
plt.title("Steiner Path")
plt.show() ```
Update: I contacted the authors of the pcst package and they said that yes, you can use a pcst solver for regular steiner, as long as it goes through all terminal nodes and you are content with the solution