Can the Prize-Collecting Steiner Tree problem be reduced to a normal Steiner Tree in graphs?

65 Views Asked by At

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()  ```
1

There are 1 best solutions below

0
On

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