 # K-hop path between two nodes for a heterogeneous graph

Given two nodes, how to find the k-hop path between them?

Hi yudizhangzyd, I am wondering why do you need this util? Do you want to get all k-hop path (with nodes in order) or just the number of k-hop path? Thanks.

Networkx has API to get all the simple paths given two nodes all_simple_paths — NetworkX 3.0 documentation . You can then filter the k-hop paths upon that.

Hi frozenbugs, all paths is what I want.

I found it is not easy to convert dgl a heterogeneous graph to Networkx graph, does dgl provide such function? Would `to_homogeneous` and `to_networkx` work?

It is indeed not supported but we could add that! The question we have is what is the proper/most-intuitive way to represent a heterogeneous graph in networkx? We’d be really appreciated if you could give us a simple example.

That’s a good question. In my case, my heterogeneous graph is actually a relational graph. So nodes can have different types (such as human, address, phone number, etc) and I don’t care about the edges, perhaps just set different node attributes in networkx?
Not sure if that would be scalable very well.

Yes, I think setting node/edge attributes is the simplest. For example, to create a user-item graph with two relations “follow” and “like”:

Idea 1 Set the “type” attributes of nodes and edges.

``````>>> import networkx as nx
>>> G = nx.DiGraph()
``````

Idea 2 Set the “triples” edge attribute (rdflib’s practice)

``````>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge(0, 1, triples=("user", "follow", "user"))
>>> G.add_edge(0, 2, triples=("user", "follow", "user"))
>>> G.add_edge(2, 0, triples=("user", "follow", "user"))
>>> G.add_edge(0, 3, triples=("user", "like", "item"))
>>> G.add_edge(0, 4, triples=("user", "like", "item"))
>>> G.add_edge(2, 4, triples=("user", "like", "item"))
``````

BTW, as a workaround for now, you can construct such networkx graph using DGL’s `to_homogeneous` API to relabel all the nodes to IDs starting from 0. Below is a pseudo-code to implement idea 2:

``````import dgl
import networkx as nx

hg = ...  # your heterogeneous graph
g = hg.to_homogeneous()  # relabel all the nodes to IDs from 0
src, dst = g.edges()
etype_id = g.edata[dgl.ETYPE]
G = nx.DiGraph()
for u, v, etid in zip(src, dst, etype_id):
triples = hg.canonical_etypes[etid]
Thanks, yeah this workaround seems to be a good solution for now. I guess this can be wrapped in a function for future generalizations. 