List the shortest paths between two nodes

Hi,

Thank you for this great tool! I wonder if it is possible to use DGL to implement the function that returns the shortest paths (a list of nodes) between a source and destination node, like the ones in NetworkX. Thanks!

Best,
Yongcheng

We don’t have a builtin function for shortest paths. You can either use the one from scipy.sparse.csgraph for faster CPU execution or write your own by message passing for single-source shortest path: essentially the message function will be adding the source node’s value and the reduce function will be taking the minimum of all messages.

1 Like

Hi @BarclayII

Thank you for the help! I truly appreciate it! Now I got a list of node IDs and would like to use the following code to propagate information with each obtained node ID list:

for id_list in list_set:
    subgraph = dgl.node_subgraph(graph, id_list)
    subgraph.prop_nodes(id_list, fn.copy_src('h', 'm'), fn.sum('m', 'h'))

The execution speed is super slow if I have many ID lists for propagation. Could you please give me some hints on how to improve the efficiency by paralleling the execution with different node ID list? Thanks!

Best,
Yongcheng

I assume that you would like to gather messages for the specific nodes in a series of lists, list by list, on the original graph.

If that’s the case, you can just do

graph.prop_nodes(id_list, fn.copy_src('h', 'm'), fn.sum('m', 'h'))

In other words, you don’t have to take a subgraph every time.

1 Like

Hi @BarclayII

Thank you for the quick response! Yes, that’s exactly what I would like to do. I will try to use graph instead of subgraph for propagation. Also, is there any way to parallelize the list-by-list propagation process? Thanks!

Best,
Yongcheng

You cannot parallelize propagation of a single list-of-list because propagation within one node list will depend on the propagation on the previous node list. Propagation within each node list is already parallelized.

If you have multiple such list-of-lists and you wish to parallelize them instead, a possible way is to create multiple replicas of the same graph, combine those list-of-lists into a single list-of-list, and then call prop_nodes with that. The combination will look something like

N = graph.num_nodes()
# list_of_lists[i][j] represents the j-th node list of the i-th list-of-lists
for i in range(len(list_of_lists)):
    for j in range(len(list_of_lists[i])):
        list_of_lists[i][j] += N * i
list_of_list_zip = itertools.zip_longest(list_of_lists)
list_of_list = [sum((l for l in ll if l is not None), []) for ll in list_of_list_zip]
1 Like

Hi @BarclayII

I truly appreciate your help! Thanks!

Best,
Yongcheng

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.